Is PHP's Count() Function O(1) or O(N) for Arrays

PHP: What is the complexity [i.e O(1),O(n)] of the function 'count'?

$ time php -r '$a=range(1,1000000); $b=0; for($i=0;$i<10;$i++) $b=count($a);'
real    0m0.458s
$ time php -r '$a=range(1,1000000); $a=array(1); $b=0; for($i=0;$i<10;$i++) $b=count($a);'
real    0m0.457s

Seems pretty O(1) to me.

Tested PHP version: PHP 5.3.3-1ubuntu9.1 with Suhosin-Patch (cli) (built: Oct 15 2010 14:00:18)

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

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.

PHP Count 1 too many on Array as it's 0 based?

How about:

<?php
$alphas = range('a', 'z');

$alphacount = count($alphas);

$a = 0;
for ($i=0;$i<$alphacount;$i++)  {
    $first = $alphas[$a];
    $second = $alphas[$i];
    if ($i >= $alphacount && $a < $alphaminus  ) {
        $i = 0;
        $a ++;
    }
    echo "$first$second<br>";
}

So you don't have to to -1 since you don't like it! :)

And how about:

$alphas = range('a', 'z');
for ($i = 0; $i < count($alphas); $i++) {
    for ($a = 0; $a < count($alphas); $a++) {
        echo "{$alphas[$i]}{$alphas[$a]}\n";
    }
}

Or forget about arrays! This is more fun :)

    array_walk($alphas, function ($a) use ($alphas) {
        array_walk($alphas, function ($b) use ($a) {
            print "$a$b\n";
        });
    });

PHP: count arrays in array

You can use array_key_last() to find the key of the final element in an array before iterating it. This can be applied to any number of array dimensions.

This example will output the text for each node in your example tree and indicate whether that node is the final array element.

function listElements(array $input)
{
    $final = array_key_last($input);
    $n = count($input);
    foreach ($input as $key => $element) {
        echo $element['text'], ($key == $final) ? " last of $n" : '', PHP_EOL;
        if (isset($element['children'])) {
            listElements($element['children']);
        }
    }
}

