Как массив PHP реализован на уровне C?
PHP array одна из базовых функций PHP. Это редко, позволяет мультивведенные ключи в том же массиве и поддерживает набор, словарь, массив, стек/очередь и повторяющуюся функциональность.
Но после работы с PHP некоторое время теперь, я нашел что довольно многие из array_* функции намного медленнее, чем Вы думали бы на первый взгляд. Как в случае array_rand на очень большом массиве (10000 +). array_rand является столь медленным на самом деле, что в случаях, где Ваше использование php выстраивают как индексный массив, функция как rand( 0, array_length( $array ) - 1 ) выполнения НАМНОГО быстрее, чем array_rand.
Теперь на мой вопрос.
Как массив PHP реализован на уровне C? Это было бы очень полезно для предсказания Большого O функции, которая в большой степени использует другую функциональность типа данных Array 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 НЕТ типа данных, который имел бы нормальные характеристики массива C. В большинстве случаев это нормально, потому что поиск хэшей выполняется намного быстрее, но ошибки проявляются в таких случаях, как array_rand .
Еще меня беспокоила разница между реализацией array_key_exists и in_array . array_key_exists использует поиск по хешу (большую часть времени O (c)), чтобы узнать, находится ли ключ в массиве, в то время как in_array должен выполнять линейный поиск по хешу (O (n) ).
Рассмотрим два примера ниже:
in_array version
$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
//we found a value
}
array_key_exists version
$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) или близко).
В заключение:
Я бы хотел, чтобы в структуре данных zend HashTable был прозрачный флаг, который устанавливался бы в тех случаях, когда массив был создан с использованием array_push или array [ ] = $ value , что позволило бы масштабировать как массив C, а не связанный список.
См. Этот комментарий в документации, подтверждающий вашу дилемму, что array_rand, хотя и работает быстро для небольших массивов, очень плохо масштабируется.
Я модифицировал fake_array_rand, чтобы он всегда возвращал только 1 элемент, и провел несколько тестов против вызова array_rand со вторым параметром, равным 1. Я провел 100 выборок для каждой функции для каждого количества элементов и взял средний результат. Хотя внутренний array_rand работает быстрее для небольшого количества элементов, он очень плохо масштабируется.
1 элемент: 2.0619630813599E-05 сек. для array_rand 8.4352493286133E-05 сек. для fake_array_rand 10 элементов: 2,1675825119019E-05 сек. для array_rand 8.427619934082E-05 сек. для fake_array_rand 100 элементов: 2,9319524765015E-05 сек. для array_rand 8.4599256515503E-05 сек. для fake_array_rand 1000 элементов: 0,0001157283782959 сек. для array_rand 8.5572004318237E-05 сек. для fake_array_rand 10000 элементов: 0,0016669762134552 сек. для array_rand 8.5201263427734E-05 сек. для fake_array_rand 100000 элементов: 0,015599734783173 сек. для array_rand 8.5580348968506E-05 сек. для элементов fake_array_rand 1000000: 0,18011983394623 сек. для array_rand, 8.6690187454224E-05 сек. для fake_array_rand
Взгляните на zend / zend_hash.c и zend / zend_hash.h
Я не знаю c, но для меня это похоже на связанную хеш-таблицу.
Поскольку массивы PHP являются упорядоченными картами (даже при использовании смежных целочисленных индексов) array_rand () , вероятно, придется составляет список ключей для выбора элемента. Я предполагаю, что было бы чрезмерно неэффективно по пространству и времени кэшировать (часто недействительный) список ключей, поэтому каждый вызов будет нести как минимум O (n) стоимость обхода и построения.
Поскольку ваша реализация rand (... length ...) использует преимущества ваших специальных знаний о том, что ключи являются непрерывными целыми числами, вы получите затраты на поиск O (log n). Это похоже на данные Chacha102.