데이터 구조체

정렬된 시퀀스를 bisect로 관리하기

bisect 모듈은 bisect()와 insort()함수를 제공하고, bisect()는 이진 검색 알고리즘을 활용해서 시퀀스를 검색하고, insort()는 정렬된 시퀀스 안에 항목을 삽입한다.

bisect()로 검색하기

bisect(haystack, needle)은 정려려된 시퀀스인 haystack 안에서 오름차순 정렬 상태를 유지한 채로 needle을 추가할 수 있는 위치를 찾아낸다.

해당 위치 앞에는 needle보다 같거나 작은 항목이 오고, bisect(haystack, needle)의 결과값을 인덱스로 사용해서 haystack.insect(index, needle)을 호출하면 needle을 추가할 수 있지만, insort() 함수는 이 두 과정을 더 빨리 처리한다.

SortedCollection 비법 (http://bit.ly/1Vm6WEa)을 제공하고있다.

import bisect
import sys

HAYSTACK = [1,4,5,6,8,12,15,20,21,23,23,26,29,30]
NEEDLES = [0,1,2,5,8,10,22,23,29,30,31]

ROW_FMT = '{0:2d} @ {1:2d}. {2}{0:<2d}'

def demo(bisect_fn):
	for needle in reversed(NEEDLES):
    	position = bisect_fn(HAYSTACK, needle) #삽입할 위치를 찾아내기 위해 선택한 bisect 함수를 사용한다.
        offset = position * '  |' #간격(offset)에 비례해서 수직 막대 패턴을 만든다.
        print(ROW_FMT.format(needle, position, offset)) #needl과 삽입 위치를 보여주는 포맷된 행을 출력한다.
        
if __name__ == '__main__':


if sys.argv[-1] == 'left': #마지막 명령행을 인수에 따라 사용할 bisect함수를 선택한다.

	bisect_fn = bisect.bisect_left
    
else:
	bisect_fn = bisect.bisect
    
print('DEMO:', bisect_fn.__name__)#선택된 함수명을 헤더에 출력한다.
print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
demo(bisect_fn)

bisect의 행동은 선택 인수 lo와 hi를 사용하면 삽입할 때 검색할 시퀀스 영역을 좁힐 수 있게 되고, lo의 기본값은 0, hi의 기본값은 시퀀스의 len()이다.

bisect는 실제로 bisect_right() 함수의 별명이고, 이 함수의 자매 함수로 bisect_left()가 있다.

• bisect_right()

  • 기존 항목 바로 뒤를 삽입 위치로 반환한다.

• bisect_left()

  • 기존 항목 위치를 삽입 위치로 변환하므로 기존 항목 바로 앞에 삽입이 된다.

"""
이 정렬된 긴 숫자 시퀀스를 검색할 때 index() 대신 더 빠른 bisect()함수를 사용한다.
https://docs.python.org/3/library/bisect.html
"""
def grade(score, breakpoints=[60,70,80,90], grades ='FDCBA'):
	i = bisect.bisect(breakpoints, score)
    return grades[i]
    
[grade(score) for score in [33,99,77,70,89,90,100]]

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

2.8.2 bisect.insort()로 삽입하기

정렬은 값비싼 연산으로 시퀀스를 일단 정렬한 후에는 정렬 상태를 유지하는 것이 좋기에 bisect().insort() 함수가 만들어졌다.

"""
bisect함수와 마찬가지로 insort 함수도 선택적으로 lo와 hi 인수를 받아 시퀀스 안에서 검색할 범위를 제한하고  삽입 위치를 검색하기 위해 bisect_left()함수를 사용하는 insort_left()함수도 있다.


"""
import bisect
import random

SIZE = 7

random.seed(1729)

my_list = []
for i in range(SIZE):
	new_item = random.randrange(SIZE*2)
    bisect.insort(my_list,new_item)
    print('%2d ->' % new_item, my_list)

Summary

위에서 설명한 내용은 리스트나 튜플뿐만 아니라 시퀀스에서도 적용되고, 리스트형이 사용하기 편하므로 남용하는 경우가 있다!! 그러므로, 숫자들로 구성된 리스트를 다루고 있다면 배열을 사용하는 것이 좋다.