python은 정렬된 목록을 가지고 있나요?

python은 정렬된 목록을 가지고 있나요?

즉, 다음과 같은 구조를 의미합니다.

• O(log n) 복잡도x.push()조작
• 요소를 찾기 위한 O(log n) 복잡도
• 계산의 복잡성list(x)어떤 것이 정리될지

퍼포먼스에 대한 질문도 있었어요list(...).insert(...)지금 여기에 있습니다.

big-O 요건의 특별한 이유가 있습니까?아니면 그냥 빨리 하길 바라는 거야?sorted containers 모듈은 순수 Python으로 고속입니다(blist 및 rbtree와 같은 fast-as-C 구현과 동일).

퍼포먼스 비교 결과, 블리스트의 정렬 리스트 타입과 동등하거나 보다 빠르게 벤치마킹할 수 있습니다.또한 rbtree, RBTree 및 PyAVL은 정렬된 dict 및 set 유형을 제공하지만 정렬된 목록 유형은 없습니다.

퍼포먼스가 필요한 경우는 항상 벤치마크를 실시해야 합니다.Big-O 표기법에서 빠르다는 주장을 입증하는 모듈은 벤치마크 비교 결과를 보여줄 때까지 의심해 보아야 합니다.

면책사항:저는 Python sorted containers 모듈의 저자입니다.

---

설치:

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

표준 Python 목록은 어떤 형식으로도 정렬되지 않습니다.표준 히프q 모듈을 사용하여 O(log n)에서 기존 목록에 추가하고 O(log n)에서 가장 작은 모듈을 제거할 수 있지만 정의에서 정렬된 목록이 아닙니다.

Python에는 rbtree, RBTree, pyavl 등 다양한 균형 트리가 구현되어 있습니다.

기본 Python 목록 작업의 "big 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 목록은 실제로 배열입니다(예를 들어 스키리스트 등이 아닙니다).뭐, 간단한 걸로 해야 할 것 같은데, 나로서는 이름이 좀 오해의 소지가 있어.

---

따라서 이등분/목록 속도는 다음과 같습니다.

• push()의 경우: 최악의 경우 O(n);
• 검색의 경우: 어레이 인덱싱의 속도를 O(1)로 간주할 경우 검색은 O(log(n) 연산이어야 합니다.
• 목록 작성의 경우: O(n)는 목록 복사 속도여야 합니다.그렇지 않으면 같은 목록의 O(1)가 됩니다.

업데이트. 코멘트에 대한 논의에 이어 다음 SO 질문을 링크하겠습니다.Python's List Implemented는 어떻게 구현되며 Python 목록 함수의 런타임 복잡성은 무엇입니까?

커스텀 검색 기능은 아직 제공되지 않지만 필요에 따라 모듈을 사용할 수 있습니다.일반 목록을 사용하여 힙큐를 구현합니다.큐의 내부 구조를 활용하는 효율적인 멤버십 테스트를 작성해야 합니다(O(log n)로 할 수 있습니다).단점은 정렬된 목록을 추출하면 복잡성이 O(n log n)가 발생한다는 것입니다.

import bisect

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

AVL 트리를 순서대로 트래버설과 조합하면, 이 문제는 시간의 복잡성으로 해결됩니다.

Python에 자신의 정렬 리스트를 실장하는 것은 어렵지 않을지도 모릅니다.다음은 개념 실증입니다.

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

3

50

사용bisect " " " " " "sortedcontainers패 altern. 또는,heapq큐를 합니다.

로운 경우:가 「」인 : 「」L는 이미 정렬되어 있습니다(예를 들어 정렬된 순서로 추가한 경우).다음 방법으로 표준 Python 목록을 사용하여 O(log n)에서 고속 검색을 이용할 수 있습니다.

import bisect
def in_sorted_list(elem, sorted_list):
    i = bisect.bisect_left(sorted_list, elem)
    return i != len(sorted_list) and sorted_list[i] == elem
L = ["aaa", "bcd", "hello", "world", "zzz"]
print(in_sorted_list("hellu", L))       # False

자세한 내용은 이 답변을 참조하십시오.

언급URL : https://stackoverflow.com/questions/1109804/does-python-have-a-sorted-list