koddla

Yazılımcıları bilgi ile güçlendirir.

Python Veri Türlerinde Arama

n eleman içeren yinelenebilir veriler üzerindeki tüm arama algoritmaları O(n) karmaşıklığına sahiptir. Sadece bisect.bisect_left() gibi özel algoritmalar O(log(n)) karmaşıklığı ile daha hızlı olabilir.

Öğenin varlığını kontrol

Python’daki tüm yerleşik koleksiyonlar, in ifadesini kullanarak öğe üyeliğini kontrol etmenin bir yolunu uygular.

Liste içinde arama 

alist = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
5 in alist   # True
10 in alist  # False

Tuple içinde arama

atuple = ('0', '1', '2', '3', '4')
4 in atuple    # False
'4' in atuple  # True

String içinde arama 

astring = 'i am a string'
'a' in astring   # True
'am' in astring  # True
'I' in astring   # False

Set içinde arama

aset = {(10, 10), (20, 20), (30, 30)}
(10, 10) in aset  # True
10 in aset        # False

Dict içinde arama 

dict biraz özeldir: normal in sadece anahtarları kontrol eder. Eğer değerler içinde arama yapmak istiyorsanız bunu belirtmeniz gerekir. Anahtar-değer çiftlerini aramak istiyorsanız da aynı şey geçerlidir.

adict = {0: 'a', 1: 'b', 2: 'c', 3: 'd'}
1 in adict                 # True   - örtülü olarak anahtarlarda arama yapar
'a' in adict               # False
2 in adict.keys()          # True   - anahtarlarda açıkça arama yapar
'a' in adict.values()      # True   - değerlerde açıkça arama yapar
(0, 'a') in adict.items()  # True   - anahtar/değer çiftlerini açıkça arar 

Stringler için indeks alma str.index str.rindex ve str.find str.rfind

String için de bir dizin yöntemi vardır. Bunun yanında daha gelişmiş seçenekler ve ek olarak str.find metodu da bulunur. Bunların her ikisi için de tersine çevrilmiş metotlarımız da bulunur.

astring = 'Hello on Koddla'
astring.index('o')  # 4
astring.rindex('o') # 10

astring.find('o')   # 4
astring.rfind('o')  # 10

Index/rindex ile find/rfind arasındaki fark, alt dizenin dize içinde bulunamaması durumunda ne olacağıdır:

astring.index('q') # ValueError: substring not found
astring.find('q')  # -1

Bu yöntemlerin tümü bir başlangıç ve bitiş dizinine izin verir:

astring.index('o', 5)    # 6
astring.index('o', 6)    # 6 - başlangıç dahil
astring.index('o', 5, 7) # 6
astring.index('o', 5, 6) #  - son dahil değil

ValueError: substring not found

astring.rindex('o', 10) # 20 
astring.rindex('o', 9) # 20 - yine soldan sağa doğru

astring.rindex('o', 4, 7) # 6

liste ve tuple için index alma list.index tuple.index

liste ve tuple, elemanın konumunu almak için bir index-metoduna sahiptir:

alist = [10, 16, 26, 5, 2, 19, 105, 26]
# listede 16'yı ara
alist.index(16) # 1
alist[1]        # 16

alist.index(15)

ValueError: 15 is not in list

Ancak yalnızca ilk bulunan öğenin konumunu döndürür:

atuple = (10, 16, 26, 5, 2, 19, 105, 26)
atuple.index(26)   # 2
atuple[2]          # 26
atuple[7]          # 26 - yine 26!

Dict içinde bir değer için anahtar arama

Sözlükler sırasız olduğundan, bir değeri veya anahtarı aramak için yerleşik bir yöntem yoktur. Ancak, belirtilen bir değer için anahtarı (veya anahtarları) alan bir fonksiyon oluşturabilirsiniz:

def getKeysForValue(dictionary, value):
    foundkeys = []
    for keys in dictionary:
        if dictionary[key] == value:
            foundkeys.append(key)
    return foundkeys

Bu, eşdeğer bir şekilde list comprehension olarak da yazılabilir:

def getKeysForValueComp(dictionary, value): 
    return [key for key in dictionary if dictionary[key] == value]

Eğer sadece tek bir bulunan anahtarla ilgileniyorsanız:

def getOneKeyForValue(dictionary, value):
    return next(key for key in dictionary if dictionary[key] == value)

İlk iki fonksiyon, belirtilen değere sahip tüm anahtarların bir listesini döndürür:

adict = {'a': 10, 'b': 20, 'c': 10}
getKeysForValue(adict, 10)     # ['c', 'a'] - sıralama rastgele de olabilir ['a', 'c']
getKeysForValueComp(adict, 10) # ['c', 'a']
getKeysForValueComp(adict, 20) # ['b']
getKeysForValueComp(adict, 25) # []

