Является ли функция PHP count () O (1) или O (n) для массивов?

96

count()Действительно ли подсчитываются все элементы массива PHP, или это значение где-то кэшируется и просто извлекается?

php arrays performance Декстер
источник
6
Почему бы не проверить это? достаточно просто создать цикл, который добавляет элементы в массив и каждый раз считает и выполняет определенное время.
Marc B
3
Взгляните на этот вопрос: stackoverflow.com/questions/2473989/…
Разработчик Pixel
Ключевые слова Google - этот вопрос также можно сформулировать так: выполняет ли PHP count () итерацию по массиву или извлекает счет из свойства массива?
jave.web 01

Ответы:

136

Что ж, можем посмотреть исходник:

/ext/standard/array.c

PHP_FUNCTION(count)вызовы php_count_recursive(), которые, в свою очередь, вызывают zend_hash_num_elements()нерекурсивный массив, который реализован следующим образом:

ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
    IS_CONSISTENT(ht);

    return ht->nNumOfElements;
}

Как видите, это O(1)для $mode = COUNT_NORMAL.

Владислав Раструсный
источник
6
Что же IS_CONSISTENT(ht)делать?
Мэтью
1
Спасибо! Я не совсем понимал, где в исходном тексте мне искать или где его взять (без необходимости проверять его из репозитория).
Декстер
3
@Matt Он проверяет правильность хеш-структуры, как я вижу. Он определен в zend_hash.c, а также O (1).
Владислав Раструсный
10
Нельзя пропустить, чтобы проголосовать за того, кто ищет ответ в исходном коде PHP :)
Лами
1
@Matt IS_CONSISTENT () - это просто проверка работоспособности массива github.com/php/php-src/blob/PHP-5.3/Zend/zend_hash.c#L51
Джон Картер
7

В PHP 5+ длина хранится в массиве, поэтому подсчет не выполняется каждый раз.

РЕДАКТИРОВАТЬ: Вам также может показаться интересным этот анализ: Производительность подсчета PHP . Хотя длина массива поддерживается массивом, все же кажется, что быстрее удержать его, если вы собираетесь вызывать count()много раз.

Jberg
источник
Думаю, вы правы, что изменение было внесено, начиная с PHP 5. Однако я еще не нашел доказательства того, что PHP 4 был O (n) для count (); Я просто вижу анекдотические комментарии. Сможете ли вы найти доказательства (например, реализацию count () для PHP 4)? Спасибо,
Кристофер Виндзор
3

PHP хранит размер массива внутри, но вы все равно вызываете функцию, когда это медленнее, чем ее не делать, поэтому вы захотите сохранить результат в переменной, если вы делаете что-то вроде использования ее в цикл:

Например,

$cnt = count($array);
for ($i =0; $i < $cnt; $i++) {
   foo($array[$i]);
}

Кроме того, вы не всегда можете быть уверены, что countвызывается массив. Если он вызывается для объекта, который, Countableнапример, реализует , countбудет вызван метод этого объекта.

Мфонда
источник
В качестве продолжения вы можете прочитать josephscott.org/archives/2010/01/php-count-performance Он в основном подробно описывает, как получить длину массива o (1) и влияние повторных вызовов функций.
TheClair
1
всегда ли выполнение вызова функции медленнее, чем его отсутствие? Я не удивлюсь, если у интерпретатора есть встроенная оптимизация.
corsiKa
1
the count method of that object will be called, не могли бы вы объяснить это немного
Steel Brain
1
@SteelBrain, если класс реализует Countableинтерфейс, то вызов count($object)- это то же самое, что и вызов $object->count(). См., Например, 3v4l.org/oYSSC .
mfonda 05
you're still making a function call when which is slower than not making oneЭто утверждение может быть неверным. Если вы выполняете обход вручную, это O(n)операция. Но если вы просто хотите получить предварительно рассчитанное значение, тогда операция O(1).
Джамшад Ахмад,