पायथन में क्रमबद्ध सूची में खोज क्यों अधिक समय लेती है?

Question

मैंने एक प्रयोग किया जिसमें मैंने एक पायथन सूची खोजने के लिए समय निकालने का प्रयास किया। मेरे पास यादृच्छिक पूर्णांक के साथ arr सूची है। arr_s में वही तत्व हैं जो क्रमबद्ध हैं।

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

अब मैं पूर्णांकों find जो तत्व है कि मैं arr और arr_s में खोज करना चाहते है के एक यादृच्छिक सरणी पैदा करते हैं।

>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr: 
...:  continue 

[OUT]:100 loops, best of 3: 2.18 ms per loop 


>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr_s: 
...:  continue 

[OUT]:100 loops, best of 3: 5.15 ms per loop 

अब मैं समझता हूँ कि मैं अनुसार क्रमबद्ध सरणी में खोज करने के लिए कोई विशेष विधि का इस्तेमाल नहीं किया है (उदाहरण के लिए द्विआधारी खोज)। तो यह मानक रैखिक खोज कर रहा है लेकिन सॉर्ट किए गए सरणी में सॉर्ट किए गए सरणी में खोज करने में काफी समय लगता है? मुझे लगता है कि इसे लगभग एक ही समय लेना चाहिए। मैंने find सरणी के सभी प्रकार की कोशिश की है। Arrays जिसमें (0, 1000), (-1000, -100) और (-10000, 10000) से पूर्णांक होते हैं, लूप हमेशा क्रमबद्ध सरणी के लिए अधिक समय लेते हैं।

Answer 1

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

arr एक सरणी है। arr_s एक सूची है। किसी सरणी को खोजना कुशलतापूर्वक संभालकर संभाला जा सकता है, लेकिन सूची खोजने के लिए निम्नलिखित पॉइंटर्स और प्रदर्शन प्रकार की जांच की आवश्यकता होती है। छंटनी के साथ इसका कोई लेना-देना नहीं है।

नोट: in does weird things in numpy.in का उपयोग numpy ndarrays के साथ एक बुरा विचार हो सकता है।

Answer 2

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

इस मामले में, मेरा अनुमान है कि सूची को सॉर्ट करने का कार्य अंतर्निहित संगठन को बदलता है, जिससे तत्वों तक पहुंचने में कुछ हद तक कम कुशल होता है।

Answer 3

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

    In [9]: it = arr.__iter__() 
    In [10]: its = arr_s.__iter__() 
    In [11]: type(it) 
    Out[11]: iterator 
    In [12]: type(its) 
    Out[12]: listiterator 

वे स्पष्ट रूप से दो अलग-अलग पुनरावृत्तियों का उपयोग करते हैं जो गति में अंतर को समझा सकते हैं।