दिलचस्प पोस्ट
एक एपीके फ़ाइल से एक परियोजना के लिए रिवर्स इंजीनियरिंग एक SQLite क्वेरी में LIMIT कथन का उपयोग करना एमवीवीएम के लिए मैं किस रूपरेखा का उपयोग करना चाहिए? PHP वैरिएबल्स का उपयोग कर एक गतिशील mysql क्वेरी बनाएं फेसबुक ग्राफ़ एपीआई – जावास्क्रिप्ट का उपयोग करके फोटो अपलोड करें स्प्रिंग लेन-देन और हाइबरनेट सीरेंट_सेशन_कोनटेक्स्ट_ क्लास JSON में उद्देश्य- C ऑब्जेक्ट को सीरियललाइज और डिसेरीलाइज़ करें .NET के लिए सबसे परिपक्व बीडीडी फ्रेमवर्क क्या है? ओपनजीएल ES में गोलाकार आरेखण पायथन: ओएससिस्टम चलाने के बाद स्टडआउट कैसे प्राप्त करें? क्या फेसबुक sharer.php अब विस्तृत मापदंडों को स्वीकार नहीं कर पाई है? गो टेम्प्लेट में जेएस फ़ाइल शामिल करें डेटा-छवि एट्रर द्वारा सीएसएस सेट पृष्ठभूमि-छवि रेल में has_one एसोसिएशन के साथ निर्माण का उपयोग करना जावा 8 में एक पैरामीटर के रूप में मैं लैम्ब्डा को किस तरीके से परिभाषित करता हूं?

कैसे सेट किया गया () कार्यान्वित?

मैंने लोगों को देखा है कि अजगर में set ऑब्जेक्ट्स में ओ (1) सदस्यता-चेकिंग है I इन्हें अनुमति देने के लिए आंतरिक रूप से कैसे कार्यान्वित किया जाता है? यह किस प्रकार की डेटा संरचना का उपयोग करता है? क्या अन्य निहितार्थ है कि कार्यान्वयन है?

यहां हर जवाब वास्तव में सशक्त था, लेकिन मैं केवल एक ही स्वीकार कर सकता हूं, इसलिए मैं अपने मूल प्रश्न के सबसे करीब से उत्तर दूँगा। सभी जानकारी के लिए धन्यवाद!

Solutions Collecting From Web of "कैसे सेट किया गया () कार्यान्वित?"

इस धागे के अनुसार:

दरअसल, सीपीआईथॉन के सेट को डमी वैल्यू (सेट्स के सदस्य होने की चाबियाँ) के साथ कीवर्ड्स जैसी कुछ चीजों के रूप में लागू किया जाता है, कुछ अनुकूलन के साथ जो मूल्यों की कमी का फायदा उठाते हैं

तो मूल तौर पर एक set एक हैशटिबल का उपयोग इसके अंतर्निहित डेटा संरचना के रूप में करता है। यह हे (1) सदस्यता जांच को बताता है, चूंकि एक हैशटेबल में एक आइटम की तलाश में ओ (1) ऑपरेशन औसत पर है

यदि आप इतने इच्छुक हैं तो आप सेट के लिए सीपीथॉन स्रोत कोड भी देख सकते हैं, जो कि अचिम डोमा के अनुसार, बहुसंख्यक क्रियान्वयन से कट-पेस्ट है।

जब लोग कहते हैं कि हे (1) सदस्यता-जांच कर रहे हैं, तो वे औसत मामले के बारे में बात कर रहे हैं। सबसे खराब स्थिति में (जब सभी हथेड मूल्यों की टक्कर होती है) सदस्यता-जांच ओ (एन) है। समय की जटिलता पर पायथन विकी देखें

विकिपीडिया लेख का कहना है कि एक हैश तालिका के लिए सबसे अच्छा केस टाइम जटिलता है जो कि O(1 + k/n) आकार बदलती नहीं है यह परिणाम सीधे पायथन सेट पर लागू नहीं होता क्योंकि अजगर सेट करता है एक हैश तालिका का आकार बदलता है।

