Поиск элементов в коллекциях

Введение

Примеры

  • Получение индекса для строк: 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__ метод.

Синтаксис

Параметры

Примечания