एक पायथन सूची का उपयोग कतार

Question

के रूप में करने की क्षमता एक सहकर्मी ने हाल ही में एक कार्यक्रम लिखा जिसमें उन्होंने एक पायथन सूची को कतार के रूप में उपयोग किया। दूसरे शब्दों में, आइटमों को हटाने की आवश्यकता होने पर आइटम और .pop(0) डालने की आवश्यकता होने पर उन्होंने .append(x) का उपयोग किया।

मुझे पता है कि पायथन के पास collections.deque है और मैं यह पता लगाने की कोशिश कर रहा हूं कि इस कोड को पुनः उपयोग करने के लिए मेरे (सीमित) समय को फिर से लिखना है या नहीं। यह मानते हुए कि हम लाखों परिशिष्ट और पॉप करते हैं लेकिन कुछ हज़ार प्रविष्टियों से अधिक नहीं है, क्या उनकी सूची उपयोग एक समस्या होगी?

विशेष रूप से, अंतर्निहित अजगर सूची कार्यान्वयन द्वारा प्रयोग किया जाता सरणी अनिश्चित काल के लिए विकसित करने के लिए भले ही इस सूची में केवल एक हजार बातें है स्पॉट के लाखों लोगों की है जारी रहेगा, या अजगर अंततः एक realloc और नि: शुल्क है कि स्मृति के कुछ क्या करेंगे?

Answer 1

आप list कार्यान्वयन का उपयोग कर स्मृति से बाहर नहीं होंगे, लेकिन प्रदर्शन खराब होगा। the docs से:

list हालांकि वस्तुओं समान कार्य का समर्थन, वे तेजी से निश्चित लंबाई के संचालन के लिए अनुकूलित और pop(0) और insert(0, v) संचालन जो दोनों का आकार बदलने के लिए हे (एन) स्मृति आंदोलन शुल्क देना पड़ रहे हैं और अंतर्निहित डेटा प्रतिनिधित्व की स्थिति स्थिति।

तो deque का उपयोग करना बहुत तेज़ होगा।

Answer 2

ऐसा लगता है कि कुछ अनुभवजन्य परीक्षण यहां करना सबसे अच्छा काम हो सकता है - दूसरा ऑर्डर समस्या अभ्यास में एक दृष्टिकोण बेहतर कर सकती है, भले ही यह सिद्धांत में बेहतर न हो।

Answer 3

प्रत्येक .pop(0) एन कदम उठाता है, क्योंकि सूची को पुनर्गठित किया जाना है। आवश्यक स्मृति अंतहीन रूप से नहीं बढ़ेगी और केवल उन वस्तुओं के लिए आवश्यक जितनी बड़ी होगी।

मैं ओ (1) संलग्न करने और सामने से पॉप प्राप्त करने के लिए deque का उपयोग करने की सलाह दूंगा।

Answer 4

कुछ उत्तर Deque बनाम सूची से इस्तेमाल के रूप में फीफो दोनों 1000 प्रविष्टियों है जब, लेकिन यह एक overbid का एक सा के लिए एक "10x" गति लाभ का दावा किया:

$ python -mtimeit -s'q=range(1000)' 'q.append(23); q.pop(0)' 
1000000 loops, best of 3: 1.24 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(1000))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.573 usec per loop 

python -mtimeit अपने दोस्त है - वास्तव में उपयोगी और सरल माइक्रो-बेंचमार्किंग दृष्टिकोण! इसके साथ आप निश्चित रूप से भी तुच्छता प्रदर्शन बहुत छोटे मामलों में तलाश कर सकते हैं:

$ python -mtimeit -s'q=range(100)' 'q.append(23); q.pop(0)' 
1000000 loops, best of 3: 0.972 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(100))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.576 usec per loop 

, और भी बहुत-बड़ों में (बहुत btw 12 100 के बजाय मदों के लिए अलग नहीं):

$ python -mtimeit -s'q=range(10000)' 'q.append(23); q.pop(0)' 
100000 loops, best of 3: 5.81 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(10000))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.574 usec per loop 

