Czy Python ma posortowaną listę?

Przez co rozumiem strukturę z:

• O (log n) złożoność x.push()operacji
• O (log n) złożoność znalezienia elementu
• O (n) złożoność obliczeń, list(x)które zostaną posortowane

Miałem również powiązane pytanie dotyczące wydajności, list(...).insert(...)która jest teraz tutaj .

Standardowa lista Pythona nie jest sortowana w żadnej formie. Standardowy moduł heapq może być użyty do dołączenia O (log n) do istniejącej listy i usunięcia najmniejszej z O (log n), ale nie jest to posortowana lista w twojej definicji.

Istnieją różne implementacje zbalansowanych drzew dla Pythona, które spełniają twoje wymagania, np. Rbtree , RBTree lub pyavl .

Czy jest jakiś szczególny powód, dla którego masz duże wymagania? A może po prostu chcesz, żeby był szybki? Sortedcontainers moduł czystej Python i szybko (jak szybko jak -C implementacjach jak BList i rbtree).

Do wykonania porównania pokazuje, że poziomy odniesienia szybciej lub na równi z BLIST jest posortowana lista typu. Zauważ również, że rbtree, RBTree i PyAVL zapewniają posortowane dyktowanie i typy zestawów, ale nie mają posortowanego typu listy.

Jeśli wymagana jest wydajność, zawsze pamiętaj o testach porównawczych. Moduł, który uzasadnia twierdzenie, że jest szybki w notacji Big-O, powinien być podejrzany, dopóki nie pokaże również porównań wzorców.

Zastrzeżenie: jestem autorem modułu sortcontainers w języku Python.

Instalacja:

pip install sortedcontainers

Stosowanie:

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

Chociaż nadal nigdy nie sprawdzałem szybkości "dużych O" podstawowych operacji na listach Pythona, bisectprawdopodobnie warto wspomnieć w tym kontekście o module standardowym:

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

PS. Ach, przepraszam, bisectjest mowa w przywoływanym pytaniu. Mimo to myślę, że nie zaszkodzi, jeśli te informacje będą tutaj)

PPS. A listy CPythona są w rzeczywistości tablicami (nie powiedzmy listami przeskoków itp.). Cóż, myślę, że muszą to być coś prostego, ale jak dla mnie nazwa jest trochę myląca.

Tak więc, jeśli się nie mylę, prędkości w połowie / listy prawdopodobnie byłyby:

• dla push (): O (n) dla najgorszego przypadku;
• dla wyszukiwania: jeśli uznamy, że szybkość indeksowania tablicy wynosi O (1), wyszukiwanie powinno być operacją O (log (n));
• do tworzenia listy: O (n) powinno być szybkością kopiowania listy, w przeciwnym razie jest to O (1) dla tej samej listy)

Upd. Po dyskusji w komentarzach pozwólcie mi połączyć tutaj następujące pytania SO: W jaki sposób jest implementowana lista Pythona i jaka jest złożoność funkcji list Pythona w czasie wykonywania

import bisect

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

Chociaż nie zapewnia (jeszcze) niestandardowej funkcji wyszukiwania, heapqmoduł może odpowiadać Twoim potrzebom. Implementuje kolejkę sterty przy użyciu zwykłej listy. Musiałbyś napisać swój własny skuteczny test członkostwa, który wykorzystuje wewnętrzną strukturę kolejki (można to zrobić w O (log n) , powiedziałbym ...). Jest jedna wada: wyodrębnianie posortowanej listy ma złożoność O (n log n) .

Użyłbym modułów biscectlub sortedcontainers. Nie mam doświadczenia, ale myślę, że heapqmoduł działa. Zawiera plikHeap Queue

Zaimplementowanie własnej listy sortowania w Pythonie może nie być trudne. Poniżej znajduje się dowód słuszności koncepcji:

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)

========= Wyniki ============

[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