पायथन: ओ (एन) से तेज सूची में डालें?

Question

मेरे पास एक क्रमबद्ध सूची एल है और मेरे पास यह निर्धारित करने के लिए एक बाइनरी खोज है कि सूची में कहां डालने की सूची है, जिसके परिणामस्वरूप सूची अभी भी क्रम में होगी।

हालांकि एल .insert (अनुक्रमणिका, वस्तु) को ओ (एन) समय जटिलता की आवश्यकता है।

क्या एल के लिए एक और डेटा संरचना है जो एक ही उद्देश्य की सेवा करेगी, लेकिन तेजी से सम्मिलन की अनुमति देगी?

Answer 1

ब्लिस्ट मॉड्यूल देखें।

https://pypi.python.org/pypi/blist/

यह हे (लॉग एन) प्रविष्टि दावा करता है।

उपयोग:

x = #list contents 
y = blist(x) 
y.insert(index, object) #now works in O(log n) 

Answer 2

sortedcontainers.SortedList के लिए बाहर एक चिल्लाओ। यह तेजी से सम्मिलित समय के साथ, आपकी सूची स्वचालित रूप से क्रम में रखेगा।

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, लेकिन यह blist, जो O(log n) है की तुलना में बेहतर मापता है, क्योंकि स्थिरांक ज्यादा बेहतर कर रहे हैं। a very in-depth look at performance on their website है।

वैकल्पिक रूप से, आप priority queue चाहते हैं, इस मामले में आप the heapq module के साथ संभावित रूप से तेज़ी से आवेषण प्राप्त कर सकते हैं।