सेट और सूचियों के संबंध में लेन() की जटिलता

Question

सेट और सूचियों के संबंध में len() की जटिलता समान रूप से ओ (1) है। सेट को संसाधित करने में अधिक समय लगता है?

~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)" 
10000000 loops, best of 3: 0.168 usec per loop 
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)" 
1000000 loops, best of 3: 0.375 usec per loop 

यह विशेष बेंचमार्क से संबंधित है, के रूप में, यह सूचियों से सेट का निर्माण करने के लिए और अधिक समय लगता है और मानक के रूप में अच्छी तरह से ध्यान में रखा जाता है?

यदि किसी सेट ऑब्जेक्ट के निर्माण की सूची बनाने की तुलना में अधिक समय लगता है, तो अंतर्निहित कारण क्या होगा?

Answer 1

सबसे पहले, आप len() की गति से मापा नहीं है, तो आप मापा जाता है एक सूची बनाने की गति/एक साथ सेटlen() की गति के साथ।

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)" 
10000000 loops, best of 3: 0.0369 usec per loop 
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)" 
10000000 loops, best of 3: 0.0372 usec per loop 

बयान आप --setup को पारित len() की गति को मापने से पहले चलाए जा रहे हैं:

timeit की --setup तर्क का प्रयोग करें।

दूसरा, आपको ध्यान रखना चाहिए कि len(a) एक बहुत तेज़ कथन है। इसकी गति को मापने की प्रक्रिया "शोर" के अधीन हो सकती है। विचार करें कि the code executed (and measured) by timeit निम्नलिखित के बराबर है:

for i in itertools.repeat(None, number): 
    len(a) 

क्योंकि len(a) और itertools.repeat(...).__next__() दोनों तेजी से संचालन कर रहे हैं और उनकी गति समान हो सकता है, itertools.repeat(...).__next__() की गति समय को प्रभावित कर सकते।

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)" 
10000 loops, best of 3: 29.2 usec per loop 
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)" 
10000 loops, best of 3: 29.3 usec per loop 

(परिणाम:

इस कारण से, आप बेहतर ढंग से माप len(a); len(a); ...; len(a) (100 बार या तो बार-बार) ताकि पाश के लिए के शरीर इटरेटर से समय की एक काफी अधिक राशि लेता चाहते अभी भी कहना है कि len() सूचियों और सेट पर ही प्रदर्शन किया है, लेकिन अब आप यह सुनिश्चित करें कि परिणाम सही है कर रहे हैं।)

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

इसका मतलब है कि, औसत पर, कोई फर्क नहीं पड़ता कि सूची a कितनी देर तक है, len(a) समान एसिम्पटोटिक संख्याओं को निष्पादित करता है। और कोई फर्क नहीं पड़ता कि सेट b कितना समय है, len(b) एक ही एसिम्प्टोटिक संख्याओं का पालन करता है। लेकिन सूचियों और सेटों के आकार की गणना करने के लिए एल्गोरिदम भिन्न हो सकता है, जिसके परिणामस्वरूप अलग-अलग प्रदर्शन होते हैं (टाइमिट दिखाता है कि यह मामला नहीं है, हालांकि यह एक संभावना हो सकती है)।

अन्त में,

एक सेट वस्तु के निर्माण के लिए और अधिक समय सूची तैयार की तुलना में लेता है, क्या अन्तर्निहित कारण हो सकता है?

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

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

Answer 2

हां, आप सही हैं, यह set और list ऑब्जेक्ट्स को पायथन द्वारा बनाने के लिए आवश्यक विभिन्न समय के कारण अधिक है। एक न्यायपूर्ण मानक के रूप में आप timeit मॉड्यूल का उपयोग और setup तर्क का उपयोग वस्तुओं पारित कर सकते हैं:

from timeit import timeit 

print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)") 
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000") 

परिणाम:

1st: 0.04927110672 
2nd : 0.0530669689178 

और आप जानना चाहते कारण है कि यह इतना तरह है, देता है कि अजगर के माध्यम से जाना चाहते हैं, तो विश्व। वास्तव में ऑब्जेक्ट को hash table का उपयोग करें और एक हैश तालिका आइटम के हैश मान बनाने और उन्हें मानों पर मैप करने के लिए हैश फ़ंक्शन का उपयोग करती है और इस सौदे में फ़ंक्शन को कॉल करने और हैश मानों की गणना करने और कुछ अन्य अतिरिक्त कार्यों में अधिक समय लगेगा। एक सूची पायथन बनाने के लिए बस ऑब्जेक्ट्स के अनुक्रम बनाएँ जो आप उन्हें अनुक्रमण के साथ एक्सेस कर सकते हैं।

Cpython source code से set_lookkey फ़ंक्शन पर आप अधिक जानकारी देख सकते हैं।

