SORU
28 ŞUBAT 2010, Pazar


Nasıl bir PHP dizi C düzeyinde uygulanır?

PHP array PHP temel özelliklerinden biridir. Seyrek, aynı dizideki multi-daktilo tuşları sağlar ve set, sözlük, dizi, yığın/ve işlevsellik sıra yinelemeli destekler.

Ama bir süre için şimdi PHP ile çalıştıktan sonra, array_* fonksiyonları çok sayıda ilk bakışta düşündüğünüzden çok daha yavaş olduklarını gördüm. Çok büyük bir dizi (10000) array_rand örneğinde olduğu gibi. array_rand endeksli bir dizi olarak php dizi kullanarak durumlarda, rand( 0, array_length( $array ) - 1 ) gibi bir fonksiyonu array_rand den ÇOK daha hızlı çalışır ki aslında o kadar da yavaş.

Şimdi benim sorum üzerine.

Nasıl bir PHP dizi C düzeyinde uygulanır?Bu çok farklı işlevi PHP dizi veri türü kullanan bir işlevi Büyük O tahmin etmek için çok yararlı olacaktır.

CEVAP
28 ŞUBAT 2010, Pazar


Tekrar tekrar okuduktan sonra/zend_hash çalışabilir.h ve ext/standard/dizi.c bence cevabı (Chris Teşekkür ederim ve önerileriniz için bamya) buldum.

PHP dizi int ve string anahtarları için izin veren zincirleme bir karma tablo (anahtar çarpışmalarıyla ilgili arama O(c) ve O(n)) ' dir. 2 farklı karma algoritmalar aynı karma anahtar uzaya iki türlü uygun kullanır. Ayrıca her değer karma saklı değer ve değer sonra saklı (liste bağlı) önce saklı bağlıdır. Ayrıca karma yineledi kadar geçerli öğeyi tutmak için kullanılan geçici bir işaretçi var.

Yakalamak için array_rand işlev olduğu için güvence altına anahtar tamamen rasgele, array_rand çalışması gerekir üzerinde yineleme dizi rand(0, count($array)) kez (O(n)). Bu aralıktaki eksik tuşları yok, garanti yok, çünkü O(c) tablosunda mahsup geçmek için yol yok çünkü.

Bu keşif, normal C dizi özelliklere sahip PHP veri YOK demektir çünkü biraz sorunlu bana olduğu gibi. Şimdi Tamam bu defa olacak, bir karma aramaları nedeniyle en çok daha hızlıdır, ama bu hataları ile array_rand gibi durumlarda gösterir.

Ayrıca beni rahatsız eden başka bir şey array_key_exists in_array uygulama arasındaki fark. array_key_exists kullandığı karma arama (çoğu zaman O(c)) için bir anahtardır dizi in_array doğrusal arama karma (O(n)).

İki aşağıdaki örnekleri göz önünde bulundurun:

in_array sürümü

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

array_key_exists sürümü

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

Süre in_array sürümü görünüyor daha temiz ve daha basit anlamak için, aslında çok yavaş büyük diziler (O(n)), nerede array_key_exists (rağmen rahatsız edici uzun isim) çok hızlı (O(c) veya yakın).

Sonuç: Keşke orada bir transparan olarak çalışabilir karma tablo veri yapısı olacağını ayarlamak durumlarda dizisi kullanılarak oluşturuldu array_push array[] = $value bu izin için Ölçekleme gibi bir C dizi yerine bir bağlı liste.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Rugiagialia

    Rugiagialia

    1 Ocak 2008
  • talkandroid

    talkandroid

    27 Mayıs 2010
  • TomSka

    TomSka

    30 Mayıs 2006