Dlaczego w standardowych bibliotekach Pythona nie ma posortowanych kontenerów?

83

Czy istnieje decyzja projektowa w języku Python (PEP), która uniemożliwia dodanie posortowanego kontenera do Pythona?

( OrderedDictnie jest sortowanym kontenerem, ponieważ jest uporządkowany według kolejności reklamowej).

python language-design sortedset sortedmap Neil G.
źródło
1
lubią kolekcje.OrderedDict?
utdemir
1
Jest po prostu szybszy. O (1) dla hashmap vs O (log n) dla uporządkowanego zbioru.
vartec
19
@utdmr: OrderedDict jest sortowane według kolejności wstawiania, a nie według dowolnego klucza, takiego jak posortowany kontener.
Neil G
1
@ Hi-Angel Nie, nie to oznacza posortowany kontener . Np.
Neil G
1
„sortowany kontener to taki, który sortuje elementy po wstawieniu”. Niezupełnie: powiedziałbym, że posortowany kontener to kontener, którego interfejs ma wydajnie posortowaną (według dowolnego klucza) iterację i wyszukiwanie. Twoje nieporozumienie wynika z twojej niezwykłej definicji.
Neil G,

Odpowiedzi:

77

To świadoma decyzja projektowa ze strony Guido (nawet trochę niechętnie odnosił się do dodania collectionsmodułu). Jego celem jest zachowanie „jednego oczywistego sposobu”, jeśli chodzi o wybór typów danych dla aplikacji.

Podstawowa koncepcja polega na tym, że jeśli użytkownik jest na tyle wyrafinowany, aby zdać sobie sprawę, że wbudowane typy nie są właściwym rozwiązaniem jego problemu, to musi również znaleźć odpowiednią bibliotekę strony trzeciej.

Biorąc pod uwagę, że lista + sortowanie, lista + heapq i lista + połowa obejmują wiele przypadków użycia, które w przeciwnym razie opierałyby się na z natury posortowanych strukturach danych, a pakiety takie jak blist istnieją, nie ma dużego wysiłku, aby dodać więcej złożoności w tej przestrzeni biblioteka standardowa.

Pod pewnymi względami jest to podobne do faktu, że w standardowej bibliotece nie ma wielowymiarowej tablicy, zamiast tego powierza to zadanie ludziom NumPy.

ncoghlan
źródło
2
Dzięki, szukałem motywacji stojących za tą decyzją projektową. Dokładnie takiej odpowiedzi szukałem. Mój początkowy instynkt nie był taki, aby robić rzeczy w ten sposób, ale argument jest bardzo przekonujący.
Neil G
collections.Countermoże być używany jako posortowany zestaw. Chociaż może to nie być wydajne.
coderek
1
@coderek: collections.Counterjest nieposortowany i nie nadaje się do reprezentowania posortowanego zestawu.
user2357112 obsługuje Monikę
Ale czy nie należy posortować przynajmniej wbudowanego słownika? Słownik musi być przechowywany w sposób posortowany, aby zapewnić szybki dostęp do elementów, wydaje mi się to dziwne, że kiedy go iterujesz, nadal w jakiś sposób otrzymujesz nieposortowane elementy.
Cześć Angel
1
@ Hi-Angel dictto tabela skrótów.
Neil G,
82

Istnieje również posortowane kontenery w języku Python moduł , który implementuje sortowane listy, dyktowanie i typy zestawów. Jest bardzo podobny do blist, ale zaimplementowany w czystym Pythonie iw większości przypadków szybszy .

>>> from sortedcontainers import SortedSet
>>> ss = SortedSet([3, 7, 2, 2])
>>> ss
SortedSet([2, 3, 7])

Ma również funkcjonalność niespotykaną w innych pakietach:

>>> from sortedcontainers import SortedDict
>>> sd = SortedDict((num, num) for num in range(100000))
>>> sd.iloc[-5] # Lookup the fifth-to-last key.
99995

Zastrzeżenie: Jestem autorem modułu sortcontainers.

GrantJ
źródło
1
Miły! Możesz rozważyć aktualizację dokumentacji, aby określić, że podstawowym magazynem jest lina .
Neil G
1
@NeilG Thanks! Uwagi dla par: blist nie jest napisany w czystym Pythonie. Posortowane typy set, list i dict są oparte na typie blist, który jest drzewem B + zaimplementowanym w C. Ponadto podstawowa struktura nie jest tak naprawdę liną; jest bardziej podobny do drzewa B +, ale ma tylko jeden poziom węzłów.
GrantJ
3
Właściwie to świetny przykład tego, jak duże-O może wprowadzać w błąd. Prawdopodobnie zwolniłoby około biliona elementów, ale większość ludzi nie ma terabajta pamięci, żeby się tym martwić. Przetestowałem go na miliardy elementów i był tak szybki, jak implementacje w C. Zużywa również znacznie mniej pamięci, utrzymując taką prostą, opartą na listach strukturę.
GrantJ
1
Tak oczywiście. To ten sam argument, którego używają, aby uzasadnić użycie tego rodzaju struktury danych dla ciągów znaków, zwłaszcza długich ciągów, które są używane w edytorze.
Neil G
2
W każdym razie dziękuję za napisanie tego. Będę o tym pamiętać, jeśli będę potrzebować tej struktury danych.
Neil G
11

Istnieje również moduł blist , który zawiera sortowany zestaw danych:

sortedset(iterable=(), key=None)

>>> from blist import sortedset
>>> my_set = sortedset([3,7,2,2])
sortedset([2, 3, 7]
Adrian
źródło
5

Nie jest to dokładnie „posortowany kontener”, ale możesz być zainteresowany modułem z połówką biblioteki standardowej , który „zapewnia obsługę utrzymywania listy w porządku posortowanym bez konieczności sortowania listy po każdym wstawieniu”.

Steven
źródło
1

W heapqstandardowej bibliotece znajduje się znak , nie jest dokładnie posortowany, ale w pewnym sensie. Istnieje również pakiet blist , ale nie ma go w standardowej bibliotece.

opat
źródło
-2

Listy Pythona są uporządkowane. Jeśli je posortujesz, zostaną w ten sposób. W Pythonie 2.7 dodano OrderedDicttyp, aby utrzymać jawnie uporządkowany słownik.

Python również ma zestawy (zbiór, w którym elementy muszą być unikalne), ale z definicji są one nieuporządkowane. Sortowanie zestawu zwraca po prostu a list.

jatanizm
źródło
8
Dziękuję za poświęcenie czasu na odpowiedź. OrderedDict jest sortowane według kolejności wstawiania, a nie według dowolnego klucza, takiego jak posortowany kontener. zestaw nie jest również sortowanym kontenerem.
Neil G
1
Czy btree może być tym, czego szukasz? stackoverflow.com/questions/628192#628432
jathanism
dzięki, btree jest dokładnie tym, czego szukałem. Mam zamiar pójść na jaw, ponieważ jest w MacPorts i ma kilka przydatnych struktur danych.
Neil G