Is PHP's count() function O(1) or O(n) for arrays?

04/19/2020 09:00:01

Does count() really count the all the elements of a PHP array, or is this value cached somewhere and just gets retrieved?

Verified Answer (131 Votes)

04/29/2011 22:42:39

Well, we can look at the source:

/ext/standard/array.c

PHP_FUNCTION(count) calls php_count_recursive(), which in turn calls zend_hash_num_elements() for non-recursive array, which is implemented this way:

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

    return ht->nNumOfElements;
}

So you can see, it's O(1) for $mode = COUNT_NORMAL.

131

Answer #2 (7 Votes)

04/29/2011 22:29:43

In PHP 5+ the length is stored in the array so the counting is not done each time.

EDIT: You also might find this analysis interesting: PHP Count Performance. Although the length of the array is maintained by the array, it still seems as though it is faster to hold on to it if you are going to call count() many times.

7

Answer #3 (3 Votes)

04/29/2011 22:31:38

PHP stores the size of an array internally, but you're still making a function call when which is slower than not making one, so you'll want to store the result in a variable if you're doing something like using it in a loop:

For example,

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

Additionally, you can't always be sure count is being called on an array. If it's called on an object that implements Countable for example, the count method of that object will be called.

3
3
Hack Hex uses Stack Exchance API by the Stack Exchange Inc. to scrape questions/answers under Creative Commons license.