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

bisect — 배열 이진 분할 알고리즘 (Array bisection algorithm)

리스트를 매번 삽입 후 정렬하지 않고도 정렬된 순서를 유지할 수 있게 해주는 모듈이에요. 비교 비용이 비싼 긴 리스트의 경우 선형 탐색이나 잦은 재정렬보다 나은 성능을 낼 수 있어요.

출처: Python 표준 라이브러리

본문

이 모듈은 매번 삽입 후 리스트를 정렬할 필요 없이 리스트를 정렬된 순서로 유지하는 것을 지원해요. 비교 연산이 비싼 긴 리스트의 경우, 이는 선형 탐색이나 잦은 재정렬보다 개선된 방식일 수 있어요.

모듈 이름이 bisect인 이유는 기본 이진 분할(bisection) 알고리즘을 사용하기 때문이에요. 특정 값을 검색하는 다른 이분 탐색 도구와 달리, 이 모듈의 함수는 삽입 지점(insertion point) 을 찾도록 설계됐어요. 따라서 이 함수들은 값이 발견됐는지 판단하기 위해 __eq__() 메서드를 절대 호출하지 않아요. 대신 __lt__() 메서드만 호출하고 배열의 값들 사이의 삽입 지점을 반환해요.

참고: 이 모듈의 함수는 스레드 안전하지 않아요. 여러 스레드가 같은 시퀀스에 대해 bisect 함수를 동시에 사용하면 정의되지 않은 동작이 발생할 수 있어요. 마찬가지로 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는 배열의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 키 함수를 지정해요. 복잡한 레코드 검색을 지원하기 위해 키 함수는 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를 정렬된 순서로 삽입해요. 이 함수는 먼저 bisect_left()를 실행해 삽입 지점을 찾아요. 그다음 a에 insert() 메서드를 실행해 정렬 순서를 유지하도록 x를 적절한 위치에 삽입해요. 테이블에 레코드를 삽입하는 것을 지원하기 위해 키 함수(있다면)는 검색 단계에는 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()와 비슷하지만 x를 a 안의 기존 항목들 뒤에 삽입해요. 이 함수는 먼저 bisect_right()를 실행해 삽입 지점을 찾아요. 그다음 a에 insert() 메서드를 실행해 정렬 순서를 유지하도록 x를 적절한 위치에 삽입해요. 키 함수(있다면)는 검색 단계에는 x에 적용되지만 삽입 단계에는 적용되지 않아요. O(log n) 검색이 느린 O(n) 삽입 단계에 지배된다는 점을 명심하세요. 3.10 버전 변경: key 매개변수 추가.

성능 참고사항

bisect()와 insort()를 사용해 시간에 민감한 코드를 작성할 때 다음을 명심하세요:

이분 분할은 값의 범위를 검색하는 데 효과적이에요. 특정 값을 찾으려면 딕셔너리가 더 성능이 좋아요.
insort() 함수는 로그 검색 단계가 선형 시간 삽입 단계에 지배되기 때문에 O(n)이에요.
검색 함수는 상태가 없고 키 함수 결과를 사용한 후 버려요. 따라서 검색 함수를 루프에서 사용하면 키 함수가 같은 배열 요소에 대해 반복해서 호출될 수 있어요. 키 함수가 빠르지 않다면 중복 계산을 피하기 위해 @functools.cache로 감싸는 것을 고려해보세요. 또는 아래 예시 섹션에서 보여주듯 미리 계산된 키 배열을 검색해 삽입 지점을 찾는 것도 고려해보세요.

더 알아보기

Sorted Collections — bisect를 사용해 정렬된 데이터 컬렉션을 관리하는 고성능 모듈.
SortedCollection recipe — bisect로 간단한 검색 메서드와 키 함수 지원을 갖춘 완전한 기능의 컬렉션 클래스를 만드는 레시피. 검색 중 불필요한 키 함수 호출을 줄이기 위해 키가 미리 계산돼요.

정렬된 리스트 검색하기

위 bisect 함수는 삽입 지점을 찾는 데 유용하지만 일반적인 검색 작업에는 까다롭거나 어색하게 쓰일 수 있어요. 다음 다섯 함수는 이를 정렬된 리스트의 표준 조회로 변환하는 방법을 보여줘요:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to 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')
... ]

>>> # Find the first movie released after 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')

>>> # Insert a movie while maintaining sort order
>>> 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])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a list of keys.
>>> 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)