Как массив PHP реализован на уровне C?
PHP array является одной из основных функций PHP. Он разрежен, допускает многопечатные ключи в одном и том же массиве и поддерживает набор, словарь, массив, стек / очередь и итеративную функциональность.
Но, поработав некоторое время с PHP, я обнаружил, что довольно много array_* функции гораздо медленнее, чем вы думаете на первый взгляд. Как и в случае array_rand на очень большом массиве (10000+). array_rand на самом деле настолько медленный, что в тех случаях, когда вы используете массив php в качестве индексированного массива, такая функция rand( 0, array_length( $array ) - 1 ) работает НАМНОГО быстрее, чем array_rand,
Теперь на мой вопрос.
Как массив PHP реализован на уровне C? Это было бы очень полезно для прогнозирования Big O функции, которая интенсивно использует различные функциональные возможности типа данных массива PHP.
5 ответов
PHP ассоциативные массивы фактически являются реализацией HashTables.
Внутренне можно создавать числовые или ассоциативные массивы. Если их объединить, это ассоциативный массив.
В числовых массивах это очень похоже на C. У вас есть массив указателей на структуры ZVAL.
Поскольку указатели имеют фиксированную длину (назовем это n), вычисление смещения (x) легко: x * n.
В PHP типы являются структурами ZVAL (потому что таким образом он реализует динамические типы), но это также помогает в ассоциативном массиве, потому что вы можете использовать фиксированную длину. Таким образом, даже если прямой доступ к массиву медленнее, он все равно считается O(1).
Так что же происходит в строковых ключах? PHP использует хеш-функцию для преобразования их в целые числа.
Поиск в числовом и ассоциативном массиве имеет одинаковую эффективность, поскольку внутренне все они являются числовыми.
Только прямой доступ к ключам массива медленнее из-за дополнительного уровня (хэш-функция).
После прочтения через zend/zend_hash.h и ext/standard/array.c, я думаю, что нашел ответ (спасибо Крису и Гамбо за предложения).
Массив PHP представляет собой цепочечную хеш-таблицу (поиск O(c) и O(n) при столкновении ключей), которая позволяет использовать ключи типа int и string. Он использует 2 разных алгоритма хеширования для размещения двух типов в одном и том же хэш-ключе. Также каждое значение, сохраненное в хэше, связано со значением, сохраненным до него, и значением, сохраненным после (связанный список). Он также имеет временный указатель, который используется для хранения текущего элемента, поэтому хэш может быть повторен.
Улов для array_rand Функция заключается в том, что для того, чтобы ключ был действительно случайным, array_rand функция должна перебирать массив rand(0, count($array)) раз (O(n)). Это связано с тем, что за время O(c) невозможно перейти к смещению в хэш-таблице, поскольку нет гарантии, что в диапазоне нет пропущенных ключей.
Это открытие несколько обеспокоило меня, потому что это означает, что в PHP НЕТ типа данных, который имеет нормальные характеристики массива Си. Сейчас в большинстве случаев это нормально, потому что поиск по хешу очень быстрый, но в таких случаях array_rand,
Еще одна вещь, которая также беспокоила меня, была разница между реализацией array_key_exists а также in_array, array_key_exists использует поиск хеша (большую часть времени O(c)), чтобы увидеть, есть ли ключ в массиве, в то время как in_array должен линейно искать хеш (O(n)).
Рассмотрим два примера ниже:
in_array версия
$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
//we found a value
}
версия array_key_exists
$array = array_fill_keys( range(0, 100000), NULL );
if( array_key_exists( $random_key, $array ) ) {
//we found a value, err key
}
Хотя версия in_array выглядит намного чище и проще для понимания, она на самом деле очень медленная для больших массивов (O(n)), где array_key_exists (несмотря на раздражающее длинное имя) очень быстр (O(c) или close).
В заключение: хотелось бы, чтобы в структуре данных Zend HashTable был прозрачный флаг, который будет установлен в случаях, когда массив был создан с использованием array_push или же array[] = $value это позволило бы масштабировать как массив C вместо связанного списка.
Поскольку массивы PHP являются упорядоченными картами (даже при использовании смежных целочисленных индексов) array_rand() Скорее всего, должен составить список ключей для выбора элемента. Я предполагаю, что было бы непомерно неэффективным пространство и время для кэширования (часто недействительного) списка ключей, так что каждый вызов будет стоить как минимум O(n) обхода и затрат на построение.
Потому что ваш rand(... length ...) реализация использует ваши специальные знания о том, что ключи являются смежными целыми числами, вы получите O(log n) затрат на поиск. Это похоже на данные Chacha102.
Взгляни на zend/zend_hash.c а также zend/zend_hash.h
Я не знаю c, но для меня это похоже на цепочку хэш-таблицы.
См. Этот комментарий в документации, подтверждающий вашу дилемму, что array_rand, хотя и работает быстро для небольших массивов, очень плохо масштабируется.
Я изменил fake_array_rand так, чтобы он всегда возвращал только 1 элемент, и сделал несколько тестов для вызова функции array_rand со вторым параметром, равным 1. Я провел 100 выборок для каждой функции для каждого числа элементов и взял средний результат. В то время как внутренний массив array_rand быстрее для небольшого числа элементов, он очень плохо масштабируется.
1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. for fake_array_rand 10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. for fake_array_rand 100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. for fake_array_rand 1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. for fake_array_rand 10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. for fake_array_rand 100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. for fake_array_rand 1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand <?php function fake_array_rand ($array) { $count = count ($array); # Help keep the number generator random :) $randval and usleep ("0.$randval"); # Seed the random number generator # Generate a random number srand ((double) microtime() * 10000000); $randval = rand(); # Use the random value to 'pick' an entry from the array # Count the number of times that the entry is picked ++$index[$randval % $count]; return $array[$randval % $count]; } ?>