Zoeken…


Opmerkingen

Alle zoekalgoritmen op iterables die n elementen bevatten, hebben een O(n) -complexiteit. Alleen gespecialiseerde algoritmen zoals bisect.bisect_left() kunnen sneller zijn met de complexiteit van O(log(n)) .

De index voor strings ophalen: str.index (), str.rindex () en str.find (), str.rfind ()

String hebben ook een index methode, maar ook meer geavanceerde opties en de extra str.find . Voor beide is er een complementaire omgekeerde methode.

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

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

Het verschil tussen index / rindex en find / rfind is wat er gebeurt als de substring niet in de string wordt gevonden:

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

Al deze methoden staan een begin- en eindindex toe:

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: substring niet gevonden

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

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

Zoeken naar een element

Alle ingebouwde collecties in Python implementeren een manier om elementlidmaatschap te controleren met behulp van in .

Lijst

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

Draad

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

reeks

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

Dict

dict is een beetje bijzonder: de normale in controleert alleen de toetsen. Als u in waarden wilt zoeken, moet u dit opgeven. Hetzelfde als u wilt zoeken naar sleutel / waarde- paren.

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

De indexlijst en tuples ophalen: list.index (), tuple.index ()

list en tuple hebben een index methode om de positie van het element te krijgen:

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 staat niet in de lijst

Maar geeft alleen de positie van het eerst gevonden element terug:

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

Sleutel (s) zoeken naar een waarde in dict

dict heeft geen ingebouwde methode voor het zoeken naar een waarde of sleutel omdat woordenboeken niet zijn geordend. U kunt een functie maken waarmee de sleutel (of toetsen) worden opgehaald voor een opgegeven waarde:

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

Dit kan ook worden geschreven als een equivalent lijstbegrip:

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

Als je maar om één gevonden sleutel geeft:

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

De eerste twee functies retourneren een list met alle keys met de opgegeven waarde:

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

De andere geeft slechts één sleutel terug:

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

en er sprake van een StopIteration - Exception als de waarde is niet in het dict :

getOneKeyForValue(adict, 25)

StopIteration

De index ophalen voor gesorteerde sequenties: bisect.bisect_left ()

Gesorteerde sequenties maken het gebruik van sneller zoekalgoritmen mogelijk: 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

Voor zeer grote gesorteerde reeksen kan de snelheidstoename behoorlijk hoog zijn. In het geval van de eerste zoekopdracht ongeveer 500 keer zo snel:

%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

Hoewel het een beetje langzamer is als het element een van de eerste is:

%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

Geneste reeksen zoeken

Zoeken in geneste reeksen zoals een list met tuple vereist een benadering zoals het zoeken van de sleutels naar waarden in dict maar heeft aangepaste functies nodig.

De index van de buitenste reeks als de waarde in de reeks is gevonden:

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

of de index van de buitenste en binnenste reeks:

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

Over het algemeen ( niet altijd ) is het gebruik van de next en een generatoruitdrukking met voorwaarden om het eerste voorkomen van de gezochte waarde te vinden de meest efficiënte aanpak.

Zoeken in aangepaste klassen: __contains__ en __iter__

Om het gebruik van in voor aangepaste klassen toe te staan, moet de klasse de magische methode __contains__ of, als dat niet het geval is, een __iter__ __-methode.

Stel dat u een klasse hebt die een list met list :

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

Het gebruik van lidmaatschapstesten is mogelijk met behulp 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__.

zelfs na het verwijderen van de __contains__ methode:

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

Opmerking: De lus in (zoals in for i in a ) gebruikt altijd __iter__ zelfs als de klasse implementeert een __contains__ methode.



Modified text is an extract of the original Stack Overflow Documentation
Licentie onder CC BY-SA 3.0
Niet aangesloten bij Stack Overflow