कोई भी इस पायथन डेटा संरचना को जानता है?

Question

पायथन कक्षा में नीचे सूचीबद्ध अनुसार छह आवश्यकताएं हैं। केवल बोल्ड शब्द आवश्यकताओं के रूप में पढ़ा जाना है।

---

को हे (1) के बाद के चार आपरेशन के रूप में कई के लिए प्रदर्शन बंद
1. ।
2. को कंटेनर में एक ऑब्जेक्ट डालने के दौरान सॉर्ट किए गए क्रम को बनाए रखना।
3. की क्षमता पिछले मूल्य (वस्तु का सबसे बड़ा मूल्य) पर अंकित है।
4. के लिए अनुमति देना दोनों तरफ (सबसे छोटे या सबसे बड़े मूल्य प्राप्त करना) पर पॉप करता है।
5. की क्षमता कुल आकार या संग्रहीत वस्तुओं की संख्या प्राप्त करने की क्षमता।
6. तैयार किए गए समाधान पायथन के मानक पुस्तकालय में कोड की तरह।

---

इस प्रकार क्या ऐतिहासिक कारणों के लिए यहाँ छोड़ दिया है (उत्सुक मदद और साबित होता है कि अनुसंधान का आयोजन किया गया था)।

---

पायथन के मानक लाइब्रेरी (विशेष रूप से डेटा प्रकार पर खंड) के माध्यम से देखने के बाद, मैं अभी भी एक वर्ग है कि एक विखंडन तालिका की आवश्यकताओं आवश्यकताओं को पूरा नहीं मिली है। collections.deque जो आवश्यक है उसके करीब है, लेकिन यह सॉर्ट किए गए डेटा को रखने में सहायता नहीं करता है। यह प्रदान करता है:

1. कुशल संलग्न और हे (1) प्रदर्शन के साथ एक Deque के दोनों तरफ पॉप्स।
2. ऑब्जेक्ट के भीतर मौजूद डेटा के लिए दोनों तरफ पर पॉप।
3. कुल आकार या भीतर मौजूद वस्तुओं की गणना प्राप्त करना।

सूचियों का उपयोग करके एक अक्षम समाधान को कार्यान्वित करना मामूली होगा, लेकिन अच्छी तरह से प्रदर्शन करने वाली कक्षा को ढूंढना कहीं अधिक वांछनीय होगा। ऊपरी सीमा के साथ बढ़ती स्मृति सिमुलेशन में, ऐसी कक्षा खाली (हटाए गए) कोशिकाओं की अनुक्रमणिका रख सकती है और विखंडन स्तर को नीचे रख सकती है। bisect मॉड्यूल मदद मिल सकती है:

1. अनुसार क्रमबद्ध क्रम में एक सरणी रखने जबकि सरणी में नई वस्तुओं डालने में मदद करता है।
2. तैयार किए गए समाधान वस्तुओं को क्रमबद्ध सूचियों को रखने के लिए जोड़े गए हैं।
3. सरणी में पर अंतिम मूल्य पर array[-1] से निष्पादित करने की अनुमति देगा।

अंतिम उम्मीदवार जो आवश्यकताओं को पूरी तरह से पूरा करने में असफल रहा और कम से कम आशाजनक दिखाई दिया heapq मॉड्यूल था। कुशल प्रविष्टियों की तरह दिखने और यह सुनिश्चित करने के दौरान कि array[0] सबसे छोटा मूल्य था, सरणी हमेशा पूरी तरह से क्रमबद्ध स्थिति में नहीं होती है। सहायक के रूप में कुछ भी नहीं मिला था।

---

किसी अजगर में कक्षा या डेटा संरचना का पता है कि आता है करीब इन छह आवश्यकताओं के लिए?

Answer 1

बहुत धन्यवाद प्रेरणा है जो निम्न अजगर वर्ग के लिए नेतृत्व प्रदान करने के लिए katrielalex के लिए बाहर जाना:

import collections 
import bisect 

class FastTable: 

    def __init__(self): 
     self.__deque = collections.deque() 

    def __len__(self): 
     return len(self.__deque) 

    def head(self): 
     return self.__deque.popleft() 

    def tail(self): 
     return self.__deque.pop() 

    def peek(self): 
     return self.__deque[-1] 

    def insert(self, obj): 
     index = bisect.bisect_left(self.__deque, obj) 
     self.__deque.rotate(-index) 
     self.__deque.appendleft(obj) 
     self.__deque.rotate(index) 

Answer 2

आपका आवश्यकताओं होने लगते हैं:

1. हे (1) प्रत्येक के अंत
2. कुशल len
3. छाँटे गए आदेश से पॉप
जिसके लिए अंतिम मान

पर

पीक आप कस्टम insert विधि के साथ deque का उपयोग कर सकते हैं जो डेक को घुमाता है, एक अंत में जोड़ता है , और unrotates।

>>> from collections import deque 
>>> import bisect 
>>> class FunkyDeque(deque): 
...  def _insert(self, index, value): 
...    self.rotate(-index) 
...    self.appendleft(value) 
...    self.rotate(index) 
... 
...  def insert(self, value): 
...    self._insert(bisect.bisect_left(self, value), value) 
... 
...  def __init__(self, iterable): 
...    super(FunkyDeque, self).__init__(sorted(iterable)) 
... 
>>> foo = FunkyDeque([3,2,1]) 
>>> foo 
deque([1, 2, 3]) 
>>> foo.insert(2.5) 
>>> foo 
deque([1, 2, 2.5, 3]) 

सूचना है कि आवश्यकताओं को 1, 2, और 4 सब तथ्य यह है कि अंतर्निहित डेटा संरचना एक Deque है, और आवश्यकता 3 क्योंकि जिस तरह से डेटा डाला जाता है की धारण से सीधे का पालन करें। (बेशक ध्यान दें कि आप जैसे _insert फोन करके छंटाई आवश्यकता को बायपास कर सकता, लेकिन उस समय के बगल में है।)

Answer 3

blist.sortedlist

हे (1) के बाद के चार आपरेशन के रूप में कई के लिए प्रदर्शन करने के लिए बंद
1. ।
2. कंटेनर में ऑब्जेक्ट डालने के दौरान सॉर्ट किए गए क्रम को बनाए रखना।
3. वस्तु में निहित अंतिम मूल्य (सबसे बड़ा मूल्य) पर देखने की क्षमता।
4. दोनों तरफ से पॉप के लिए अनुमति देना (सबसे छोटा या सबसे बड़ा मूल्य प्राप्त करना)।
5. कुल आकार या संग्रहित वस्तुओं की संख्या प्राप्त करने की क्षमता।
6. पायथन की मानक लाइब्रेरी में कोड जैसे तैयार किए गए समाधान होने के नाते।

यह एक बी + वृक्ष है।