Suche…


Bemerkungen

Alle Suchalgorithmen auf iterierbaren Elementen, die n Elemente enthalten, weisen eine O(n) -Komplexität auf. Nur spezialisierte Algorithmen wie bisect.bisect_left() können mit O(log(n)) bisect.bisect_left() schneller sein.

Den Index für Strings abrufen: str.index (), str.rindex () und str.find (), str.rfind ()

String auch eine index , aber auch erweiterte Optionen und die zusätzliche str.find . Für beide gibt es eine komplementäre umgekehrte Methode.

astring = 'Hello on StackOverflow'
astring.index('o')  # 4
astring.rindex('o') # 20

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

Der Unterschied zwischen index / rindex und find / rfind besteht darin, was passiert, wenn die Teilzeichenfolge nicht in der Zeichenfolge gefunden wird:

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

Alle diese Methoden ermöglichen einen Start- und Endindex:

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: Unterzeichenfolge nicht gefunden

astring.rindex('o', 20) # 20 
astring.rindex('o', 19) # 20 - still from left to right

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

Nach einem Element suchen

Alle integrierten Sammlungen in Python implementieren eine Art und Weise Element Mitgliedschaft zu überprüfen Verwendung in .

Liste

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

Tupel

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

String

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

einstellen

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

Dikt

dict ist etwas Besonderes: die normalen in nur die Schlüssel überprüft. Wenn Sie nach Werten suchen möchten, müssen Sie diese angeben. Dasselbe, wenn Sie nach Schlüsselwertpaaren suchen möchten.

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

Abrufen der Indexliste und der Tupel: list.index (), tuple.index ()

list und tuple haben eine index Methode, um die Position des Elements zu ermitteln:

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)

ValueError: 15 ist nicht in der Liste

Gibt jedoch nur die Position des ersten gefundenen Elements zurück:

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

Suchschlüssel nach einem Wert in dict

dict hat keine integrierte Methode zum Suchen eines Werts oder Schlüssels, da Wörterbücher ungeordnet sind. Sie können eine Funktion erstellen, die den Schlüssel (oder die Schlüssel) für einen angegebenen Wert abruft:

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

Dies könnte auch als äquivalentes Listenverständnis geschrieben werden:

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

Wenn Sie nur einen gefundenen Schlüssel interessieren:

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

Die ersten beiden Funktionen geben eine list aller keys mit dem angegebenen Wert zurück:

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) # []

Der andere gibt nur einen Schlüssel zurück:

getOneKeyForValue(adict, 10)   # 'c'  - depending on the circumstances this could also be 'a'
getOneKeyForValue(adict, 20)   # 'b'

und wirft eine StopIteration - Exception , wenn der Wert nicht in dem ist dict :

getOneKeyForValue(adict, 25)

StopIteration

Den Index für sortierte Sequenzen abrufen: bisect.bisect_left ()

Sortierte Sequenzen ermöglichen die Verwendung schneller Suchalgorithmen: 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

Bei sehr großen sortierten Sequenzen kann der Geschwindigkeitszuwachs sehr hoch sein. Für die erste Suche ungefähr 500 mal so schnell:

%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

Es ist zwar etwas langsamer, wenn das Element eines der ersten ist:

%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

Verschachtelte Sequenzen durchsuchen

Das Suchen in verschachtelten Sequenzen wie eine list von tuple erfordert einen Ansatz wie das Durchsuchen der Schlüssel nach Werten in dict , erfordert jedoch angepasste Funktionen.

Der Index der äußersten Sequenz, wenn der Wert in der Sequenz gefunden wurde:

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

oder der Index der äußeren und inneren Sequenz:

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

Im Allgemeinen ( nicht immer ) ist die Verwendung von next und eines Generatorausdrucks mit Bedingungen zum Auffinden des ersten Werts des gesuchten Werts der effizienteste Ansatz.

Suchen in benutzerdefinierten Klassen: __contains__ und __iter__

Um die Verwendung von in für benutzerdefinierte Klassen zuzulassen, muss die Klasse entweder die magische Methode __contains__ oder, __iter__ eine __iter__ __contains__ Methode, __iter__ .

Angenommen, Sie haben eine Klasse, die eine list mit list s enthält:

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))

Mitgliedschaft Prüfung zu verwenden ist möglich mit 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__.

auch nach dem Löschen der __contains__ Methode:

del ListList.__contains__
5 in a     # True
# Prints: Using __iter__.

Hinweis: Die Schleife in (wie in for i in a ) verwendet immer __iter__ auch wenn die Klasse eine implementiert __contains__ Methode.



Modified text is an extract of the original Stack Overflow Documentation
Lizenziert unter CC BY-SA 3.0
Nicht angeschlossen an Stack Overflow