ओ (1) पायथन

Question

में पूर्णांक के सूचकांक डेक वहाँ मेरे विकल्प क्या हैं? मुझे append एस (दाएं छोर पर) और popleft एस (बाएं सिरे से, स्वाभाविक रूप से) पर कॉल करने की आवश्यकता है, लेकिन स्टोरेज के बीच से भी पढ़ने के लिए, जो एल्गोरिदम की प्रकृति द्वारा लगातार बढ़ेगा। मैं इन सभी परिचालनों को O(1) में रखना चाहता हूं।

मैं इसे सर्कुलरली-एड्रेस किए गए सरणी (शब्द क्या है?) पर पर्याप्त आसान सी में कार्यान्वित कर सकता है जो पूर्ण होने पर स्वचालित रूप से बढ़ेगा; लेकिन पाइथन के बारे में क्या? अन्य भाषाओं के पॉइंटर्स की भी सराहना की जाती है (मुझे एहसास है कि "संग्रह" टैग अधिक जावा इत्यादि उन्मुख है और तुलना की सराहना करता है, लेकिन द्वितीयक लक्ष्य के रूप में)।

मैं एक लिस्प पृष्ठभूमि से आया हूं और यह जानने के लिए आश्चर्यचकित था कि पाइथन में एक सूची से एक प्रमुख तत्व को हटाने में O(n) ऑपरेशन है। एक deque दस्तावेज को छोड़कर एक जवाब हो सकता है कि मध्य में मध्य में O(n) पहुंच है। क्या कुछ और है, पूर्व निर्मित?

Answer 1

आप दो पायथन सूचियों का उपयोग कर एक अमूर्त ओ (1) डेटा संरचना प्राप्त कर सकते हैं, जिसमें डेक के बाएं आधे हिस्से को पकड़ा जा सकता है और दूसरा सही आधा होल्डिंग कर सकता है। सामने के आधे को उलट दिया जाता है ताकि डेक के बाएं सिरे को सूची के पीछे रखा जा सके। कुछ इस तरह:

class mydeque(object): 

    def __init__(self): 
    self.left = [] 
    self.right = [] 

    def pushleft(self, v): 
    self.left.append(v) 

    def pushright(self, v): 
    self.right.append(v) 

    def popleft(self): 
    if not self.left: 
     self.__fill_left() 
    return self.left.pop() 

    def popright(self): 
    if not self.right: 
     self.__fill_right() 
    return self.right.pop() 

    def __len__(self): 
    return len(self.left) + len(self.right) 

    def __getitem__(self, i): 
    if i >= len(self.left): 
     return self.right[i-len(self.left)] 
    else: 
     return self.left[-(i+1)] 

    def __fill_right(self): 
    x = len(self.left)//2 
    self.right.extend(self.left[0:x]) 
    self.right.reverse() 
    del self.left[0:x] 

    def __fill_left(self): 
    x = len(self.right)//2 
    self.left.extend(self.right[0:x]) 
    self.left.reverse() 
    del self.right[0:x] 

मैं 100% यकीन है कि अगर इस कोड और अजगर की सूचियों का परिशोधित प्रदर्शन के बीच बातचीत वास्तव में एक ऑपरेशन के लिए हे (1) में परिणाम नहीं कर रहा हूँ, लेकिन मेरे पेट इतना कहते हैं।

Answer 2

लिस्प सूची के बीच तक पहुंचने से ओ (एन) भी है।

पायथन list एस सरणी सूचियां हैं, यही कारण है कि सिर popping महंगा है (पूंछ स्थिर समय है)।

जो आप खोज रहे हैं वह सरणी (निरंतर) सिर पर निरंतर समय हटाने के साथ एक सरणी है; इसका मूल रूप से मतलब है कि आपको list के शीर्ष पर एक डेटास्ट्रक्चर बनाना होगा जो आलसी हटाने का उपयोग करता है, और कतार खाली होने पर आलसी-हटाए गए स्लॉट को रीसायकल करने में सक्षम है।

वैकल्पिक रूप से, एक हैशटेबल का उपयोग करें, और कुछ पूर्णांक कुंजी की वर्तमान संगत श्रृंखला का ट्रैक रखने के लिए।

Answer 3

Python's Queue Module आपकी मदद कर सकता है, हालांकि मुझे यकीन नहीं है कि पहुंच O(1) है या नहीं।