आप देख सकते हैं कि डेक के लिए ओ (1) प्रदर्शन का दावा अच्छी तरह से स्थापित किया गया है, जबकि एक सूची 1000 वस्तुओं के चारों ओर धीमी है, जो लगभग 10,000 के आयाम का क्रम है। आप यह भी देख सकते हैं कि यहां तक ​​कि ऐसे मामलों में आप केवल 5 माइक्रोसॉन्ड बर्बाद कर रहे हैं या प्रति संलग्न/पॉप जोड़ी बर्बाद कर रहे हैं और यह तय कर सकते हैं कि बर्बादी कितनी महत्वपूर्ण है (हालांकि अगर आप उस कंटेनर के साथ ऐसा कर रहे हैं, तो डेक में कोई नकारात्मकता नहीं है, इसलिए आप 5 स्विचक कम या ज्यादा एक महत्वपूर्ण अंतर नहीं होने पर भी स्विच कर सकते हैं)।

Answer 5

बेज़ले के Python Essential Reference, Fourth Edition से, पी। 194:

कुछ पुस्तकालय मॉड्यूल नए प्रकार कि मात कुछ कार्यों में बनाया-इन प्रदान करते हैं। उदाहरण के लिए, collections.deque प्रकार एक सूची के लिए समान कार्यक्षमता प्रदान करता है लेकिन को दोनों सिरों पर आइटम सम्मिलित करने के लिए अत्यधिक अनुकूलित किया गया है। इसके विपरीत, सूची, अंत में आइटम को जोड़ते समय केवल कुशल है। यदि आप सामने वाले आइटम डालते हैं, तो सभी तत्वों को कमरे बनाने के लिए स्थानांतरित करने की आवश्यकता है। को यह करने की आवश्यकता है क्योंकि सूची बड़ी और बड़ी हो जाती है। बस आप अंतर की एक विचार देने के लिए, यहाँ एक सूची के सामने और एक Deque में एक लाख आइटम डालने के समय माप है:

और यह कोड नमूना वहाँ इस प्रकार है:

>>> from timeit import timeit 
>>> timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=1000000) 
0.13162776274638258 
>>> timeit('s.insert(0,37)', 's = []', number=1000000) 
932.07849908298408 

समय मेरी मशीन से हैं।

---

2012-07-01 अपडेट

>>> from timeit import timeit 
>>> n = 1024 * 1024 
>>> while n > 1: 
...  print '-' * 30, n 
...  timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=n) 
...  timeit('s.insert(0,37)', 's = []', number=n) 
...  n >>= 1 
... 
------------------------------ 1048576 
0.1239769458770752 
799.2552740573883 
------------------------------ 524288 
0.06924104690551758 
148.9747350215912 
------------------------------ 262144 
0.029170989990234375 
35.077512979507446 
------------------------------ 131072 
0.013737916946411133 
9.134140014648438 
------------------------------ 65536 
0.006711006164550781 
1.8818109035491943 
------------------------------ 32768 
0.00327301025390625 
0.48307204246520996 
------------------------------ 16384 
0.0016388893127441406 
0.11021995544433594 
------------------------------ 8192 
0.0008249282836914062 
0.028419017791748047 
------------------------------ 4096 
0.00044918060302734375 
0.00740504264831543 
------------------------------ 2048 
0.00021195411682128906 
0.0021741390228271484 
------------------------------ 1024 
0.00011205673217773438 
0.0006101131439208984 
------------------------------ 512 
6.198883056640625e-05 
0.00021386146545410156 
------------------------------ 256 
2.9087066650390625e-05 
8.797645568847656e-05 
------------------------------ 128 
1.5974044799804688e-05 
3.600120544433594e-05 
------------------------------ 64 
8.821487426757812e-06 
1.9073486328125e-05 
------------------------------ 32 
5.0067901611328125e-06 
1.0013580322265625e-05 
------------------------------ 16 
3.0994415283203125e-06 
5.9604644775390625e-06 
------------------------------ 8 
3.0994415283203125e-06 
5.0067901611328125e-06 
------------------------------ 4 
3.0994415283203125e-06 
4.0531158447265625e-06 
------------------------------ 2 
2.1457672119140625e-06 
2.86102294921875e-06