Python 모듈 소개 - 이등분 순서 목록

bisect – 순서 있는 목록 유지

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

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

삽입

가져오기 이등분

임의로 가져오기

# 상수 시드를 사용하여

# 동일한 의사 난수

#은 루프가 실행될 때마다 사용됩니다.

random.seed(1)

print'New Pos Contents'

print'--- --- --------'

# 난수를 생성하고

# 해당 항목을 목록에 삽입합니다. sorted

# 순서.

l = []

for i inrange(1, 15):

r = 무작위.randint(1, 100 )

위치 = bisect.bisect(l, r)

bisect.insort(l, r)

print'%3d %3d' %(r, 위치) , 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)):

순서에 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가 이미 존재하는 경우 오른쪽에 삽입합니다.

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

표준의 점수를 기준으로 평점을 계산하는 예가 있습니다.

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

... i = bisect(중단점, 점수)

... 성적 반환[i]

...

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

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

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

>> ;> 데이터 =[('빨간색', 5), ('파란색', 1), ('노란색', 8), ('검은색', 0)]

>>> data.sort(key=lambdar: r[1])

>>keys =[r[1] for r in data] # 미리 계산된 키 목록

>> 데이터[bisect_left(keys,0)]

('검정색', 0)

>>> 키,1)]

('파란색', 1)

>>> data[bisect_left(keys,5)]

('빨간색', 5)

>>> 데이터[bisect_left(keys,8)]

('노란색', 8)