Поиск элементов в коллекциях и последовательностях
Получение индекса для строк: str.index (), str.rindex() и str.find(), str.rfind()
String также имеет index метод , но и более продвинутые варианты и дополнительное str.find.Для обоих из них есть дополнительный обратный метод.
astring = 'Hello on StackOverflow'
astring.index('o') # 4
astring.rindex('o') # 20
astring.find('o') # 4
astring.rfind('o') # 20
Разница между index / rindex и find / rfind это то , что происходит , если подстрока не найдена в строке:
astring.index('q') # ValueError: substring not found
astring.find('q') # -1
Все эти методы позволяют начальный и конечный индексы:
astring.index('o', 5) # 6
astring.index('o', 6) # 6 - start is inclusive
astring.index('o', 5, 7) # 6
astring.index('o', 5, 6) # - end is not inclusive
ValueError: подстрока не найдена
astring.rindex('o', 20) # 20
astring.rindex('o', 19) # 20 - still from left to right
astring.rindex('o', 4, 7) # 6 В поисках элемента
Все встроенные в коллекции в Python реализовать способ проверить членство элемента с использованием in. Список
alist = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
5 in alist # True
10 in alist # False
Кортеж
atuple =('0', '1', '2', '3', '4')
4 in atuple # False
'4' in atuple # True
строка
astring = 'i am a string'
'a' in astring # True
'am' in astring # True
'I' in astring # False
Задавать
aset = {(10, 10), (20, 20), (30, 30)}
(10, 10) in aset # True
10 in aset # False
Dict
dict немного особенный: нормальный in проверяет только ключи. Если вы хотите , чтобы искать в значении , которые необходимо указать. То же самое , если вы хотите найти пар ключ-значение.
adict = {0: 'a', 1: 'b', 2: 'c', 3: 'd'}
1 in adict # True - implicitly searches in keys
'a' in adict # False
2 in adict.keys() # True - explicitly searches in keys
'a' in adict.values() # True - explicitly searches in values
(0, 'a') in adict.items() # True - explicitly searches key/value pairs Получение списка индексов и кортежей: list.index(), tuple.index()
list и tuple имеют index -метода получить позицию элемента:
alist = [10, 16, 26, 5, 2, 19, 105, 26]
# search for 16 in the list
alist.index(16) # 1
alist[1] # 16
alist.index(15)
Ошибка значения: 15 отсутствует в списке
Но возвращает только позицию первого найденного элемента:
atuple = (10, 16, 26, 5, 2, 19, 105, 26)
atuple.index(26) # 2
atuple[2] # 26
atuple[7] # 26 - is also 26! Поиск ключа(ей) по значению в dict
dict не имеет встроенный метода для поиска значения или ключа , потому что словари являются упорядоченными. Вы можете создать функцию, которая получает ключ (или ключи) для указанного значения:
def getKeysForValue(dictionary, value):
foundkeys = []
for keys in dictionary:
if dictionary[key] == value:
foundkeys.append(key)
return foundkeys
Это также может быть записано как эквивалентное понимание списка:
def getKeysForValueComp(dictionary, value):
return [key for key in dictionary if dictionary[key] == value]
Если вам нужен только один найденный ключ:
def getOneKeyForValue(dictionary, value):
return next(key for key in dictionary if dictionary[key] == value)
Первые две функции возвращает list всех keys , которые имеют определенное значение:
adict = {'a': 10, 'b': 20, 'c': 10}
getKeysForValue(adict, 10) # ['c', 'a'] - order is random could as well be ['a', 'c']
getKeysForValueComp(adict, 10) # ['c', 'a'] - dito
getKeysForValueComp(adict, 20) # ['b']
getKeysForValueComp(adict, 25) # []
Другой вернет только один ключ:
getOneKeyForValue(adict, 10) # 'c' - depending on the circumstances this could also be 'a'
getOneKeyForValue(adict, 20) # 'b'
и поднять StopIteration - Exception , если значение не в dict :
getOneKeyForValue(adict, 25)
StopIteration
Получение индекса для отсортированных последовательностей: bisect.bisect_left()
Отсортированные последовательности позволяют использовать более быстрый поиск алгоритмов: bisect.bisect_left() [1]:
import bisect
def index_sorted(sorted_seq, value):
"""Locate the leftmost value exactly equal to x or raise a ValueError"""
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)] # Sorted list from 1 to 100000 with step 3
index_sorted(alist, 97285) # 32428
index_sorted(alist, 4) # 1
index_sorted(alist, 97286)
ValueError
Для очень больших отсортированных последовательностей выигрыш в скорости может быть достаточно высоким. В случае первого поиска примерно в 500 раз быстрее:
%timeit index_sorted(alist, 97285)
# 100000 loops, best of 3: 3 µs per loop
%timeit alist.index(97285)
# 1000 loops, best of 3: 1.58 ms per loop
Хотя это немного медленнее, если элемент является одним из самых первых:
%timeit index_sorted(alist, 4)
# 100000 loops, best of 3: 2.98 µs per loop
%timeit alist.index(4)
# 1000000 loops, best of 3: 580 ns per loop
Поиск вложенных последовательностей
Поиск во вложенных последовательностях , как в list из tuple требует такого подхода , как поиск ключей для значений в dict , но нуждается в пользовательских функциях.
Индекс самой внешней последовательности, если значение было найдено в последовательности:
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
или индекс внешней и внутренней последовательности:
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
В общем случае (не всегда) с помощью next и выражения генератора с условиями , чтобы найти первое вхождение искомого значения является наиболее эффективным подходом.
Поиск в пользовательских классах: __contains__ и __iter__
Для того, чтобы разрешить использование in пользовательских классах класса должен либо предоставить магический метод __contains__ или, если это невозможно, в __iter__ -метод.
Предположим , у вас есть класс , содержащий list из list s:
class ListList:
def __init__(self, value):
self.value = value
# Create a set of all values for fast access
self.setofvalues = set(item for sublist in self.value for item in sublist)
def __iter__(self):
print('Using __iter__.')
# A generator over all sublist elements
return (item for sublist in self.value for item in sublist)
def __contains__(self, value):
print('Using __contains__.')
# Just lookup if the value is in the set
return value in self.setofvalues
# Even without the set you could use the iter method for the contains-check:
# return any(item == value for item in iter(self))
Использование тестирования членства возможно при использовании in :
a = ListList([[1,1,1],[0,1,1],[1,5,1]])
10 in a # False
# Prints: Using __contains__.
5 in a # True
# Prints: Using __contains__.
даже после удаления __contains__ метода:
del ListList.__contains__
5 in a # True
# Prints: Using __iter__.
Примечание: зацикливание in (как for i in a ) всегда будет использовать __iter__ даже если класс реализует __contains__ метод.