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




python-3.x time-complexity (5)

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

यदि आप O (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

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

सेट और सूचियों के संबंध में len() की जटिलता समान रूप से O (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

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

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


पहली स्ट्रिंग को ध्यान में रखते हुए समय -s ध्वज के साथ इसका उपयोग करें:

~$ 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 फ़ंक्शन पर विचार कर रहा है, और परिणाम बहुत समान हैं क्योंकि हमने सेट / सूची के निर्माण समय को ध्यान में नहीं रखा था।


संबंधित लाइनें 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     }

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

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


हां, आप सही हैं, यह अजगर द्वारा 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

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

आप http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640 से http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640 फ़ंक्शन पर अधिक विवरण देख सकते हैं।

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

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


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

--setup के --setup तर्क का उपयोग करें:

$ 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 की गति को मापने से पहले आपके द्वारा पास किए गए कथन --setup पर चलाए --setup हैं।

दूसरे, आपको ध्यान देना चाहिए कि len(a) एक बहुत जल्दी बयान है। इसकी गति को मापने की प्रक्रिया "शोर" के अधीन हो सकती है। विचार करें कि टाइमिट द्वारा निष्पादित कोड (और मापा गया) निम्न के बराबर है:

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

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

इस कारण से, आप बेहतर तरीके से len(a); len(a); ...; len(a) मापेंगे len(a); len(a); ...; len(a) len(a); len(a); ...; len(a) len(a); len(a); ...; len(a) (बार-बार 100 बार या इससे अधिक) ताकि लूप के लिए शरीर खुजली की तुलना में काफी अधिक समय लेता है:

$ 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() पास सूचियों और सेटों पर समान प्रदर्शन हैं, लेकिन अब आप सुनिश्चित हैं कि परिणाम सही है।)

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

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

अंततः,

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

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

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






python-internals