In: Genel


[*]

2022-02-15, Yorumlar

Sıralanmış ve döndürülmüş farklı öğelerden oluşan bir listeniz olduğunu varsayalım. Bu listedeki bir öğeyi nasıl ararsınız?

Örneğin, liste:

[7, 11, 13, 19, 2, 3, 5]

sıralanır (sırasıyla ilk 7 asal sayı) ve döndürülür (7’yi ilk sıraya koymak için).

Girdi olarak bu liste ile, o zaman:

  • yukarı Bak 13 İadeler 2 dan beri 13 dizinde 2
  • yukarı Bak 2 İadeler 4
  • yukarı Bak 4 sentinel değerini döndürür -1

Açık teknik, sadece listeyi aramaktır:

def lookup(values, v):
    try:
        return values.index(v)
    except IndexError:
        return -1

Bu, tüm listeyi işleyen doğrusal bir algoritmadır. Sıralanmış + döndürülmüşlüğünden yararlanmanın bir yolu var mı?

eğer liste oldu sıralanırsa, logaritmik bir arama için ikili arama uygulayabiliriz. Ve aslında, özel bir sipariş uygulayarak liste dır-dir sıralanmış.

Python’da özel bir siparişi nasıl uygulayabiliriz?

Python geliştikçe bunu yapmanın yolu değişti. Aşağıdaki tablo, sıralayan ve karşılaştıran standart Python işlevlerinin gelişimini göstermektedir.

Sürüm Yıl Fonksiyonlar Notlar
2.0 2000 max, min, list.sort([cmp]), bisect.bisect Dikkat [cmp] sıralama sürecini önemli ölçüde yavaşlatır
2.3 2003 yığınq Öncelik sırası algoritması olarak da bilinir
2.4 2004 sıralanmış (yinelenebilir[, cmp[, key[, reverse]]]), list.sort([cmp[, key[, reverse]]]), itertools.groupby(yinelenebilir[, key) In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function
2.4 2004 heapq.nlargest, heapq.nsmallest Heapq extended
2.5 2006 max([key]), dk([key]), heapq.nlargest(…[, key]), heapq.smallest(…[, key])
2.6 2008 heapq.merge Heapq tekrar uzatıldı
3.0 2008 sıralı (yinelenebilir, anahtar[, reverse]), list.sort(anahtar[, reverse]) Daha fazla yok cmp
3.5 2015 heapq.merge(…, anahtar)
3.10 2021 bisect.bisect(…, anahtar) vb Bu düşük seviyeyi bırakır heapq fonksiyonlar

Python’un en eski sürümleri, listeleri sıralamanıza izin verdi ve sıralama, bir cmp işlev – belgeler uyarılmış olsa da, bir performans cezası olacağı[*]. yerleşik min ve max
işlevler özelleştirilemez ve karşılaştırmada kullanılan karşılaştırma yapılamaz. bisect modül – Python’un ikili arama uygulamasıdır.

2.3’te heapq modül göründü, ancak bisectyığın öğelerinin sırasını özelleştirmenin bir yolu yoktu.

2.4 tanıtıldı key sıralamayı özelleştirme argümanı, bunun tercih edilmesi gerektiğine dikkat ederek cmp. Farklı cmp iki öğeyi karşılaştıran, key tek bir öğe alır ve o öğe için bir sıralama sırası döndürür. bu key yanına argüman eklendi cmp içinde list.sort ve yeni sorted
yerleşik işlev; ve key gruplandırmayı özelleştirmenin tek yoluydu
itertools.groupby.

2.5 eklendi key ile min ve maxve ayrıca heapq.nlargest, heapq.nsmallest. Bunlara rağmen heapq işlevler şimdi bir kabul keyalt düzey yığın işlevleri yığınlaştırma, itme, açma ve değiştirme işlevi görmez.

2.6 tanıtıldı heapq.mergebir yığın kullanarak sıralanmış girdileri birleştirmek için kullanışlı bir işlevdir, ancak bir sıralama anahtarı belirtme seçeneği yoktur.

3.0 kurtuldu cmpyapımı key sıralamayı özelleştirmenin tek yolu. Python 2’den 3’e geçiş yapmak için cmp fonksiyonların dönüştürülmesi gerekiyor key fonksiyonlar. Python 2.5’te olduğu gibi, 3.0’da bir anahtar uygulayabilirsiniz. list.sort, sorted, min, max,
itertools.groupby, heapq.nlargest, heapq.nsmallest – ama değil
bisect veya diğeri heapq fonksiyonlar.

3.5 eklendi key ile heapq.mergeile hizalayarak heapq.nlargest
ve heapq.nsmallestancak alt düzey yığın işlevleriyle bir sıralama anahtarı kullanmak imkansız kaldı.

Bir sonraki değişiklik 3.10’da geldi. key parametre eklendi bisect modül. Söyleyebileceğim kadarıyla, standart Python’un, siparişi tamamen özelleştirmenize izin vermeyen tek parçası, heapq modül.

Arama tuşuyla ikiye böl

Bu nedenle, orijinal bulmacaya geri dönmek için, örnek sıralı+döndürülmüş listemizi düşünün:

>>> values = [7, 11, 13, 19, 2, 3, 5]

İlk dört eleman, ilk elemana 7’den büyük veya ona eşittir, son üç eleman 7’den küçüktür.

>>> [v < values[0] for v in values]
[False, False, False, False, True, True, True]

Dan beri False < True Yukarıdaki liste kavrayışının sonucu sıralanır. Bu fikri genişleterek, aşağıdaki anlama da sıralanır.

>>> [(v < values[0], v) for v in values]
[(False, 7), (False, 11), (False, 13), (False, 19), (True, 2), (True, 3), (True, 5)]

Şimdi ikili aramayı kullanarak logaritmik bir aramamız var:

from bisect import bisect_left

def lookup(values, v):
    key = lambda x: (x < values[0], x)
    i = bisect_left(values, key(v), key=key)
    return i if (i < len(values) and values[i] == v) else -1

v’yi arama, anahtarını ara

Değerini anlayınca şaşırdım v aranmak, sahip olmak zorunda key
uygulanan fonksiyon önceki arama bisect_left. Yani, nerede olduğunu bulmak için v
içeri girmeli values sıralama düzenini korumak için key(v) ile bisect_left. Bu, diğer dillerdeki ikili arama arayüzüyle eşleşmiyor. Ayrıca örneğimizde boş listeleri özel bir durum olarak ele almamız gerektiği anlamına gelir.

def lookup(values, v):
    if not values: return -1
    key = lambda x: (x < values[0], x)
    i = bisect_left(values, key(v), key=key)
    return i if (i < len(values) and values[i] == v) else -1

[*] Tür tanıtımından önce keystandart model
süslemek-sıralamak-süslemek.

[*]

Bir cevap yazın

Ready to Grow Your Business?

We Serve our Clients’ Best Interests with the Best Marketing Solutions. Find out More

How Can We Help You?

Need to bounce off ideas for an upcoming project or digital campaign? Looking to transform your business with the implementation of full potential digital marketing?

For any career inquiries, please visit our careers page here.
[contact-form-7 404 "Bulunamadı"]