PHP ilişkisel diziler HashTables aslında uygulanması bulunmaktadır.

Zend / zend_hash.h ve ext / standart / array.c üzerinde okuduktan sonra ben cevabı (Teşekkür Chris ve önerileriniz için bamya) bulduk düşünüyorum.

PHP dizi int ve string anahtarlarının sağlar (anahtar çarpışmalar O arama (c) ve O (n)) zincirleme bir karma tablo. Bu aynı karma anahtar uzaya iki türlü uygun 2 farklı karma algoritmalar kullanır. Ayrıca karma depolanan her bir değer daha önce depolanan değeri ve (bağlantılı liste) sonra depolanan değeri ile bağlantılıdır. Ayrıca, karma iterated nedenle mevcut öğeyi tutmak için kullanılan geçici bir işaretçi yer alır.

array_rand fonksiyonu için yakalama sağlamak için bu anahtar gerçekten rastgele olduğunu, array_rand function rand(0, count($array)) kere dizinin üzerinde yineleme gerekir (O ​​(n )). Aralığında eksik anahtarları olmadığı hiçbir garantisi yoktur çünkü O'da karma tablo ofset (c) zaman taşımak için hiçbir yolu yoktur, çünkü bu.

Normal C dizi özelliklere sahip PHP NO veri türü var demektir çünkü bu keşif biraz, beni rahatsız etti. Şimdi karma aramalarını çok daha hızlı çünkü bu çoğu zaman, Tamam, ama bu faylar array_rand gibi durumlarda aracılığıyla göstermek.

Ayrıca beni rahatsız başka bir şey array_key_exists ve in_array uygulanması arasındaki fark oldu. in_array doğrusal karma aramak zorunda iken array_key_exists, karma arama anahtar dizide olup olmadığını görmek için (O (c) çoğu zaman) kullanır (O (n) .)

Aşağıdaki iki örnek düşünün:

in_array versiyon

$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
   //we found a value
}

array_key_exists versiyon

$array = array_fill_keys( range(0, 100000), NULL );
if( array_key_exists( $random_key, $array ) ) {
   //we found a value, err key
}

While the in_array versiyon looks much cleaner and simpler to understand, it's actually very slow on large arrays (O(n)), where array_key_exists (despite is annoyingly long name) is very fast (O(c) or close).

In conclusion: I wish there was a transparent flag in the zend HashTable data-structure that would be set in cases where the array was created using array_push or array[] = $value that would allow for scaling like a C array instead of a linked list.

PHP dizileri beri are ordered maps (bitişik tamsayı endeksleri kullanılarak bile) array_rand() olasılıkla eksilerini bir öğe seçmek için tuşlarının bir listesini sahiptir. Bu yüzden her çağrı en az bir O (n) kastetmek ve inşaat maliyet tabi olacak engelleyici alan ve (sık sık geçersiz) anahtar liste önbelleğe etkisiz zaman olacağını tahmin ediyorum.

Lütfen rand(... length ...) uygulama size tuşları bitişik tamsayılar buna sahip özel bilgi yararlanır, çünkü O (log n) arama maliyetleri alırsınız. Bu Chacha102 verileri ile tutarlı görünüyor.

Hızlı, küçük diziler için, çok kötü terazi ederken, array_rand ikilemi teyit belgelerinde bu açıklamayı görüyor.

Ben hep sadece 1 öğeyi döndürmek için fake_array_rand değiştirilmiş ve 1 olarak ikinci parametre ile array_rand çağrı karşı bazı kriterler yaptım. Ben elemanların her numara için her bir fonksiyon için 100 örnekleri koştu ve ortalama sonuç aldı. Iç array_rand elemanlarının küçük bir sayı için daha hızlı olsa da, çok kötü bir şekilde ölçeklenir.

1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. 
for fake_array_rand 

10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. 
for fake_array_rand 

100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. 
for fake_array_rand 

1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. 
for fake_array_rand 

10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. 
for fake_array_rand 

100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. 
for fake_array_rand 

1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand 

<?php 
function fake_array_rand ($array) 
{ 
        $count = count ($array); 
        # Help keep the number generator random :) 
        $randval and usleep ("0.$randval"); 

        # Seed the random number generator 
        # Generate a random number 
        srand ((double) microtime() * 10000000); 
        $randval = rand(); 

        # Use the random value to 'pick' an entry from the array 
        # Count the number of times that the entry is picked 
        ++$index[$randval % $count]; 

        return $array[$randval % $count]; 
} 
?>

http://us.php.net/manual/en/function.array-rand.php#22360

Zend / zend_hash.c ve zend / zend_hash.h bir göz atın

Ben c bilmiyorum, ama benim için bu bir zincirleme karma tablo gibi görünüyor.