bisect 모듈은 순서가 지정된 목록을 유지합니다.

bisect – 순서 있는 목록 유지

목적: 순서 있는 목록을 유지하기 위해 매번 sort를 호출할 필요가 없습니다.

bisect 모듈은 순서가 지정된 목록에 요소를 삽입하는 알고리즘을 구현합니다. 어떤 경우에는 목록을 반복적으로 정렬하거나 큰 목록을 구성한 후 정렬하는 것보다 이것이 더 효율적입니다. Bisect는 이분법을 의미합니다. 여기서는 bisection 방법을 사용하여 정렬합니다. bisect의 소스 코드는 bisection 정렬을 위한 템플릿입니다. 이 모듈에는 100줄 미만의 코드가 있습니다.

삽입

import bisect
import random
   
# Use aconstant seed to ensure that
# the samepseudo-random numbers
# are usedeach time the loop is run.
random.seed(1)
   
print'New  Pos Contents'
print'---  --- --------'
   
# Generaterandom numbers and
# insert theminto a list in sorted
# order.
l = []
for i inrange(1, 15):
#产生1-100的随机数
    r = random.randint(1, 100)
    position = bisect.bisect(l, r)
    bisect.insort(l, r)
print'%3d  %3d' % (r, position), l

실행 결과:

#./bisect_example.py

새 Pos 콘텐츠

--- - ----------

14 0[14]

85 1[14, 85]

77 1[14, 77, 85]

26 1[14, 26, 77, 85]

50 2[14, 26, 50, 77, 85]

45 2[14, 26, 45, 50, 77, 85]

66 4[14, 26, 45, 50, 66, 77, 85]

79 6[14, 26, 45, 50, 66, 77, 79, 85]

10 0[10, 14, 26, 45, 50, 66, 77, 79, 85]

3 0[3, 10, 14, 26, 45, 50, 66, 77, 79, 85]

84 9[3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]

44 4[ 3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]

77 9[3, 10, 14, 26, 44, 45, 50, 66, 77 , 77, 79, 84, 85]

1 0[1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

Bisect 모듈에서 제공하는 기능은 다음과 같습니다.

bisect.bisect_left(a,x, lo=0, hi=len(a)) :

순서가 지정된 목록 a에 x가 삽입된 인덱스를 찾습니다. lo와 hi는 목록의 범위를 지정하는 데 사용되며 기본값은 전체 목록을 사용하는 것입니다. x가 이미 존재하는 경우 왼쪽에 삽입합니다. 반환 값은 인덱스입니다.

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

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

이 둘은 bisect_left와 유사하지만 x가 이미 존재하는 경우 오른쪽에 삽입합니다.

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

순서 목록 a에 x를 삽입합니다. 효과는 a.insert(bisect.bisect_left(a,x, lo, hi), x)와 동일합니다.

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

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

insort_left와 유사하지만 x가 이미 존재하는 경우 오른쪽에 삽입합니다.

함수는 2가지 카테고리로 나눌 수 있는데, bisect*는 인덱스를 찾는 데 사용됩니다. Insort*는 실제 삽입에 사용됩니다. 기본적으로 반복은 오른쪽부터 삽입됩니다. 가장 일반적으로 사용되는 것은 아마도 insort일 것입니다.

표준에 점수를 기준으로 성적을 계산하는 예가 있습니다:

>>> def grade(score,breakpoints=[60, 70, 80, 90], grades='FDCBA ') :

... i = 이등분(중단점, 점수)

... 성적 반환[i]

...

> >> [[33, 99, 77, 70, 89, 90, 100]의 점수 등급(점수)]

['F', 'A', 'C','C', ' B' , 'A', 'A']

Bisect는 sort와 같은 키워드 매개변수를 지원하지 않습니다.

>>> data =[('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambdar: r[1])
>>> keys =[r[1] for r in data]         #precomputed 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)