Python에서 정렬된 목록 작업: `bisect` 모듈의 마법

정렬된 목록으로 작업하는 것은 때로는 약간 까다로울 수 있습니다. 삽입할 때마다 목록의 순서를 유지하고 목록 내의 요소를 효율적으로 검색해야 합니다. 이진 검색은 정렬된 목록에서 검색하는 강력한 알고리즘입니다. 처음부터 구현하는 것은 그리 어렵지 않지만 시간이 많이 걸릴 수 있습니다. 다행히 Python에서는 정렬된 목록을 훨씬 쉽게 처리할 수 있는 bisect 모듈을 제공합니다.

이진 검색이란 무엇입니까?

이진 검색은 정렬된 배열 내에서 대상 값의 위치를 ​​찾는 알고리즘입니다. 전화번호부에서 이름을 검색한다고 상상해 보세요. 첫 번째 페이지부터 시작하는 대신 책 중간부터 시작하여 이름이 중간에 있는 것보다 알파벳순으로 큰지 또는 작은지에 따라 전반부에서 계속 검색할지 여부를 결정할 수 있습니다. 이진 검색은 비슷한 방식으로 작동합니다. 두 개의 포인터로 시작합니다. 하나는 목록의 시작 부분이고 다른 하나는 끝 부분입니다. 그런 다음 중간 요소가 계산되어 대상과 비교됩니다.

bisect 모듈: 정렬된 목록 작업 단순화

이진 검색은 효과적이지만 매번 구현을 작성하는 것은 지루할 수 있습니다. 하지만 단 한 줄의 코드로 동일한 작업을 수행할 수 있다면 어떨까요? 이것이 바로 Python의 bisect 모듈이 등장하는 곳입니다. Python의 표준 라이브러리의 일부인 bisect를 사용하면 삽입할 때마다 정렬할 필요 없이 정렬된 목록을 유지할 수 있습니다. 이는 간단한 이등분 알고리즘을 사용하여 수행됩니다.

bisect 모듈은 bisect와 insort라는 두 가지 주요 기능을 제공합니다. bisect 함수는 목록 정렬을 유지하기 위해 요소를 삽입해야 하는 인덱스를 찾는 반면, insort는 정렬 순서를 유지하면서 요소를 목록에 삽입합니다.

bisect 모듈 사용: 실제 예

모듈 가져오기부터 시작해 보겠습니다.

import bisect

예 1: 정렬된 목록에 숫자 삽입

정렬된 숫자 목록이 있다고 가정해 보겠습니다.

data = [1, 3, 5, 6, 8]

목록 정렬을 유지하면서 새 번호를 삽입하려면 다음을 사용하세요.

bisect.insort(data, 7)

이 코드를 실행한 후 데이터는 다음과 같습니다.

[1, 3, 5, 6, 7, 8]

예 2: 삽입점 찾기

실제로 숫자를 삽입하지 않고 숫자가 어디에 삽입될지 알고 싶다면 어떻게 해야 할까요? bisect_left 또는 bisect_right 함수를 사용할 수 있습니다.

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

이것은 목록 정렬을 유지하려면 인덱스 2에 숫자 4를 삽입해야 함을 나타냅니다.

예 3: 동적 목록에서 정렬 순서 유지

동적으로 증가하는 목록을 관리하고 있으며 정렬된 상태를 유지하면서 요소를 삽입해야 한다고 가정해 보겠습니다.

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

요소가 삽입되면 각 단계의 목록이 출력됩니다.

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

예 4: 사용자 정의 개체와 함께 bisect 사용

튜플과 같은 사용자 정의 개체 목록이 있고 이를 특정 기준에 따라 삽입하려고 한다고 가정해 보겠습니다.

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

또는 각 튜플의 두 번째 요소를 기반으로 삽입할 수도 있습니다.

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

이등분 활용: 단어 검색

bisect 모듈은 숫자에만 국한되지 않습니다. 문자열, 튜플, 문자 등의 목록을 검색하는 데에도 유용할 수 있습니다.
예를 들어, 정렬된 목록에서 단어를 찾으려면:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

또는 특정 접두사가 있는 단어 그룹에서 첫 번째 단어를 찾으려면:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix + 'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

단, bisect_left는 대상이 목록에 존재하는지 여부가 아니라 대상이 삽입되어야 하는 인덱스를 반환한다는 점에 유의하세요.

bisect와 insort의 변형

이 모듈에는 오른쪽 변형인 bisect_right 및 insort_right도 포함되어 있습니다. 이 함수는 요소가 이미 목록에 있는 경우 요소를 삽입할 가장 오른쪽 인덱스를 반환합니다. 예를 들어 bisect_right는 대상이 목록에 있는 경우 대상보다 큰 첫 번째 요소의 인덱스를 반환하는 반면 insort_right는 해당 위치에 요소를 삽입합니다.

후드 아래를 양분하다

bisect 모듈의 장점은 이진 검색 알고리즘을 효율적으로 구현하는 데 있습니다. 예를 들어 bisect.bisect_left를 호출하면 이 함수는 기본적으로 목록에서 이진 검색을 수행하여 새 요소에 대한 올바른 삽입 지점을 결정합니다.

내부적으로 작동하는 방식은 다음과 같습니다.

1. 초기화: 함수는 목록 내 검색 범위의 하한 및 상한을 나타내는 두 개의 포인터 lo 및 hi로 시작합니다. 처음에는 lo가 목록의 시작(인덱스 0)으로 설정되고 hi가 목록의 끝(목록 길이와 동일한 인덱스)으로 설정됩니다. 그러나 사용자 정의 lo 및 hi 값을 지정하여 목록의 특정 범위 내에서 검색할 수도 있습니다.

2. Bisection: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid + 1`.

1. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort_left code example:

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.

위 내용은 Python에서 정렬된 목록 작업: `bisect` 모듈의 마법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!