Bir dizi N öğesini aradığınızı ve karşılık gelen anahtarları bulmak için dizi değerlerinde Y Aramaları yaptığınızı düşünün; Ya Y array_search
'u yapabilir ya da bir array_flip
ve Y doğrudan aramaları yapabilirsiniz. İlk yöntem neden ikinci yönteme göre daha yavaştır? İlk yöntemin ikincisinden daha hızlı olduğu bir senaryo var mı? Anahtarların ve değerlerin benzersiz olduğunu farz edebilirsiniz.Dizi_search'in ardışık array_flip ve doğrudan aramadan daha hızlı olduğu bir senaryo var mı?
cevap
Dizi anahtarları karmadır, bu nedenle onlara bakmak, karma işlevini çağırmak ve karma tablosuna dizine eklemeyi gerektirir. Yani array_flip()
, O (N) 'dir ve bir dizi anahtarın O (1) olması, yani Y
aramalarının O (Y) + O (N) olduğunu.
Dizi değerleri karma değil, bu nedenle arama yapmak için doğrusal arama gerekir. Bu O (N), yani Y aramaları O (N * Y).
Aranan değerlerin diziden eşit olarak dağıtıldığı varsayıldığında, ortalama doğrusal arama durumu N/2 öğelerini karşılaştırmalıdır. Yani, array_flip()
, N elemanlarını incelemek zorunda olduğu için, 2 array_search()
çağrısının zamanını almalıdır.
Karma masanın oluşturulmasında ekstra ek yük vardır. Ancak, PHP yazma üzerine yazma kullanır, bu nedenle array_flip()
sırasında anahtarları veya değerleri kopyalamak zorunda kalmaz, bu yüzden çok da kötü değildir. Az sayıda arama için, ilk yöntem daha hızlı olabilir. Koparma noktasını bulmak için kıyaslamak zorundasın.
Hiçbir zaman * tamamen * bir dizi anahtarının neden sabit zaman olduğunu anladım, ama bir dizi değeri ararken doğrusal (her ikisi de yıkanabilir olduğu varsayılarak)? –
@Asad Değerler hashed olmadığından. Konumlara değer vermek için yine başka bir karma yapı eşleme değerine ihtiyacınız olacaktır. – Corbin
Bunu açıklamak için cevabımı güncelledi. – Barmar
- 1. ImageMagick'den daha hızlı bir şey var mı?
- 2. BigQuery'ye doğrudan Cloud Storage'a yüklemekten daha hızlı mı yükleniyor?
- 3. İkili arama, n modern bir CPU'da doğrusal aramadan daha hızlı mı?
- 4. divmod()% ve // operatörlerini kullanmaktan daha mı hızlı?
- 5. Ruby's Dir.glob'a daha hızlı bir alternatif var mı?
- 6. GDI GetPixel() öğesine daha hızlı bir alternatif var mı?
- 7. HttpHandlers'den daha hızlı bir şey?
- 8. eclipse.jdt.core kavanozuna doğrudan bir bağlantı var mı?
- 9. Java'da BufferedImage pikselleri arasında daha hızlı yineleme yöntemi var mı?
- 10. `extend` `+ =` dan daha hızlı mı? python'da
- 11. MATLAB'da bir matrisi rastgele karıştırmanın daha iyi/daha hızlı bir yolu var mı?
- 12. daha hızlı yolu?
- 13. Böyle bir senaryo var multiprocessing.Process
- 14. MongoDB Saklanan JavaScript Prosedürleri daha hızlı mı?
- 15. Youtube API - youtube.com'da aramadan daha kötü sonuçlar
- 16. nümerik verilerden cPickle'den daha hızlı mı?
- 17. AndroidBitmap_xxx işlevlerini kullanmaktan daha hızlı bir video işleme çözümü var mı?
- 18. SELECT sorgusuna daha fazla özgüllük eklemek daha hızlı mı?
- 19. CLucene, java lucene'den daha hızlı mı?
- 20. Yazma, x86'da okunandan daha hızlı mı?
- 21. Bileşenler şablonlara göre daha hızlı mı?
- 22. getattr() dict aramasına karşı daha hızlı mı?
- 23. get_headers'den daha hızlı bir şey()
- 24. Haskell'in nerede olduğu gibi bir şey var mı?
- 25. Daha hızlı tuşlara basmak, pygame
- 26. PowerPoint sunusunda slaytın dizinini almanın doğrudan bir yolu var mı?
- 27. İdris'te `-` `işlevini doğrudan kullanmanın iyi bir yolu var mı?
- 28. "scipy.misc.comb" ad hoc bir binom hesaplamasından daha mı hızlı?
- 29. MSXML'den daha iyi bir IDOMImplementation var mı?
- 30. Android'de BLE için ardışık Karakteristik hızlı ve kararlı yazma nasıl?
Bu ilginç bir soru. Bunu kanıtlayan herhangi bir performans testiniz var mı? Ek olarak, bu kontrolü yaparken katı seçeneği kullanıyor musunuz? –
@Daryl Gill soruyu neden düzenlediniz? Aslında N aramaları ve N aramaları yaptım, şimdi onu orijinal haline geri döndürürsem, tüm bu tartışma geçersiz olacak. – EnJayz
Sadece şunu söylemek istiyorum: 'Anahtarların ve değerlerin benzersiz olduğunu varsayabilirsin: Bu çok önemli: eğer değerler eşsiz değilse,' array_flip' yaparken çeşitli değerler yüzünden bazı öğeleri kaybedersiniz. Aynı tuşta, ikinci olanlar eski olanların üzerine yazacaktır. –