पायथन शब्दकोश कुंजी। "जटिलता" में

Question

मुख्य प्रश्न मुख्य रूप से विषय पर मेरी जिज्ञासा को पूरा करने के लिए त्वरित प्रश्न।

मैं एक एसक्यूलाइट डेटाबेस बैकएंड के साथ कुछ बड़े पायथन कार्यक्रम लिख रहा हूं और भविष्य में बड़ी संख्या में रिकॉर्ड से निपट रहा हूं, इसलिए मुझे जितना संभव हो उतना अनुकूलित करना होगा।

कुछ कार्यों के लिए, मैं एक शब्दकोश में कुंजी के माध्यम से खोज रहा हूँ। मैं प्रोटोटाइप के लिए "इन" कीवर्ड का उपयोग कर रहा हूं और बाद में उन खोजों को अनुकूलित करने और उन खोजों को अनुकूलित करने की योजना बना रहा था क्योंकि मुझे पता है कि "इन" कीवर्ड आमतौर पर ओ (एन) है (क्योंकि यह सिर्फ एक संपूर्ण सूची में चित्रण करने और तुलना करने के लिए पाइथन का अनुवाद करता है प्रत्येक तत्व)।

if(key in dict.keys()): 
    ...code... 

लिए:

if(dict[key] != None): 
    ...code... 

यह मूल रूप से एक ही आपरेशन है, लेकिन शीर्ष हे होगा लेकिन, एक अजगर dict मूल रूप से है के रूप में सिर्फ एक हैश नक्शा, अजगर दुभाषिया बहुत चालाक व्याख्या करने के लिए है (एन) और नीचे ओ (1) होगा।

मेरे कोड में नीचे संस्करण का उपयोग करना मेरे लिए आसान है, लेकिन फिर मैं उत्सुक था और सोचा कि मैं पूछूंगा।

Answer 1

सबसे पहले, key in d.keys() आपको d के लिए key in d के समान मूल्य देने की गारंटी है।

और एक dict पर in आपरेशन, या dict_keys वस्तु आप उस पर keys() (3.x में) कॉल करने से वापस पाने, है नहीं हे (एन), यह हे है (1)।

कोई असली "अनुकूलन" नहीं चल रहा है; यह हैश हैश का उपयोग करना हैश तालिका पर __contains__ को लागू करने का स्पष्ट तरीका है, क्योंकि यह __getitem__ को लागू करने का स्पष्ट तरीका है।

---

आप पूछ सकते हैं कि यह कहां गारंटी है।

अच्छा, यह नहीं है। Mapping Typesdict को मूल रूप से collections.abc.Mapping के हैश तालिका कार्यान्वयन के रूप में परिभाषित करता है। किसी को मैपिंग के हैश टेबल कार्यान्वयन को बनाने से रोकना कुछ भी नहीं है, लेकिन फिर भी ओ (एन) खोज प्रदान करता है। लेकिन यह इतना बुरा कार्यान्वयन करने के लिए अतिरिक्त काम होगा, तो वे क्यों होंगे?

तुम सच में अपने आप को यह साबित करने की जरूरत है, तो आप हर कार्यान्वयन आप ध्यान परीक्षण कर सकते हैं (एक प्रोफाइलर साथ, या एक कस्टम __hash__ और __eq__ कि कॉल लॉग के साथ कुछ प्रकार का उपयोग करके, या ...), या स्रोत पढ़ ।

---

2.x में, आप नहीं keys कॉल करने के लिए, चाहते हैं, क्योंकि है कि एक KeysView के बजाय चाबियों का एक list उत्पन्न करता है,। आप iterkeys का उपयोग कर सकते हैं, लेकिन यह एक इटरेटर या कुछ और उत्पन्न कर सकता है जो ओ (1) नहीं है। तो, बस एक अनुक्रम के रूप में खुद को प्रयोग करें।

यहां तक ​​कि 3.x में, आप keys पर कॉल नहीं करना चाहते हैं, क्योंकि इसकी कोई आवश्यकता नहीं है। dict को इटरेट करना, इसकी __contains__ जांचना, और सामान्य रूप से इसे अनुक्रम की तरह व्यवहार करना हमेशा अपनी चाबियों को एक ही चीज़ करने के बराबर है, तो परेशान क्यों करें?(और निश्चित रूप से छोटे KeyView का निर्माण, और इसके माध्यम से पहुंचने के लिए, आपके चलने वाले समय में कुछ नैनोसेकंड और आपके प्रोग्राम में कुछ कीस्ट्रोक जोड़ने जा रहे हैं।)

