Mam posortowaną listę L i mam binarne wyszukiwanie do określenia, gdzie na liście, aby wstawić element tak, że lista wynikowa będzie nadal w porządku.Python: wstawić na listę szybciej niż O (N)?
Jednak L.insert (indeks, obiekt) wymaga złożoności czasu O (N).
Czy istnieje inna struktura danych dla L, która będzie służyć temu samemu celowi, ale pozwala na szybsze wstawianie?
Sprawdź moduł blist.
https://pypi.python.org/pypi/blist/
Podnosi O (log n) instalacji.
Wykorzystanie:
x = #list contents
y = blist(x)
y.insert(index, object) #now works in O(log n)
Podczas gdy ten link może odpowiedzieć na pytanie, lepiej umieścić w nim istotne części odpowiedzi i podać link do odsyłacza. Odpowiedzi dotyczące linków mogą stać się nieważne, jeśli strona z linkami się zmieni. –
Krzyk się sortedcontainers.SortedList. Spowoduje to automatyczne uporządkowanie listy z szybkim czasem wstawiania.
from sortedcontainers import SortedList
mylist = SortedList([1, 2, 4, 5])
mylist.add(3)
mylist
#>>> SortedList([1, 2, 3, 4, 5], load=1000)
SortedListinsertions are amortized O(sqrt n), or O(cbrt n) with different choices of parameters, ale skaluje lepiej niż blist, który jest O(log n), ponieważ stałe są dużo lepsze. Jest a very in-depth look at performance on their website.
Alternatywnie, być może potrzebujesz priority queue, w którym to przypadku możesz uzyskać potencjalnie szybsze wkładki z the heapq module.
Część 'O (log n)' jest [nie ściśle prawdą] (http://www.grantjenks.com/doc s/sortedcontainers/performance-scale.html). 'sortedcontainers.SortedList' przechowuje dane w [zbilansowanych listach list] (http://www.grantjenks.com/docs/sortedcontainers/implementation.html) i wykorzystuje lokację danych, która pozwala szybciej zamortyzować czas. Złożoność wstawki Big-O jest, ściśle mówiąc, 'O (n^2)', ale z powodu dużego "współczynnika obciążenia", złożoność wstawki amortyzowanej wynosi ~ n^(1/3) '. – randomir
@randomir Dzięki, to jest coś [byłem świadomy] (https://www.reddit.com/r/Python/comments/4ge9xs/python_sorted_collections/d2hkra5/), właśnie wtedy, kiedy to napisałem. Mój post został już naprawiony. – Veedrac
Nadal dobra odpowiedź, chociaż (nie wiedziałem o "sortowanych kontenerach", prawdopodobnie dlatego, że ich nie potrzebowałem do dziś :)). – randomir
Drzewo wyszukiwania binarnego? Wygląda na to, że Python nie ma wbudowanego, ale prawdopodobnie istnieje pakiet dla jednego. –
Tak Drzewo wyszukiwania binarnego to wstawienie O (1). –
Ahh Miałem nadzieję, że nie powiecie BST. :( – user4967499