Diğeri yalnızca bir anahtar döndürür:

getOneKeyForValue(adict, 10)   # 'c'  - Koşullara bağlı olarak bu 'a' da olabilir
getOneKeyForValue(adict, 20)   # 'b'

ve değer dict içinde değilse bir StopIteration-Exception yükseltir:

getOneKeyForValue(adict, 25)

StopIteration

Sıralanmış diziler için indeks alma bisect.bisect_left

Sıralanmış diziler daha hızlı arama algoritmaların kullanılmasına olanak tanır: bisect.bisect_left():

import bisect

def index_sorted(sorted_seq, value):
    """x'e tam olarak eşit olan en soldaki değeri bulun veya bir ValueError yükseltin"""
    i = bisect.bisect_left(sorted_seq, value)
    if i != len(sorted_seq) and sorted_seq[i] == value:
        return i
    raise ValueError

alist = [i for i in range(1, 100000, 3)] # 3'er artarak 1'den 100000'e kadar sıralanmış liste
index_sorted(alist, 97285) # 32428
index_sorted(alist, 4)     # 1
index_sorted(alist, 97286)

ValueError

Çok büyük sıralanmış diziler için hız kazancı oldukça yüksek olabilir. İlk arama için yaklaşık 500 kat daha hızlıdır:

%timeit index_sorted(alist, 97285)
# 100000 döngü, Döngü başına 3 µs
%timeit alist.index(97285)
# 1000 döngü, Döngü başına 1,58 ms

Eleman ilklerden biriyse biraz daha yavaş olsa da:

%timeit index_sorted(alist, 4)
# 100000 döngü, Döngü başına 2.98 µs 
%timeit alist.index(4)
# 1000000 döngü, Döngü başına 580 ns 

İç içe dizilerin aranması

Bir tuple listesi gibi iç içe dizilerde arama yapmak, dict’teki değerler için anahtarları aramak gibi bir yaklaşım gerektirir, ancak özelleştirilmiş işlevlere ihtiyaç duyar.

Değer dizide bulunduysa, en dıştaki dizinin dizini:

def outer_index(nested_sequence, value):
    return next(index for index, inner in enumerate(nested_sequence) 
                      for item in inner 
                      if item == value)

alist_of_tuples = [(4, 5, 6), (3, 1, 'a'), (7, 0, 4.3)]
outer_index(alist_of_tuples, 'a')  # 1
outer_index(alist_of_tuples, 4.3)  # 2

veya dış ve iç dizinin indeksi:

def outer_inner_index(nested_sequence, value):
    return next((oindex, iindex) for oindex, inner in enumerate(nested_sequence) 
                                 for iindex, item in enumerate(inner) 
                                 if item == value)

outer_inner_index(alist_of_tuples, 'a') # (1, 2)
alist_of_tuples[1][2]  # 'a'

outer_inner_index(alist_of_tuples, 7)   # (2, 0)
alist_of_tuples[2][0]  # 7

Genel olarak (her zaman değil), aranan değerin ilk tekrarını bulmak için next ve koşullara sahip bir oluşturucu ifade -generator kullanmak en verimli yaklaşımdır.

Özel sınıflarda arama – contains ve iter

Özel sınıflar için in kullanımına izin vermek için sınıf ya sihirli __contains__ yöntemini ya da bu mümkün değilse bir __iter__ yöntemini sağlamalıdır.

Listelerden oluşan bir liste içeren bir sınıfınız olduğunu varsayalım:

class ListList:
    def __init__(self, value):
        self.value = value
        # Hızlı erişim için tüm değerlerin bir kümesini oluşturun
        self.setofvalues = set(item for sublist in self.value for item in sublist)
        
    def __iter__(self):
        print('__iter__ kullanır.')
        # Tüm alt liste elemanları üzerinde bir üreteç
        return (item for sublist in self.value for item in sublist)
        
    def __contains__(self, value):
        print('__contains__ kullanır.')
        # Sadece değerin kümede olup olmadığına bakın
        return value in self.setofvalues
# Set olmadan da contains-check için iter yöntemini kullanabilirsiniz:
# return any(item == value for item in iter(self))

Üyelik testi için in kullanmak mümkündür:

a = ListList([[1,1,1],[0,1,1],[1,5,1]])
10 in a    # False
# Çıktı: __contains__ kullanır.
5 in a     # True
# Çıktı: __contains__ kullanır.

__contains__ yöntemini sildikten sonra bile:

del ListList.__contains__
5 in a     # True
# Çıktı: __iter__ kullanır.

Not: Döngü (for i in a’da olduğu gibi), sınıf bir __contains__ yöntemi uygulasa bile her zaman __iter__ kullanacaktır.

Bir yanıt yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Back to top