यह भी ध्यान दें कि यदि दो एल्गोरिदम में समान जटिलता है तो इसका मतलब यह नहीं है कि दोनों एल्गोरिदम में एक ही रन टाइम या निष्पादन गति है।

---

_{क्योंकि big O अंकन limiting behavior of a function वर्णन करता है और सटीक जटिलता समीकरण नहीं दिखाती है। उदाहरण के लिए निम्नलिखित समीकरणों की जटिलता f(x)=100000x+1 और f(x)=4x+20 ओ (1) है और इसका मतलब है कि दोनों रैखिक समीकरणों के रूप में हैं क्योंकि आप देख सकते हैं कि पहले फ़ंक्शन में एक बहुत बड़ी ढलान है, और एक ही इनपुट के लिए वे अलग-अलग परिणाम देंगे ।}

Answer 3

len(a) बयान निकालें। नतीजा काफी समान है। केवल एक सेट को बनाए रखने के लिए एक सेट को धोने की जरूरत है ताकि यह धीमा हो।

Answer 4

प्रासंगिक लाइनों http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640

640  static Py_ssize_t 
641  set_len(PyObject *so) 
642  { 
643   return ((PySetObject *)so)->used; 
644  } 

और http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431

431  static Py_ssize_t 
432  list_length(PyListObject *a) 
433  { 
434   return Py_SIZE(a); 
435  } 

दोनों कर रहे हैं केवल एक स्थिर देखने हैं।

तो आप क्या अंतर पूछ सकते हैं। आप वस्तुओं के निर्माण को भी मापते हैं। और यह एक सूची से एक सेट बनाने के लिए थोड़ा और समय लेने वाला है।

Answer 5

उपयोग इस बिना timeit के खाते में पहली स्ट्रिंग ले रही है:

~$ python -mtimeit -s "a=range(1000);" "len(a)" 
10000000 loops, best of 3: 0.0424 usec per loop 
          ↑ 

---

~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)" 
10000000 loops, best of 3: 0.0423 usec per loop 
          ↑ 

अब यह केवल केवल len समारोह पर विचार कर रहा है, और परिणाम काफी हैं वैसे ही हमने सेट/सूची के निर्माण समय को ध्यान में नहीं रखा है।

Answer 6

मुझे उत्कृष्ट उत्तरों को यहां प्रस्तुत करने दें: O(1) केवल इनपुट के आकार के संबंध में आपको order of growth के बारे में बताता है।

O(1) विशेष रूप से केवल निरंतर समय इनपुट के आकार के संबंध मेंका मतलब है। एक विधि हमेशा 0.1s लग सकता है, किसी भी इनपुट के लिए, और एक अन्य किसी भी इनपुट के लिए 1000 साल लग सकते हैं, और वे दोनों O(1)

इस मामले में होगी, जबकि प्रलेखन अस्पष्टता के कुछ डिग्री है, यह इसका मतलब यह है कि विधि आकार 1 की सूची को संसाधित करने के लिए लगभग उसी समय ले जाती है क्योंकि यह आकार 1000 की सूची को संसाधित करने के लिए लेता है; इसी तरह, आकार 1 के शब्दकोश को संसाधित करने में एक ही समय लगता है क्योंकि यह 1000 आकार के शब्दकोश को संसाधित करने में लग रहा है।

विभिन्न डेटा प्रकारों के संबंध में कोई गारंटी नहीं दी जाती है।

यह किसी भी समय कॉल स्टैक के नीचे डेटा प्रकार के आधार पर भिन्न हो सकता है, len() के कार्यान्वयन के बाद यह असंतोषजनक है।

संयोग से, इस अस्पष्टता स्थिर टाइप किया भाषाओं जहां ClassA.size() और ClassB.size() सभी उद्देश्यों के लिए कर रहे हैं और दो अलग अलग तरीकों purpouses में समाप्त हो रहा है।

Answer 7

कई ने कहा है कि हे (1) विभिन्न डेटा प्रकार पर प्रदर्शन के बारे में नहीं है, लेकिन अलग अलग इनपुट के एक समारोह के रूप में प्रदर्शन के बारे में आकार।

आप हे (1) -नेस परीक्षण करने के लिए कोशिश कर रहे हैं, तो आप अधिक

~$python -m timeit --setup "a=list(range(1000000))" "len(a)" 
10000000 loops, best of 3: 0.198 usec per loop 

~$python -m timeit --setup "a=list(range(1))" "len(a)" 
10000000 loops, best of 3: 0.156 usec per loop 

बिग डेटा या कम डेटा की तरह कुछ के लिए विचार करना होता है, समय लिया काफी समान है। अन्य पोस्टों के अनुसार, यह सेटअप समय को परीक्षण समय से अलग करता है, लेकिन लैन-टाइम बनाम लूप-टाइम के शोर को कम करने के लिए नहीं जाता है।