Ben bir yere başvurmak için olması iyi bir fikir olacağını düşündüm önce kimse bu yapmış gibi görünmüyor çünkü. Ben array_* işlevleri tanımlamak için rağmen gitti ve ya kriter veya kod süzme yoluyla ettik. Ben en yakın daha ilginç Big-O koymak denedim. Bu liste tam değildir.

Not: Bir karma arama gerçekten O (n) olsa bile (1) O olduğu varsayılarak hesaplanan All Big-O. N katsayısı arama Big-O özellikleri etkisini alarak başlamak istiyorum önce yeterince büyük bir dizi depolama koç havai size zarar vereceğini, bu yüzden düşüktür. Örneğin array_key_exists-N at = 1 ve N = 1,000,000 bir çağrı arasındaki fark ~% 50 saat artıştır.

Interesting Points:

1. isset / array_key_exists çok in_array daha hızlı ve array_search olduğu
2. + (sendika) array_merge biraz daha hızlı (ve daha güzel görünüyor). Ama o kadar akılda tutmak farklı çalışır.
3. shuffle array_rand ile aynı Big-O katmanlı verildi
4. array_pop / array_push yeniden göstergesi alınmaz için array_shift / array_unshift nedeniyle daha hızlı

Lookups:

array_key_exists O (n) ama O gerçekten yakın (1) - bu, çünkü çarpışmalar doğrusal yoklama, ancak çarpışma şansı çok küçük olduğu için, katsayı da çok azdır. I O (1), daha gerçekçi, büyük-O vermek gibi karma aramalarını tedavi bulmak. Örneğin N = 1000 ve N = 100000 arasındaki farklı sadece yaklaşık% 50 yavaş aşağı.

isset( $array[$index] ) O (n) ama O gerçekten yakın (1) - bu array_key_exists gibi aynı arama kullanır. Anahtar kodlanmış ise o dil yapı yana, aynı anahtar tekrar tekrar kullanıldığı durumlarda hız yukarı çıkan, arama önbelleğe alır.

in_array O (n) - bu değerini bulana kadar dizide olsa bir doğrusal arama yapar çünkü bu.

array_search O (n) - bu İn_Array'in gibi aynı temel işlevi kullanır ama değerini döndürür.

Queue functions:

array_push O (Σ var_i, tüm i için)

array_pop O (1)

array_shift O (n) - tüm tuşları reindex var

(Tüm i için n + Σ var_i) array_unshift O - tüm tuşları reindex var

Array Intersection, Union, Subtraction:

array_intersect_key if kavşak% 100 do O (Max (param_i_size) * Σparam_i_count, tüm i için), kesişme 0% kesişir eğer O (Σparam_i_size, tüm i için)

array_intersect kesişme 100% O do if (n ^ 2 * Σparam_i_count, tüm i için), kesişme% 0 O kesişir (n ^ 2) ise

array_intersect_assoc if kavşak% 100 do O (Max (param_i_size) * Σparam_i_count, tüm i için), kesişme 0% kesişir eğer O (Σparam_i_size, tüm i için)

array_diff O (π param_i_size, tüm i için) - Hepsi param_sizes ürün bulunuyor

array_diff_key O (Σ param_i_size, i = 1!) - Biz ilk dizinin üzerinde yineleme gerek yok çünkü bu.

array_merge O (Σ array_i, i = 1!) - İlk dizinin üzerinde yineleme gerekmez

Bu yeniden numaralandırmak zorunda olmadığından array_merge daha az yük - n 2 dizinin boyutu (yani array_first + array_second) olan + (sendika) O (n),

array_replace O (Σ array_i, tüm i için)

Random:

shuffle O (n)

array_rand O (n) - doğrusal bir anket gerektirir.

Obvious Big-O:

array_fill O (n)

array_fill_keys O (n)

range O (n)

array_splice O (+ uzunluğu ofset)

array_slice O (+ uzunluğu ofset) ya da O (n) ise uzunluğu = 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)

Ben kolay fonksiyonları Big-O bulmak için yapmak için Eureqa teşekkür etmek istiyorum. Bu keyfi veri için en uygun işlevini bulabilirsiniz inanılmaz free program.

EDIT:

PHP dizi aramalarını O(N) olduğuna şüphe olanlar için, ben (en çok gerçekçi değerler için hala etkili O(1) olan) olduğunu test etmek için bir kriter yazdım.

$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 );
}

Özellikle tarif durumda açıklama ilişkisel diziler karma tablo olarak uygulanan olmasıdır - böylece anahtarla arama (ve buna, array_key_exists) O (1) 'dir. Ancak, diziler değeriyle endeksli, yani bir değer dizide olup olmadığını keşfetmek için genel durumda tek yol doğrusal bir arama motorudur değildir. Hiçbir sürpriz yok.

PHP yöntemleri algoritmik karmaşıklığı özel kapsamlı belgeler var sanmıyorum. Bu çaba gerektirecek yeterince büyük bir endişe Ancak, eğer, her zaman the source code bakabilirsiniz.

Hemen hemen her zaman yerine array_key_exists in isset kullanmak istiyorum. Ben internals bakmıyorum, ama isset çalışır ederken, dizinin her tuşu üzerinde dolaşır, çünkü array_key_exists O (N) olduğundan eminim Bir dizi indeksi erişirken kullanılan aynı hash algoritmasını kullanarak bir öğesine erişmek. O O olması gerekir (1).

Için dikkat edilmesi gereken biri "yakaladım" şudur:

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

Ben bu yüzden fark benchmarked, meraklı:

<?php

$bigArray = range(1,100000);

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    isset($bigArray[50000]);
}

echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    array_key_exists(50000, $bigArray);
}

echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>

is_set: 0.132308959961 seconds
array_key_exists: 2.33202195168 seconds

Tabii ki, bu zaman karmaşıklığı görünmüyor, ancak 2 işlevleri birbirleriyle karşılaştırmak nasıl göstermektedir.

, Zaman karmaşıklığı test ilk tuşu ve son tuşa bu işlevlerden birini çalıştırmak için gereken süreyi karşılaştırmak.

Eğer kullanırsanız, muhtemelen "gerçek" O (1) dizi arama sahip olacaktır SPLFixedArray