python अजगर डायरी के लिए ओ(1) के लिए सबसे खराब केस टाइम जटिलता का अनुकूलन




memory dictionary (3)

ज्यादातर प्रदर्शन हिट (आमतौर पर टक्कर पर ले जाते हैं) सभी कॉलों पर परिशोधित होते हैं। तो सबसे यथार्थवादी उपयोग के लिए, आप प्रत्येक कॉल के लिए O(n) करेंगे वास्तव में, एकमात्र ऐसा मामला जहां आप हर कॉल पर O(n) हिट लगाते हैं, वह रोग के मामले में होता है जहां हर प्रमुख की हैश मौजूदा कुंजी के हैश मान (जो कि हैशटेबल का सबसे खराब (संभवतः या सबसे दुर्भाग्यपूर्ण) उपयोग के साथ टकराता है) ।

उदाहरण के लिए, यदि आप पहले से ही कुंजी के अपने सेट को जानते हैं, और आप जानते हैं कि उनके पास हैश टकराव नहीं होंगे (यानी सभी उनके हैश अद्वितीय हैं), तो आप टकराव के मामले नहीं भुगतेंगे। अन्य प्रमुख O(n) ऑपरेशन हैशटेबल रीसाइजिंग है, लेकिन इसकी आवृत्ति कार्यान्वयन (एक्सपेस फैक्टर / हैश फ़ंक्शन / टकराव रिज़ॉल्यूशन स्कीम इत्यादि) पर निर्भर करती है और इनपुट सेट के आधार पर रन-टू-रन में भी भिन्न होगी ।

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

एक पूरी तरह से अलग सवाल यह है कि आप संरचना को पढ़ने / क्वेरी करने का इरादा कर रहे हैं? क्या आपको अलग-अलग मूल्यों को संलग्न करने की आवश्यकता है और उन्हें एक चाबी के माध्यम से पहुंच है? यह आदेश दिया जाना चाहिए? शायद एक set एक dict तुलना में अधिक उपयुक्त हो सकता है, क्योंकि आपको वास्तव में एक key:value आवश्यकता नहीं है key:value मैपिंग

अद्यतन करें:

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

यह भी लगता है कि आप शुरू करने के लिए एक डाटाबेस से डेटा पढ़ रहे हैं, इसलिए आप इसे आगे बढ़ा सकते हैं?

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

अजगर का उपयोग करके sqlite3 मॉड्यूल में उपयोग करने की कोशिश करें और ":memory:" निर्माण के आधार पर डीबी फ़ाइल पथ के रूप में इन-मेमोरी संस्करण का प्रयास करें:

con = sqlite3.connect(":memory:")

मुझे मेमोरी (रैम) में 500 एम दो अंकी यूनिकोड वर्ण संग्रहीत करना है

मैं जो डेटा संरचना का उपयोग करता हूं, वह होना चाहिए:

Worst Case Space Complexity: O(n)
Worst Case Time Complexity: O(1) <-- insertion, read, update, deletion

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

मैंने सुना है कि अगर प्रविष्टियों की संख्या ज्ञात है, तो ओ परिस्थितियों में ओ (1) की समय की जटिलता प्राप्त की जा सकती है।

उसको कैसे करे?

यदि अजगर में संभव नहीं है, तो क्या मैं अपने पायथन कोड में सीधे मेमोरी पतों और डेटा को एक्सेस कर सकता हूं? यदि हां, तो कैसे?


क्या औसत कारणों के बजाय आपको सबसे खराब स्थिति के बारे में परवाह है? कोई उचित हैशटेबल आपको ओ (एन) का औसत प्रदर्शन देगा।

यदि आप वास्तव में ओ (1) के सबसे खराब प्रदर्शन चाहते हैं, तो यहां दो संभावित दृष्टिकोण हैं:

  1. max(charCode)-min(charCode) प्रविष्टियों का एक सदिश max(charCode)-min(charCode) और सीधे यूनिकोड वर्ण कोड से आप max(charCode)-min(charCode) चाहें देखें। यह अच्छी तरह से काम करेगा यदि आपकी चाबियाँ एक कॉम्पैक्ट-पर्याप्त रेंज में आती हैं जो आप रैम में फिट कर सकते हैं।

  2. हैश फ़ंक्शंस या शब्दकोश आकार (एक शब्दकोश के एक कस्टम कार्यान्वयन का उपयोग करके, जिसे आप इसे नियंत्रित करने की सुविधा देता है) का चयन करने के लिए एक क्रूर बल के दृष्टिकोण का उपयोग करें, और जब तक आप कोई टकराव न करें तब तक नए फ़ंक्शन और / या आकारों की कोशिश करना जारी रखें। एक बहुत लंबे समय के लिए यह उम्मीद है। मैं यह सुझा नहीं करता।

संपादित करें:

मान लीजिए कि आप जानते हैं कि न्यूनतम वर्ण कोड आपको दिखाई देगा 1234 और अधिकतम आपको 98765 है। आगे मान लें कि आपके पास 98765-1234 तत्वों को रखने के लिए पर्याप्त रैम है। मैं यह भी मान numpy कि आप numpy पुस्तकालय या कुछ अन्य कुशल सरणी क्रियान्वयन का उपयोग करने के लिए तैयार हैं numpy उस स्थिति में, आप वैक्टर में मूल्यों को इस तरह से स्टोर कर सकते हैं:

# configuration info
max_value = 98765 # replace with your number
min_value = 1234  # replace with your number
spread = (max_value - min_value)
dtype = object # replace with a primitive type if you want to store something simpler

# create the big vector
my_data = numpy.empty((spread,), dtype=dtype)

# insert elements
my_char_code              = ...
my_value_for_my_char_code = ...

assert min_value <= my_char_code < max_value
my_data[my_char_code - min_value] = my_value_for_my_char_code

# extract elements
my_char_code              = ...
assert min_value <= my_char_code < max_value
my_value_for_my_char_code = my_data[my_char_code - min_value]

यह ओ (1) है क्योंकि लुकअप पॉइंटर अंकगणितीय का उपयोग करके लागू किया गया है और सरणी में संग्रहीत तत्वों की संख्या पर कोई निर्भरता नहीं है।

यह दृष्टिकोण बहुत ही बेकार हो सकता है यदि आप वास्तव में संग्रहित करने वाले तत्वों की संख्या spread से बहुत कम होते spread । उदाहरण के लिए, यदि 4 अरब (सभी यूटीएफ 32) का spread होता है तो केवल my_data कम से कम 4 अरब * 8 बाइट्स / पॉइंटर = 32 जीबी रैम (और संभवतः बहुत अधिक; मुझे नहीं पता कि बड़े पायथन संदर्भ क्या हैं) । दूसरी ओर, यदि min_value 3 अरब और max_value = min_value + 100 , तो मेमोरी उपयोग छोटा होगा।


शब्दकोश तकनीकी रूप से हे (एन) का एक सबसे खराब मामला है, लेकिन यह संभवतः होने की संभावना नहीं है और संभवत: आपके मामले में नहीं होगा। मैं डिक्शनरी का उपयोग करने की कोशिश करता हूं और केवल एक अलग कार्यान्वयन पर स्विच कर सकता हूं यदि यह आपके लिए क्या करना है, इसके लिए पर्याप्त नहीं है।

यहां विषय पर एक उपयोगी धागा है





complexity-theory