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.