python - पायथन: डेक बनाम सूची प्रदर्शन तुलना




performance data-structures (2)

इसका क्या मूल्य है:

> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop

> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop

> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop

> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop

जैसा कि आप देख सकते हैं, जहां यह वास्तव में चमकता है, appendleft बनाम insert

पायथन डॉक्स में मैं देख सकता हूं कि डेक एक विशेष संग्रह है जो बाएं या दाएं किनारों से वस्तुओं को पॉप / जोड़ने के लिए अत्यधिक अनुकूल है। जैसे दस्तावेज कहता है:

डेक्स स्टैक्स और कतारों का एक सामान्यीकरण है (नाम "डेक" कहा जाता है और "डबल-एंडेड कतार" के लिए छोटा होता है)। Deques समर्थन थ्रेड-सुरक्षित, स्मृति कुशल परिशिष्ट और डेक के दोनों तरफ से पॉप को किसी भी दिशा में लगभग उसी ओ (1) प्रदर्शन के साथ समर्थन करता है।

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

मैंने ipython का उपयोग करके कुछ तुलना करने का फैसला किया। क्या कोई मुझे बता सकता है कि मैंने यहां क्या किया है:

In [31]: %timeit range(1, 10000).pop(0)
 10000 loops, best of 3: 114 us per loop

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop

In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop

Could anyone explain me what I did wrong here

हां, आपका समय सूची या डेक बनाने के लिए समय पर प्रभुत्व है। पॉप करने का समय तुलना में महत्वहीन है।

इसके बजाय आपको उस समय को अलग करना चाहिए जिसे आप परीक्षण समय से (पॉप स्पीड) परीक्षण करने का प्रयास कर रहे हैं:

In [1]: from collections import deque

In [2]: s = range(1000)

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

उस ने कहा, प्रदर्शन के संदर्भ में डेक्स और सूची के बीच वास्तविक मतभेद हैं:

  • डेक्स में ओ (1) एपेंडैबल () और पॉपलफ्ट ( ) की गति होती है जबकि सूचियों में ओ (एन) प्रदर्शन (0, मान) और पॉप (0) के लिए प्रदर्शन होता है

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





deque