파이썬 API 둘러보기

bisect(, SortedList)

가끔 정렬된 리스트가 필요하다.

정렬된 상태를 유지하면서 O(logn)으로 찾거나 삽입하는 리스트.

 

주의할 점은, bisect.bisect()는 아이템이 없어도 그냥 삽입할 인덱스가 어디인지 돌려준다.

>>> import bisect
lst = [1, 4, 7, 10]

>>> bisect.bisect(lst, 5)
2
>>> bisect.bisect(lst, 4)
2

>>> bisect.insort(lst, 8)
>>> lst
[1, 4, 7, 8, 10]

>>> bisect.insort(lst, 11)
>>> lst
[1, 4, 7, 8, 10, 11]

>>> bisect.insort(lst, 4)
>>> lst
[1, 4, 4, 7, 8, 10, 11]

 

sortedcontainers.SortedList

간편해 보이는데 따로 설치해야 한다.

 

또는

 

이렇게 직접 만들 수도 있다:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
장과장02
현재 버전
선택 버전
graphittie 자세히 보기