Как массив PHP реализован на уровне C?

Question

PHP array является одной из основных функций PHP. Он редкий, допускает многопечатные ключи в одном и том же массиве и поддерживает набор, словарь, массив, стек / очередь и итеративную функциональность.

Но, поработав некоторое время с PHP, я обнаружил, что довольно много функций array_* работают намного медленнее, чем вы думаете на первый взгляд. Как и в случае array_rand для очень большого массива (10000+). array_rand на самом деле настолько медленный, что в тех случаях, когда вы используете массив php в качестве индексированного массива, такая функция, как rand( 0, array_length( $array ) - 1 ), выполняется НАМНОГО быстрее, чем array_rand.

Теперь на мой вопрос.

Как массив PHP реализован на уровне C? Это было бы очень полезно для прогнозирования Big O функции, которая интенсивно использует различные функциональные возможности типа данных массива PHP.

Answer 1

После прочтения через 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 версия

$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 вместо связанного списка.

Answer 2

PHP ассоциативные массивы на самом деле являются реализацией HashTables .

Внутренне можно создавать числовые или ассоциативные массивы. Если их объединить, это ассоциативный массив.

В числовых массивах это очень похоже на C. У вас есть массив указателей на структуры ZVAL.

Поскольку указатели имеют фиксированную длину (назовем это n), вычисление смещения (x) легко: x * n.

В PHP типы являются структурами ZVAL (потому что таким образом реализуются динамические типы), но это также помогает в ассоциативном массиве, потому что вы можете использовать фиксированную длину. Таким образом, даже если прямой доступ к массиву медленнее, он все равно считается O (1).

Так что же происходит со строковыми ключами? PHP использует хеш-функцию для преобразования их в целые числа.

Поиск в числовом и ассоциативном массиве имеет аналогичную эффективность, поскольку внутренне все они являются числовыми.

Из-за дополнительного уровня (хэш-функции) медленнее только прямой доступ к ключам массива.

Answer 3

Поскольку PHP-массивы являются упорядоченными картами (даже при использовании смежных целочисленных индексов), array_rand(), вероятно, должен составлять список ключей для выбора элемента. Я предполагаю, что было бы непозволительно неэффективно использовать пространство и время для кэширования списка (часто недействительных) ключей, поэтому каждый вызов будет стоить как минимум O (n) обхода и затрат на создание.

Поскольку ваша реализация rand(... length ...) использует ваши специальные знания о том, что ключи являются непрерывными целыми числами, вы получите O (log n) затрат на поиск. Это похоже на данные Chacha102.

Answer 4

Взгляните на zend/zend_hash.c и zend/zend_hash.h

Я не знаю c, но для меня это похоже на цепочку хеш-таблиц.

Answer 5

См. Этот комментарий в документации, подтверждающий вашу дилемму, что 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]; 
} 
?>

http://us.php.net/manual/en/function.array-rand.php#22360