विकिपीडिया लेख पर थोड़ा और आगे कहता है कि औसत मामले के लिए, और एक साधारण वर्दी हैशिंग फ़ंक्शन को संभालना, समय की जटिलता O(1/(1-k/n)) , जहां k/n को निरंतर c<1 घिरा हो सकता है c<1

बिग-ओ केवल एसिम्प्टोक्टिक व्यवहार के रूप में n → ∞ के रूप में संदर्भित करता है। चूंकि कश्मीर / एन को निरंतर, सी <1, एन के स्वतंत्र से घिरा हो सकता है,

O(1/(1-k/n)) O(1/(1-c)) से बड़ा नहीं है जो O(constant) = O(1) बराबर है।

तो वर्दी साधारण हैशिंग मानते हुए, औसतन , पायथन सेट के लिए सदस्यता-जांच O(1)

मुझे लगता है कि इसकी एक सामान्य गलती, लुकअप set (या उस बात के लिए हैशटेबल) ओ (1) नहीं हैं।
विकिपीडिया से

सरलतम मॉडल में, हैश फ़ंक्शन पूरी तरह अनिर्दिष्ट है और तालिका का आकार बदलना नहीं है। हैश फ़ंक्शन के सर्वोत्तम संभव विकल्प के लिए, खुले पते के साथ आकार n की एक तालिका में कोई टकराव नहीं होता है और सफलतापूर्वक लुकअप के लिए एक तुलना के साथ n तत्वों को धारण करता है, और चेन और कश्मीर कुंजी के साथ आकार n की एक तालिका में न्यूनतम अधिकतम (0, घन) टक्कर और ओ (1 + कश्मीर / एन) लुकअप के लिए तुलना। हैश फ़ंक्शन के सबसे खराब विकल्प के लिए, प्रत्येक प्रविष्टि एक टक्कर का कारण बनती है, और हश तालिकाओं को रेखीय खोज के लिए पतित करता है, जिसमें Ω (k) सम्मिलन प्रति परिशोधित तुलना और एक सफल लुकअप के लिए तुलना की जाती है।

संबंधित: क्या जावा वास्तव में है हे (1)?

हमारे पास सभी स्रोत तक आसानी से पहुंच है, जहां set_lookkey() पहले की गई टिप्पणी कहती है:

 /* set object implementation Written and maintained by Raymond D. Hettinger <python@rcn.com> Derived from Lib/sets.py and Objects/dictobject.c. The basic lookup function used by all operations. This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. The initial probe index is computed as hash mod the table size. Subsequent probe indices are computed as explained in Objects/dictobject.c. To improve cache locality, each probe inspects a series of consecutive nearby entries before moving on to probes elsewhere in memory. This leaves us with a hybrid of linear probing and open addressing. The linear probing reduces the cost of hash collisions because consecutive memory accesses tend to be much cheaper than scattered probes. After LINEAR_PROBES steps, we then use open addressing with the upper bits from the hash value. This helps break-up long chains of collisions. All arithmetic on hash should ignore overflow. Unlike the dictionary implementation, the lookkey function can return NULL if the rich comparison returns an error. */ ... #ifndef LINEAR_PROBES #define LINEAR_PROBES 9 #endif /* This must be >= 1 */ #define PERTURB_SHIFT 5 static setentry * set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) { ... 

set's और dict's बीच अंतर को थोड़ा और अधिक जोर देने dict's , यहां setobject.c टिप्पणी से संबंधित एक अंश है, जो स्पष्ट करता है कि सेट के खिलाफ सेट के मुख्य अंतर है।

सेट के लिए मामलों का उपयोग उन शब्दों से काफी भिन्न होता है जहां देखा-अप कुंजी मौजूद होने की अधिक संभावना होती है। इसके विपरीत, सेट प्राथमिक तौर पर सदस्यता परीक्षण के बारे में होते हैं जहां एक तत्व की उपस्थिति अग्रिम में नहीं पता है। तदनुसार, निर्धारित कार्यान्वयन को पाया गया और न पाया गया दोनों स्थितियों के लिए अनुकूलित करना आवश्यक है।

गिटौब पर स्रोत