[python] 파이썬에는 정렬 된 목록이 있습니까?

Program / 글쓴이

이는 다음과 같은 구조를 의미합니다.

  • x.push()운영을 위한 O (log n) 복잡성
  • 요소를 찾기위한 O (log n) 복잡성
  • list(x)정렬 될 O (n) 복잡도 계산

또한 성능에 대한 관련 질문 list(...).insert(...)이 있습니다 .

답변

표준 파이썬리스트는 어떤 형태로도 정렬되지 않습니다. 표준 heapq 모듈을 사용하여 기존 목록에 O (log n)를 추가하고 O (log n)에서 가장 작은 것을 제거 할 수 있지만 정의에서 정렬 된 목록은 아닙니다.

rbtree , RBTree 또는 pyavl 과 같이 요구 사항을 충족하는 Python 용 균형 트리의 다양한 구현이 있습니다 .

답변

귀사의 요구 사항이 큰 특별한 이유가 있습니까? 아니면 그냥 빨리 하시겠습니까? sortedcontainers의 모듈 (blist rbtree와 같은 고속-C와 같은 구현에서와 같이) 고속 순수 파이썬하고있다.

성능 비교 쇼 더 빨리 또는에 파 blist의 정렬 된 목록 유형 벤치 마크. rbtree, RBTree 및 PyAVL은 정렬 된 dict 및 set 유형을 제공하지만 정렬 된 목록 유형은 없습니다.

성능이 필요한 경우 항상 벤치마킹해야합니다. Big-O 표기법이 빠르다는 주장을 입증하는 모듈은 벤치 마크 비교도 표시 할 때까지 의심의 여지가 있습니다.

면책 조항 : 저는 Python sortedcontainers 모듈의 저자입니다.

설치:

pip install sortedcontainers

용법:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5

답변

기본 파이썬 목록 작업의 “큰 O”속도를 아직 확인하지는 않았지만 bisect표준 모듈은 아마도이 맥락에서 언급 할 가치가 있습니다. 

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

추신. 아, 죄송합니다 bisect. 참조 된 질문에 언급되어 있습니다. 아직도, 나는이 정보가 여기에 있다면 크게 해를 끼치 지 않을 것이라고 생각합니다)

PPS. 그리고 CPython 목록은 실제로 배열입니다 (예 : skiplists 등). 글쎄, 나는 그들이 단순한 것이어야한다고 생각하지만, 나에게는 이름이 약간 오해의 소지가 있습니다.

따라서 내가 실수하지 않으면 bisect / list 속도는 아마도 다음과 같습니다.

  • push ()의 경우 : 최악의 경우 O (n);
  • 검색 : 배열 인덱싱 속도를 O (1)로 간주하면 검색은 O (log (n)) 연산이어야합니다.
  • 목록 생성의 경우 : O (n)은 목록 복사 속도 여야하며, 그렇지 않으면 동일한 목록에 대해 O (1)입니다.

Upd. 의견에 대한 토론에 이어 여기에 다음과 같은 질문을 링크 시키십시오 .Python의 List는 어떻게 구현 되고 파이썬 목록 함수의 런타임 복잡성은 무엇입니까?

답변

import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)

답변

사용자 정의 검색 기능을 제공하지는 않지만 heapq모듈은 사용자 요구에 적합 할 수 있습니다. 일반 목록을 사용하여 힙 큐를 구현합니다. 대기열의 내부 구조를 사용하는 효율적인 회원 자격 테스트를 작성해야합니다 ( O (log n) 에서 수행 할 수 있습니다 …). 한 가지 단점이 있습니다. 정렬 된 목록을 추출하면 복잡도가 O (n log n) 입니다.

답변

biscect또는 sortedcontainers모듈을 사용합니다 . 나는 실제로 경험이 없지만 heapq모듈이 작동 한다고 생각 합니다. 그것은 포함Heap Queue

답변

파이썬에서 자체 정렬 목록을 구현하는 것은 어렵지 않을 수 있습니다. 아래는 개념 증명입니다.

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]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= 결과 ============

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

101

삼

50