☰ Menu Python

☰ Menu

bisect — 배열 이진 분할 알고리즘

소스 코드: Lib/bisect.py

---

이 모듈은 정렬된 리스트를 삽입 후에 다시 정렬할 필요 없도록 관리할 수 있도록 지원합니다. 값비싼 비교 연산이 포함된 항목의 긴 리스트의 경우, 이는 선형 검색이나 빈번한 재정렬에 비해 개선된 것입니다.

이 모듈이 bisect`라고 불리는 이유는 기본 이진 분할 알고리즘을 사용하여 작업을 수행하기 때문입니다. 특정 값을 검색하는 다른 이진 분할 도구와 달리, 이 모듈의 함수는 삽입 지점을 찾도록 설계되었습니다. 따라서, 함수는 값이 발견되었는지 확인하기 위해 :meth:`~object.__eq__ 메서드를 절대 호출하지 않습니다. 대신, 함수는 __lt__() 메서드만 호출하고 배열의 값들 사이의 삽입 지점을 반환합니다.

참고

이 모듈의 함수들은 스레드에 안전하지 않습니다. 여러 스레드가 같은 시퀀스에 대해 bisect 함수를 동시에 사용하면 정의되지 않은 동작을 초래할 수 있습니다. 마찬가지로, 제공된 시퀀스가 다른 스레드에 의해 변경되는 동안 bisect 함수가 작동하면 결과는 정의되지 않습니다. 예를 들어, 여러 스레드에서 동일한 리스트에 :py:func:`~bisect.insort_left`를 사용하면 리스트가 정렬되지 않은 상태가 될 수 있습니다.

다음과 같은 함수가 제공됩니다:

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾습니다. 매개 변수 lo 와 hi는 고려해야 할 리스트의 부분집합을 지정하는 데 사용될 수 있습니다; 기본적으로 전체 리스트가 사용됩니다. x가 a에 이미 있으면, 삽입 위치는 기존 항목 앞(왼쪽)이 됩니다. 반환 값은 a가 이미 정렬되었다고 가정할 때 list.insert()의 첫 번째 매개 변수로 사용하기에 적합합니다.

반환된 삽입 위치 ip는 배열 a를 두 개의 조각으로 분할하여, 왼쪽에 대해서는 all(elem < x for elem in a[lo : ip])이 참이고, 오른쪽에 대해서는 all(elem >= x for elem in a[ip : hi])이 참이 되도록 만듭니다.

key*는 배열의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자의 :term:`키 함수 <key function>`을 지정합니다. 복잡한 레코드를 검색하는 것을 지원하기 위해, 키 함수는 *x 값에 적용되지 않습니다.

key 가 None 이면, 요소들은 직접 비교되며 키 함수는 호출되지 않습니다.

버전 3.10에서 변경: key 매개 변수를 추가했습니다.

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)

bisect_left()와 비슷하지만, a에 있는 x의 기존 항목 뒤(오른쪽)에 오는 삽입 위치를 반환합니다.

반환된 삽입 위치 ip는 배열 a를 두 개의 조각으로 분할하여, 왼쪽에 대해서는 all(elem <= x for elem in a[lo : ip])이 참이고, 오른쪽에 대해서는 all(elem > x for elem in a[ip : hi])이 참이 되도록 만듭니다.

버전 3.10에서 변경: key 매개 변수를 추가했습니다.

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)

a 에 x 를 정렬된 순서로 삽입합니다.

이 함수는 먼저 insert() 메서드를 실행합니다.

테이블의 레코드를 삽입하는 것을 지원하기 위해, key 함수(있는 경우)는 검색 단계에서는 x 에 적용되지만 삽입 단계에서는 적용되지 않습니다.

O (log n) 검색은 느린 O (n) 삽입 단계에 지배됨을 유의하십시오.

버전 3.10에서 변경: key 매개 변수를 추가했습니다.

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)

bisect.insort(a, x, lo=0, hi=len(a), *, key=None)

insort_left()와 비슷하지만, a에 x를 x의 기존 항목 다음에 삽입합니다.

