CODEWITHSUNDEEP
phparraysperformance
Dexter
Dexter

Reputation: 3122

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

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

Upvotes: 114

Views: 17992

Answers (3)

Vladislav Rastrusny
Vladislav Rastrusny

Reputation: 29975

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.

Upvotes: 173

mfonda
mfonda

Reputation: 7993

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.

Upvotes: 6

jberg
jberg

Reputation: 4818

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.

Upvotes: 10

Related Questions