Verimliliği

Question

Zaten örneğin, sıralanabilir ve anahtar kelimedeki kullanmak bir liste varsa:

a = [1,2,5,6,8,9,10] 
print 8 in a 

Bu sıralı bir arama yapmak ama yapamıyor gerektiğini düşünüyorum İkili arama yaparak daha hızlı mı yapıyorum? Sıralı bir listede arama yapmak için pythonik bir yol var mı?

Answer 1

Standart kitaplıkta, bisect modülünde Python için ikili bir arama var. olduğu gibi in/contains desteklemez, ama bunu işlemek için küçük bir fonksiyon yazabiliriz: bisect olduğu gibi,

from bisect import bisect_left 
def contains(a, x): 
    """returns true if sorted sequence `a` contains `x`""" 
    i = bisect_left(a, x) 
    return i != len(a) and a[i] == x 

Sonra

>>> contains([1,2,3], 3) 
True 
>>> contains([1,2,3], 4) 
False 

Bu olsa çok hızlı olacak değil Python'da yazılan ve C ile yazılmadığınız için, büyük olasılıkla çok sayıda örnek için ardışık in daha hızlı bulabilirsiniz. Python 2.4'ten beribisect, CPython'da isteğe bağlı bir C hızlandırma gerçekleştirmiştir.

CPython'daki kesin kırılma noktasını zamanlamak zordur. Bunun nedeni, kodun C ile yazılmasıdır; Eğer büyük veya sırayla herhangi değerinden düşük olduğunda bir değer için kontrol ederseniz, o zaman CPU dallanma tahmini sana oyun oynayacak ve elde edersiniz: Burada

In [2]: a = list(range(100)) 
In [3]: %timeit contains(a, 101) 
The slowest run took 8.09 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 370 ns per loop 

, 3 iyi temsil etmeyen Algoritmanın çalışma süresi doğru.

Ancak ince ayar testleri, 30 öğeden azına sahip listeler için, ikileme işleminin in'dan daha hızlı olabileceği sonucuna ulaştım.Gerçekten birçok in işlemleri yapıyorsanız

---

Ancak, bir set kullanmak gerektiğini; Öte yandan

>>> a = [10, 6, 8, 1, 2, 5, 9] 
>>> a_set = set(a) 
>>> 10 in a_set 
True 

, bir liste sıralama: Hiç olacağını bir kümesi haline kez listeyi dönüştürebilir (hatta sıralanabilir etmez) ve in operasyonu herhangi bir ikili arama daha asimptotik hızlı olacaktır büyük bir set oluşturmaktan çok zaman-karmaşıklığı vardır, bu yüzden çoğu zaman bir set gitmek için yol olacaktır.

Answer 2

Standart kitaplık sıralanmış sıralarda arama yapmayı destekleyen bisect modülüne sahiptir.

Ancak, küçük listeler için, in operatörünün arkasındaki C uygulamasının bisect'u geçeceğine bahse girerim. Sen ... Hedef donanım üzerinde gerçek başabaş noktası belirlemek için yaygın vakalarda bir demet

---

Bu kayda değer olduğunu (bir sırasız iterable paçayı eğer yani ölçmek zorundayız set), daha sonra O(N) olan bir sırayla O(logN) ve in işlecindeki bir işleç ile karşılaştırıldığında, O(1) zamanında (in işlecini kullanarak) arama yapabilirsiniz. Ve, bir set ile de ilk etapta sıralama maliyeti kaçının :-).