(This uses the same approach shown in the most recent update of this answer to the proposed duplicate. I'm just showing here how it can still work when applied recursively.)

---

Based on your edit it looks like the $i you're referring to corresponds to recursion depth. You can keep track of that by adding the depth to the function signature and incrementing it in the recursive call. Here is an example using PHP 5.6 syntax with end()/key() rather than array_key_last().

function listElements(array $input, $depth = 0)
{
    end($input);
    $final = key($input);
    $n = count($input);
    foreach ($input as $key => $element) {
        echo $element['text'];
        echo ($key == $final) ? " last of $n," : '';
        echo " depth $depth", PHP_EOL;
        if (isset($element['children'])) {
            listElements($element['children'], $depth + 1);
        }
    }
}

Working example at https://3v4l.org/J9fek

fastest way to determine if array has a length?

Assuming that create_array returns a PHP array, then count is "Just as Fast" - or rather, both operations are O(1) - and does not depend upon the size of the array. This is because arrays store their size internally.

That being said, if create_array returns an arbitrary Countable, then the count may have to do more work, depending upon how the returned object is implemented - imagine if an object implemented as a Single-Linked List was returned; this would require O(n) time to count.

In any case, using empty is more semantically clear and, as shown by a small micro-benchmark by Darragh, performs the same as isset in wall-clock time.

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

Checking for empty arrays: count vs empty

I generally use empty. Im not sure why people would use count really - If the array is large then count takes longer/has more overhead. If you simply need to know whether or not the array is empty then use empty.

count() parameter must be an array or an object that implements countable in laravel

This is my solution:

count(array($variable));

How to determine if an array has any elements or not?

You can use the count() or sizeof() PHP functions:

if (sizeof($result) > 0) {
    echo "array size is greater than zero";
}
else {
    echo "array size is zero";
}

Or you can use:

if (count($result) > 0) {
    echo "array size is greater than zero";
}
else {
    echo "array size is zero";
}

List of Big-O for PHP functions

Since it doesn't seem like anyone has done this before I thought it'd be good idea to have it for reference somewhere. I've gone though and either via benchmark or code-skimming to characterize the array_* functions. I've tried to put the more interesting Big-O near the top. This list is not complete.

Note: All the Big-O where calculated assuming a hash lookup is O(1) even though it's really O(n). The coefficient of the n is so low, the ram overhead of storing a large enough array would hurt you before the characteristics of lookup Big-O would start taking effect. For example the difference between a call to array_key_exists at N=1 and N=1,000,000 is ~50% time increase.

Interesting Points:

1. isset/array_key_exists is much faster than in_array and array_search
2. +(union) is a bit faster than array_merge (and looks nicer). But it does work differently so keep that in mind.
3. shuffle is on the same Big-O tier as array_rand
4. array_pop/array_push is faster than array_shift/array_unshift due to re-index penalty

Lookups:

array_key_exists O(n) but really close to O(1) - this is because of linear polling in collisions, but because the chance of collisions is very small, the coefficient is also very small. I find you treat hash lookups as O(1) to give a more realistic big-O. For example the different between N=1000 and N=100000 is only about 50% slow down.

isset( $array[$index] ) O(n) but really close to O(1) - it uses the same lookup as array_key_exists. Since it's language construct, will cache the lookup if the key is hardcoded, resulting in speed up in cases where the same key is used repeatedly.

in_array O(n) - this is because it does a linear search though the array until it finds the value.

array_search O(n) - it uses the same core function as in_array but returns value.

Queue functions:

array_push O(∑ var_i, for all i)

array_pop O(1)

array_shift O(n) - it has to reindex all the keys

array_unshift O(n + ∑ var_i, for all i) - it has to reindex all the keys

Array Intersection, Union, Subtraction:

array_intersect_key if intersection 100% do O(Max(param_i_size)*∑param_i_count, for all i), if intersection 0% intersect O(∑param_i_size, for all i)

array_intersect if intersection 100% do O(n^2*∑param_i_count, for all i), if intersection 0% intersect O(n^2)

array_intersect_assoc if intersection 100% do O(Max(param_i_size)*∑param_i_count, for all i), if intersection 0% intersect O(∑param_i_size, for all i)

array_diff O(π param_i_size, for all i) - That's product of all the param_sizes

array_diff_key O(∑ param_i_size, for i != 1) - this is because we don't need to iterate over the first array.

array_merge O( ∑ array_i, i != 1 ) - doesn't need to iterate over the first array

+ (union) O(n), where n is size of the 2nd array (ie array_first + array_second) - less overhead than array_merge since it doesn't have to renumber

array_replace O( ∑ array_i, for all i )

Random:

shuffle O(n)

array_rand O(n) - Requires a linear poll.

Obvious Big-O:

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice O(offset + length)

array_slice O(offset + length) or O(n) if length = NULL

array_keys O(n)

array_values O(n)

array_reverse O(n)

array_pad O(pad_size)

array_flip O(n)

array_sum O(n)

array_product O(n)

array_reduce O(n)

array_filter O(n)

array_map O(n)

array_chunk O(n)

array_combine O(n)

I'd like to thank Eureqa for making it easy to find the Big-O of the functions. It's an amazing free program that can find the best fitting function for arbitrary data.

EDIT:

For those who doubt that PHP array lookups are O(N), I've written a benchmark to test that (they are still effectively O(1) for most realistic values).

$tests = 1000000;
$max = 5000001;

for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}

PHP array: count or sizeof?

I would use count() if they are the same, as in my experience it is more common, and therefore will cause less developers reading your code to say "sizeof(), what is that?" and having to consult the documentation.

I think it means sizeof() does not work like it does in C (calculating the size of a datatype). It probably made this mention explicitly because PHP is written in C, and provides a lot of identically named wrappers for C functions (strlen(), printf(), etc)

---

Related Topics