수색…


비고

n 요소를 포함하는 iterables의 모든 검색 알고리즘은 O(n) 복잡성을 갖습니다. bisect.bisect_left() 와 같은 특수화 된 알고리즘 만이 O(log(n)) 복잡성으로 더 빠를 수 있습니다.

문자열 인덱스 얻기 : 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 / rindexfind / 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

요소 검색

파이썬의 모든 내장 컬렉션을 사용하여 요소의 회원 자격을 확인하는 방법 구현 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 ()

listtuple 은 요소의 위치를 ​​얻는 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)

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

처음 두 함수는 지정된 값을 갖는 모든 keys list 을 반환합니다.

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 발생시킵니다. - 값이 dict 없으면 Exception 발생합니다.

getOneKeyForValue(adict, 25)

중지

정렬 된 순서에 대한 색인 얻기 : 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

중첩 된 시퀀스 검색

tuple list 처럼 중첩 된 시퀀스를 검색하려면 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__ -method을.

listlist 포함한 클래스가 있다고합시다 :

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__ 메소드를 삭제 한 __contains__ :

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

참고 : 루핑 in (같이 for i in a ) 항상 사용합니다 __iter__ 클래스가 구현하는 경우에도 __contains__ 방법을.



Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow