पायथन में सूचियों की तुलना में सेट तेजी से क्या बनाता है?

Question

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

जब भी मेरे कोड में गति महत्वपूर्ण होती है, तो मैं सूचियों के स्थान पर सेट का उपयोग कर रहा हूं, लेकिन हाल ही में मैं सोच रहा हूं कि सेट सूचियों से इतनी तेज क्यों हैं। क्या कोई मुझे समझा सकता है, या मुझे उस स्रोत पर इंगित कर सकता है जो समझाएगा, सेट को तेज बनाने के लिए पाइथन में दृश्यों के पीछे क्या चल रहा है?

Answer 1

सेट hash tables का उपयोग करके लागू किए गए हैं। जब भी आप किसी ऑब्जेक्ट को किसी सेट में जोड़ते हैं, तो set ऑब्जेक्ट की स्मृति के भीतर स्थिति को ऑब्जेक्ट के हैश का उपयोग करके निर्धारित किया जाता है। सदस्यता के लिए परीक्षण करते समय, जो कुछ करने की ज़रूरत है वह मूल रूप से यह देखने के लिए है कि वस्तु उसके हैश द्वारा निर्धारित स्थिति पर है, इसलिए इस ऑपरेशन की गति सेट के आकार पर निर्भर नहीं है। सूचियों के लिए, इसके विपरीत, पूरी सूची को खोजना आवश्यक है, जो सूची बढ़ने के साथ धीमा हो जाएगा।

यह भी कारण है कि सेट आपके द्वारा जोड़े गए ऑब्जेक्ट्स के क्रम को सुरक्षित नहीं करते हैं।

ध्यान दें कि सेट सामान्य रूप से सूचियों से तेज़ नहीं हैं - सदस्यता परीक्षण सेट के लिए तेज़ है, और इसलिए तत्व को हटा रहा है। जब तक आपको इन परिचालनों की आवश्यकता नहीं है, सूचियां अक्सर तेज़ी से होती हैं।

Answer 2

पायथन hashtables का उपयोग करता है, जिसमें ओ (1) लुकअप है।

Answer 3

मुझे लगता है कि आपको डेटा संरचनाओं पर एक पुस्तक पर एक अच्छी नजर डालने की आवश्यकता है। असल में, पायथन सूची dynamic arrays के रूप में लागू की जाती है और सेट hash tables के रूप में लागू किए जाते हैं।

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

Answer 4

एक सूची को एक-एक करके खोजा जाना चाहिए, जहां एक सेट या डिक्शनरी में तेजी से खोज के लिए एक अनुक्रमणिका है।

Answer 5

list: कल्पना कीजिए कि आप अपने कोठरी में अपने मोजे के लिए देख रहे हैं, लेकिन आप जिसमें दराज अपने मोजे हैं पता नहीं है, तो आप दराज से दराज खोज जब तक आप उन्हें (खोजने के लिए या शायद आप ऐसा कभी नहीं)। यही वह है जिसे हम O(n) कहते हैं, क्योंकि सबसे खराब परिदृश्य में, आप अपने सभी दराजों में देखेंगे (जहां n दराजों की संख्या है)।

set: अब, कल्पना आप अभी भी अपने कोठरी में अपने मोजे के लिए देख रहे हैं, लेकिन अब तुम्हें पता है, जिसमें दराज अपने मोजे हैं, 3 दराज में कहते हैं। तो, आप सभी दराजों में खोज करने के बजाय, केवल तीसरे दराज में खोज करेंगे। यही वह है जिसे हम O(1) कहते हैं, क्योंकि सबसे खराब परिदृश्य में आप केवल एक दराज में देखेंगे।

Answer 6

जबकि मैंने अभी तक अजगर में कुछ भी प्रदर्शन नहीं किया है, फिर भी मैं यह इंगित करना चाहता हूं कि सूचियां अक्सर तेज़ी से होती हैं।

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

तो सेट प्रति से सूचियों से तेज़ नहीं हैं, लेकिन केवल तभी यदि आपको बहुत से तत्वों को संभालना है।