पाइथन dict

Question

तक पहुंचने की समय जटिलता मैं एक साधारण पायथन प्रोग्राम लिख रहा हूं।

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

मेरे पास हैशिंग मूल्य जो बिंदुओं के tuples हैं। प्रत्येक बिंदु है: (x, y), 0 < = x, y < = 50
शब्दकोश में प्रत्येक कुंजी है: 2-5 अंक का एक टुपल: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))

चाबियाँ लिखे जाने की तुलना में कई बार अक्सर पढ़ी जाती हैं।

क्या मैं सही हूं कि पाइथन डिक्ट्स ऐसे इनपुट के साथ रैखिक पहुंच के समय से ग्रस्त हैं?

जहां तक ​​मुझे पता है, सेटों ने लॉगरिदमिक पहुंच के समय की गारंटी दी है।
पायथन में सेट (या कुछ समान) का उपयोग करके मैं डिक्ट्स का अनुकरण कैसे कर सकता हूं?

def memoize(fun): 
    memoized = {} 
    def memo(*args): 
     key = args 
     if not key in memoized: 
      memoized[key] = fun(*args) 
     return memoized[key] 
    return memo 

Answer 1

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

सबसे अच्छी विधि जांच करने और आपके द्वारा उपयोग की जा रही वस्तुओं के हैश को देखने के लिए सबसे अच्छी विधि होगी। CPython Dictint PyObject_Hash (PyObject *o) का उपयोग करता है जो hash(o) के बराबर है।

एक त्वरित जांच के बाद, मैं अभी तक दो tuples एक ही मूल्य है कि हैश है, जो संकेत मिलता है कि देखने (24 घंटे के लिए उपलब्ध है) हे (1)

l = [] 
for x in range(0, 50): 
    for y in range(0, 50): 
     if hash((x,y)) in l: 
      print "Fail: ", (x,y) 
     l.append(hash((x,y))) 
print "Test Finished" 

CodePad है खोज करने में कामयाब नहीं किया है

Answer 2

आप सही नहीं हैं:

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

Answer 3

यदि आपने उदाहरण कोड और डेटा प्रदान किया है तो सुझाव देना आसान होगा।

शब्दकोश एक्सेस करना एक समस्या होने की संभावना नहीं है क्योंकि ऑपरेशन O(1) on average, and O(N) amortized worst case है। यह संभव है कि अंतर्निर्मित हैशिंग फ़ंक्शन आपके डेटा के लिए टकराव का अनुभव कर रहे हों। यदि आपको अंतर्निहित हैशिंग फ़ंक्शन के साथ समस्याएं आ रही हैं, तो आप अपना स्वयं का प्रदान कर सकते हैं।

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

आप अपने वर्ग में __hash__ विधि के ऊपर लिख इस तरह एक कस्टम हैश समारोह को लागू करने के कर सकते हैं:

def __hash__(self):  
    return hash(str(self)) 

अपने डेटा वास्तव में कैसा दिखता है के आधार पर, आप के साथ एक तेजी से आने के लिए सक्षम हो सकता है हैश फ़ंक्शन जिसमें मानक फ़ंक्शन की तुलना में कम टकराव है। हालांकि, यह असंभव है। अधिक जानकारी के लिए Python Wiki page on Dictionary Keys देखें।

Answer 4

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

आप कितने tuples याद कर रहे हैं? क्या आपने मेमोरी पदचिह्न माना है? शायद आप अपना पूरा समय स्मृति आवंटक या पेजिंग मेमोरी में खर्च कर रहे हैं।

Answer 5

मेरा प्रोग्राम शब्दकोशों के लिए रैखिक पहुंच से पीड़ित प्रतीत होता है, इसके रन-टाइम तेजी से बढ़ता है भले ही एल्गोरिदम वर्गबद्ध है।

मैं मूल्यों को याद करने के लिए एक शब्दकोश का उपयोग करता हूं। यह एक बाधा प्रतीत होता है।

यह आपके ज्ञापन विधि में एक बग का सबूत है।

Answer 6

अपने विशिष्ट सवालों के जवाब देने के लिए:

Q1: "" "मैं सही हूँ कि अजगर dicts ऐसी जानकारी के साथ रैखिक अभिगम समय से पीड़ित हैं?" ""

A1: यदि आप का मतलब है कि औसत लुकअप समय ओ (एन) है जहां एन dict में प्रविष्टियों की संख्या है, तो यह अत्यधिक संभावना है कि आप गलत हैं। यदि आप सही हैं, तो पाइथन समुदाय बहुत अच्छी तरह से जानना चाहेगा कि आप किस परिस्थिति में सही हैं, ताकि समस्या को कम किया जा सके या कम से कम चेतावनी दी जा सके। न तो "नमूना" कोड और न ही "सरलीकृत" कोड उपयोगी हैं। कृपया वास्तविक कोड और डेटा दिखाएं जो समस्या को पुन: पेश करता है। कोड को प्रत्येक वस्तु के लिए निर्देशित किया जाना चाहिए जैसे कि धुन वस्तुओं की संख्या और प्रत्येक पी के लिए तीर पहुंच की संख्या जहां पी कुंजी (2 < = पी < = 5)

प्रश्न 2: "" अब तक के रूप में मैं जानता हूँ कि, सेट लघुगणक अभिगम समय की गारंटी है मैं सेट (या कुछ इसी तरह) पायथन में "" "

ए 2 का उपयोग कर dicts कैसे अनुकरण कर सकते हैं:। क्या संदर्भ में सेट की गारंटी है लघुगणक अभिगम समय? पायथन कार्यान्वयन के लिए ऐसी कोई गारंटी नहीं है। हाल ही में हालिया सीपीथन संस्करण एक कट-डाउन डंक कार्यान्वयन (केवल कुंजी, कोई मान नहीं) का उपयोग करते हैं, इसलिए उम्मीद औसत ओ (1) व्यवहार है। आप सेट्स या किसी भी भाषा में समान कुछ के साथ डिकट्स कैसे अनुकरण कर सकते हैं? संक्षिप्त उत्तर: अत्यधिक कठिनाई के साथ, यदि आप dict.has_key(key) से परे कोई कार्यक्षमता चाहते हैं।