(यह स्पष्ट नहीं है कि अनुक्रम संचालन का उपयोग करना समकक्ष है d.keys()/d.iterkeys() और d 2.x में प्रदर्शन प्रदर्शन मुद्दों के अलावा, प्रत्येक सीपीथन, ज्योथन, आयरनपीथन और पीपीपी कार्यान्वयन के बराबर हैं, लेकिन ऐसा लगता है कि यह कहीं भी 3.x में नहीं है । और यह कोई प्रभाव नहीं पड़ेगा, बस key in d का उपयोग)

---

हम एक कर रहे हैं। टी, ध्यान दें कि यह:

if(dict[key] != None): 

... काम नहीं करेगा। यदि keydict में नहीं है, तो यह KeyError बढ़ाएगा, None वापस नहीं करेगा।

इसके अलावा, आपको == या != के साथ None कभी भी जांचना नहीं चाहिए; हमेशा is का उपयोग करें।

आप इसे try-या अधिक आसानी से कर सकते हैं, if dict.get(key, None) is not None करें। लेकिन फिर, ऐसा करने का कोई कारण नहीं है। साथ ही, यह उन मामलों को संभाल नहीं पाएगा जहां None एक पूरी तरह से वैध आइटम है। यदि ऐसा है, तो आपको sentinel = object(); if dict.get(key, sentinel) is not sentinel: जैसे कुछ करने की आवश्यकता है।

---

तो, सही बात लिखने के लिए:

if key in d: 

---

आम तौर पर, यह सच नहीं है:

I know the "in" keyword is generally O(n) (as this just translates to python iterating over an entire list and comparing each element

in ऑपरेटर, अधिकांश अन्य ऑपरेटरों की तरह, __contains__ विधि (या सी/जावा/.NET/RPython अंतर्निहित के बराबर) के लिए सिर्फ एक कॉल है। list सूची को पुन: स्थापित करके और प्रत्येक तत्व की तुलना करके इसे लागू करता है; dict मूल्य को हश करके और हैश को देखकर इसे लागू करता है; blist.blist बी + ट्री चलकर इसे लागू करता है; आदि। तो, यह ओ (एन), ओ (1), ओ (लॉग एन) हो सकता है, या कुछ पूरी तरह से अलग हो सकता है।

Answer 2

अजगर 2 dict.keys() में जबकि key in dict एक O(1) ऑपरेशन है कि, क्यों यह एक O(N) आपरेशन है चाबियों का पूरे सूची बनाता है पहले।

if(dict[key] != None)KeyError बढ़ा देंगे अगर कुंजी dict में नहीं पाया जाता है, तो यह पहली बार कोड के बराबर नहीं है।

अजगर 2 परिणाम:

अजगर 3 परिणाम:

>>> dic = dict.fromkeys(range(10**5)) 
>>> %timeit 10000 in dic 
1000000 loops, best of 3: 295 ns per loop 
>>> %timeit 10000 in dic.keys() 
1000000 loops, best of 3: 475 ns per loop 

>>> dic = dict.fromkeys(range(10**5)) 
>>> %timeit 10000 in dic 
1000000 loops, best of 3: 170 ns per loop 
>>> %timeit 10000 in dic.keys() 
100 loops, best of 3: 4.98 ms per loop 
>>> %timeit 10000 in dic.iterkeys() 
1000 loops, best of 3: 402 us per loop 
>>> %timeit 10000 in dic.viewkeys() 
1000000 loops, best of 3: 457 ns per loop 

अजगर 3 dict.keys() में जो काफी तेजी से अजगर 2 के keys() से, लेकिन अभी भी धीमी सरल सामान्य key in dict है एक दृश्य ऑब्जेक्ट

केवल उपयोग करें:

if key in dict: 
    #code 

Answer 3

यह करने के लिए उचित तरीका होगा

if key in dict: 
    do stuff 

में ऑपरेटर हे है (1) शब्दकोशों और अजगर में सेट के लिए।

Answer 4

dict के लिए ऑपरेटर में ओ (1) की औसत केस समय-जटिलता है। अन्य dict() विधियों की समय जटिलता के बारे में विस्तृत जानकारी के लिए, इस link पर जाएं।