이 함수는 먼저 insert() 메서드를 실행합니다.

테이블의 레코드를 삽입하는 것을 지원하기 위해, key 함수(있는 경우)는 검색 단계에서는 x 에 적용되지만 삽입 단계에서는 적용되지 않습니다.

O (log n) 검색은 느린 O (n) 삽입 단계에 지배됨을 유의하십시오.

버전 3.10에서 변경: key 매개 변수를 추가했습니다.

성능 참고 사항

bisect() 및 insort() 를 사용하여 시간 민감 코드를 작성할 때는 다음 사항들을 염두에 두십시오:

• 이진 분할은 값 범위 검색에 효과적입니다. 특정 값을 찾는 경우, 딕셔너리가 더 성능이 좋습니다.

• insort() 함수들은 로그 검색 단계가 선형 시간 삽입 단계에 지배되기 때문에 O (n)입니다.

• 검색 함수들은 상태를 가지지 않으며 사용 후 키 함수 결과를 버립니다. 결과적으로, 검색 함수들을 루프에서 사용하면 키 함수가 동일한 배열 요소에 여러 번 호출될 수 있습니다. 키 함수가 빠르지 않다면, 중복 계산을 방지하기 위해 :py:deco:`functools.cache`로 감싸는 것을 고려하십시오. 또는, (아래 예제 섹션에서 표시된 것처럼) 삽입 지점을 찾기 위해 미리 계산된 키 배열을 검색하는 것을 고려하십시오.

더 보기

• Sorted Collections 는 bisect 를 사용하여 정렬된 데이터 컬렉션을 관리하는 고성능 모듈입니다.

• bisect를 사용하여 직접적인 검색 메서드와 키 함수 지원을 포함하는 완전한 기능을 갖춘 컬렉션 클래스를 만드는 SortedCollection recipe. 검색 중에 불필요한 키 함수 호출을 피하고자 키는 미리 계산됩니다.

정렬된 리스트 검색하기

위의 bisect functions는 삽입 위치를 찾는 데 유용하지만, 일반적인 검색 작업에 사용하기가 까다롭거나 어색할 수 있습니다. 다음 다섯 함수는 정렬된 리스트에 대한 표준 조회로 변환하는 방법을 보여줍니다:

def index(a, x):
    'x 와 정확히 같은 가장 왼쪽의 값을 찾습니다'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'x보다 작은 가장 오른쪽 값을 찾습니다'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'x보다 작거나 같은 가장 오른쪽 값을 찾습니다'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'x보다 큰 가장 왼쪽 값을 찾습니다'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'x보다 크거나 같은 가장 왼쪽 항목을 찾습니다'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

예제

bisect() 함수는 숫자 테이블 조회에 유용할 수 있습니다. 이 예제는 bisect()를 사용하여 (가령) 시험 점수에 대한 문자 등급을 조회하는데, 정렬된 숫자 경계점 집합에 기반합니다: 90 이상은 ‘A’, 80에서 89는 ‘B’ 등입니다:

>>> def grade(score):
...     i = bisect([60, 70, 80, 90], score)
...     return "FDCBA"[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

bisect() 및 insort() 함수들은 튜플 리스트와도 작동합니다. key 인수는 테이블의 레코드 순서를 정하는 데 사용되는 필드를 추출하는 역할을 할 수 있습니다:

>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint

>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

>>> movies = [
...     Movie('Jaws', 1975, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # 1960년 이후 개봉한 최초의 영화를 찾습니다
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')

>>> # 정렬 순서를 유지하면서 영화를 삽입합니다
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
 Movie(name='Love Story', released=1970, director='Hiller'),
 Movie(name='Jaws', released=1975, director='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

키 함수가 비싸면, 미리 계산된 키 목록을 검색하여 레코드의 인덱스를 찾으면 반복돠는 함수 호출을 피할 수 있습니다:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # 또는 operator.itemgetter(1) 를 사용하세요.
>>> keys = [r[1] for r in data]         # 미리 계산된 키 리스트.
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)