Bir süre için şimdi PHP kullanarak sonra tüm PHP fonksiyonları beklendiği kadar hızlı inşa ettiğini fark ettim. Eğer bir sayı asal ise asal önbelleğe alınan bir dizi kullanarak bulan bir fonksiyon altında iki olası uygulamaları göz önünde bulundurun.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $array_of_number => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $array_of_number => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

Bu in_array doğrusal $prime_array büyüdükçe yavaşlar olan doğrusal arama O(n) ile uygulanan olmasıdır. Nerede array_key_exists işlevi uyguladığı bir karma arama O(1) olan değil yavaşlatmak sürece karma tablo alır son derece nüfuslu (bu durumda sadece O(n)).

Şimdiye kadar deneme yanılma yoluyla büyük-Ç fark ettim, ve bazen looking at the source code. Soru şimdi...

Teorik listesi (veya) pratik tüm için büyük O zamanlar PHP fonksiyonlar* var mı?

*ya da en azından ilginç olanları

İçin örnek bulmak çok zor tahmin etmek ne büyük O işlevleri listelenen çünkü mümkün uygulanmasına bağlı bilinmeyen temel veri yapıları PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace () ile dizi girişi), vb.

Gibi görünmüyor beri herkes iyi bir fikir olacağını düşündüm önce bu başvuru için bir yere sahip oldu. Ya da kod-kaymağını kriter üzerinden olsa array_* işlevleri karakterize etmek için gittim. Tepeye yakın daha ilginç Koca-Ey vermeye çalıştım. Bu tam bir liste değildir.

Not: Bütün(n) olmasına rağmen, bir karma arama O olduğunu varsayarak hesaplanan(1) Büyük-Ç. N katsayısı yeterince büyük bir dizi depolama ram yükü araması Koca-Ey özelliklerine etkisini göstermeye başlamadan önce sana zarar verecek kadar düşük. Örneğin=1 ve N=1,000,000 N array_key_exists bir çağrı arasındaki fark ~50% zaman artırmak.

İlginç Bir Nokta:

1. isset/array_key_exists çok daha hızlı in_array array_search daha
2. (Birliği) bir bit array_merge daha hızlı (ve daha hoş görünüyor). Ama unutmayın çok farklı çalışır.
3. shuffle array_rand Büyük-O aynı katta
4. array_pop/array_push yeniden dizin cezası nedeniyle*/array_unshift *17 daha hızlı

Aramalar:

array_key_exists O(n) ama gerçekten kapatmak için O(1) - Bu, çünkü lineer yoklama çarpışmaları, ama çünkü şans çarpışmalar, çok küçük, katsayısı da çok küçük. O kadar karma aramalarını tedavi buluyorum(1) büyük-O. örneğin N arasında farklı=1000 ve N=100000 yalnızca yaklaşık P daha gerçekçi yavaş vermek.

isset( $array[$index] ) O(n) ama gerçekten O(1) yakın - array_key_exists aynı arama kullanır. Bu dil yapısı bu yana, eğer bu anahtar, aynı tuşa tekrar tekrar kullanıldığı durumlarda hızlandırmak sonuçlanan kodlanmış olup arama önbelleğe alır.

in_array O(n) - bu değeri bulana kadar dizi olsa doğrusal bir arama geliyor olması.

array_search O(n) - in_array gibi aynı temel işlevi kullandığı ama değeri döndürür.

Sıra fonksiyonları:

array_push Ç (i aktin var_i,)

array_pop O(1)

array_shift O(n) - tüm anahtarları anda

array_unshift O(n i aktin var_i,) - tüm anahtarları anda

Dizi Kesişim, Birleşim, Çıkarma:

Kavşak array_intersect_key 100% kavşak ve %0(Max(param_i_size) i* ' welcome param_i_count,), ıntersect O (pasif param_i_size, Tek bildiğim O

Kavşak array_intersect 100% 0% O(n^2) kesiştiği O (*şirketimizin param_i_count^2, i, n), kavşak yap

Kavşak array_intersect_assoc 100% kavşak ve %0(Max(param_i_size) i* ' welcome param_i_count,), ıntersect O (pasif param_i_size, Tek bildiğim O

array_diff Ç(π i param_i_size,) - tüm param_sizes ürün

array_diff_key (pasif param_i_size, ben=! Ç 1) - Bu ilk dizi üzerinden yineleme yapmak için ihtiyacımız yok çünkü.

array_merge Ç (pasif array_i, i=! 1 ) - İlk dizi üzerinden yineleme ihtiyacı yok

N 2. dizinin boyutunu (Birliği) O(n), (yani array_first array_second) - yeniden numaralandır için önemi yok, çünkü array_merge daha az yük

array_replace O (i aktin array_i,)

Rastgele:

shuffle O(n)

array_rand O(n) doğrusal bir anket Gerektirir.

Bariz Büyük:

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice Ç(uzunluğu ofset)

array_slice Ç(uzunluğu offset) veya O(n) uzunluğu = NULL

array_keys O(n)

array_values O(n)

array_reverse O(n)

array_pad Ç(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)

Kolay fonksiyonları Big-O bulmak için yapmak için Eureqa teşekkür etmek istiyorum. Bir şaşırtıcıücretsizprogram rasgele veri için en iyi uyan fonksiyonu bulabilirsiniz.

DÜZENLEME:

PHP dizi aramaları şüphe edenler için* *54, bir kriter olduğunu test etmek için yazdım (hala etkili en gerçekçi değerler O(1)).

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