array PHP является одной из основных функций PHP. Он разрежен, позволяет использовать многотипные ключи в одном массиве и поддерживает набор, словарь, массив, стек / очередь и итеративную функциональность.
Но после работы с PHP на некоторое время, я обнаружил, что многие из функций array_* намного медленнее, чем вы думаете на первый взгляд. Как и в случае array_rand на очень большом массиве (10000+). array_rand на самом деле настолько медленен, что в тех случаях, когда вы используете массив php в качестве индексированного массива, функция типа rand( 0, array_length( $array ) - 1 ) работает намного быстрее, чем array_rand .
Теперь на мой вопрос.
Как реализуется массив PHP на уровне C? Это было бы очень полезно для прогнозирования Big O функции, которая в значительной степени использует различные функции типа данных массива PHP.
PHP-ассоциативные массивы фактически реализуют HashTables .
Внутри можно создавать числовые массивы или ассоциативные массивы. Если вы их объединяете, это ассоциативный массив.
В числовых массивах он очень похож на C. У вас есть массив указателей на структуры ZVAL.
Поскольку указатели имеют фиксированную длину (назовем ее n), вычисление смещения (x) легко: x * n.
В PHP-типах это структуры ZVAL (потому что он реализует динамические типы), но также помогает в ассоциативном массиве, поскольку вы можете считать фиксированную длину. Поэтому, даже если прямой доступ к массиву медленнее, он все еще считается O (1).
Итак, что происходит в строковых клавишах? PHP использует хэш-функцию для преобразования их в межсетевые.
Поиск в числовом и ассоциативном массиве имеет схожую эффективность, потому что внутри они все числовые.
Только прямой доступ к клавишам массива медленнее из-за дополнительного уровня (хэш-функция).
Прочитав zend / zend_hash.h и ext / standard / array.c, я думаю, что нашел ответ (Спасибо, Крис и gumbo за предложения).
Массив PHP представляет собой цепочку хеш-таблицы (поиск O (c) и O (n) при столкновении ключей), которая позволяет использовать int и строковые ключи. Он использует 2 разных алгоритма хэширования, чтобы соответствовать двум типам в одно и то же пространство хеш-ключа. Также каждое значение, хранящееся в хеше, связано со значением, хранящимся перед ним, и значением, сохраненным после (связанный список). Он также имеет временный указатель, который используется для хранения текущего элемента, поэтому хэш может быть повторен.
array_rand функции array_rand заключается в том, что для обеспечения того, что ключ действительно случайный, функция array_rand должна итерации по массиву rand(0, count($array)) раз (O (n)). Это связано с тем, что нет способа перейти к смещению в хеш-таблице в времени O (c), потому что нет гарантии, что в этом диапазоне отсутствуют недостающие ключи.
Это открытие несколько смутило меня, потому что это означает, что в PHP нет типа данных, который имеет обычные характеристики массива C. В большинстве случаев это нормально, потому что поиск в хэше очень быстрый, но ошибки проявляются в таких случаях, как array_rand .
Еще одна вещь, которая также беспокоила меня, – это разница между реализацией array_key_exists и array_key_exists . 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() вероятно, должен array_rand() список ключей для выбора элемента. Я предполагаю, что было бы непомерно время и время неэффективно кэшировать (часто недействительный) список ключей, поэтому каждый вызов будет по меньшей мере обходить обход и стоимость строительства.
Поскольку ваша реализация rand(... length ...) использует преимущества специального знания, которое у вас есть, что ключи являются непрерывными целыми числами, вы получите затраты на поиск O (log n). Это похоже на данные Chacha102.
См. Этот комментарий в документации, подтверждающей вашу дилемму, что array_rand, в то время как быстрый для небольших массивов, весы очень плохо.
Я изменил fake_array_rand, чтобы всегда возвращать только один элемент, и сделал некоторые тесты против вызова 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]; } ?>
Взгляните на zend/zend_hash.c и zend/zend_hash.h
Я не знаю, c, но для меня это похоже на цепочку хэшей.