कुशल शब्दकोश खोज रहे हैं?

Question

मुझे पाइथन में बड़े शब्दकोशों के माध्यम से खोज करने की दक्षता के बारे में एक त्वरित प्रश्न था। मैं एक बड़ी अल्पविराम से अलग फ़ाइल पढ़ रहा हूं और प्रत्येक पंक्ति से एक कुंजी और मूल्य प्राप्त कर रहा हूं। यदि मेरी कुंजी पहले से ही शब्दकोश में है, तो मैं शब्दकोश में सूचीबद्ध मान में मान जोड़ रहा हूं, यदि कुंजी शब्दकोश में मौजूद नहीं है, तो मैं बस मान जोड़ता हूं। इससे पहले कि मैं इस का उपयोग कर रहा था:

if key in data_dict.keys(): 
    add values 
else: 
    data_dict[key] = value 

यह बहुत तेजी से शुरू होता है, लेकिन जैसा कि शब्दकोश बढ़ता है यह बिंदु है जहां मैं यह बिल्कुल इस्तेमाल नहीं कर सकते करने के लिए, धीमी और धीमी हो जाती है। मैं जिस तरह से मैं यह करने के लिए शब्दकोश में कुंजी के लिए खोज बदल दिया है:

try: 
    # This will fail if key not present 
    data_dict[keyStr] = input_data[keyStr] + load_val 
except: 
    data_dict[keyStr] = load_val 

यह असीम तेजी से होता है, और पढ़ सकते हैं/लिखने 3 सेकंड में कोड के 350,000 से अधिक लाइनों।

मेरा प्रश्न था कि if key in data_dict.keys(): कमांड try: data_dict[keyStr] पर कॉल से बहुत अधिक समय लेता है? और शब्दकोश में कुंजी की खोज करते समय पायथन try कथन का उपयोग क्यों नहीं करेगा?

Answer 1

समस्या यह है कि प्रत्येक परीक्षण के लिए आप .keys() के साथ कुंजी की एक नई सूची उत्पन्न कर रहे हैं। चूंकि चाबियों की सूची अधिक हो जाती है, समय आवश्यक हो जाता है। as noted by dckrooney भी, कुंजी की खोज शब्दकोश की हैश-टेबल संरचना का लाभ लेने के बजाय रैखिक हो जाती है।

बदलें साथ:

if key in data_dict: 

Answer 2

यह सवाल का जवाब नहीं देता है, बल्कि इसे टालता है। collections.defaultdict का उपयोग करने का प्रयास करें। आपको if/else या try/except की आवश्यकता नहीं होगी।

from collections import defaultdict 

data_dict = defaultdict(list) 
for keyStr, load_val in data: 
    data_dict[keyStr].append(load_val) 

Answer 3

इसका कारण यह है data_dict.keys() रिटर्न एक सूची शब्दकोश (कम से कम पायथन 2.x में) में कुंजी को शामिल करते है। जो, सूची में कोई कुंजी है या नहीं, यह जानने के लिए, एक रैखिक खोज की आवश्यकता है।

जबकि, dict के तत्व को एक्सेस करने का प्रयास सीधे शब्दों के भयानक गुणों का लाभ उठाता है ताकि पहुंच लगभग तात्कालिक हो।

Answer 4

वहाँ कोशिश समारोह के लिए समान है कि तुम मदद करनी चाहिए कुछ है: dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val 

Answer 5

data_dict.keys() शब्दकोश में चाबियों का एक अवर्गीकृत सूची देता है। इस प्रकार जब भी आप यह देखने के लिए जांच करते हैं कि कोई दी गई कुंजी शब्दकोश में है या नहीं, तो आप कुंजी की सूची (एक ओ (एन) ऑपरेशन) में एक रैखिक खोज कर रहे हैं। आपकी सूची जितनी अधिक होगी, दी गई कुंजी की खोज में उतना ही समय लगेगा।

इसे data_dict[keyStr] पर तुलना करें। यह एक हैश लुकअप करता है, जो एक ओ (1) ऑपरेशन है। यह (सीधे) शब्दकोश में कुंजी की संख्या पर निर्भर नहीं करता है; यहां तक ​​कि जैसे ही आप अधिक कुंजी जोड़ते हैं, यह जांचने का समय कि शब्दकोश में दी गई कुंजी स्थिर है या नहीं।

Answer 6

तुम भी बस

if key in data_dict: 

बजाय

if key in data_dict.keys(): 

जैसा कि बताया जा उपयोग कर सकते हैं, पहले एक सीधा हैश देखने है - ऑफसेट इरादा सीधे गणना की जाती है, और उसके बाद जाँच की - यह मोटे तौर पर है ओ (1), जबकि चाबियों की जांच एक रैखिक खोज है, जो ओ (एन) है।

In [258]: data_dict = dict([(x, x) for x in range(100000)]) 

In [259]: %timeit 999999 in data_dict.keys() 
100 loops, best of 3: 3.47 ms per loop 

In [260]: %timeit 999999 in data_dict 
10000000 loops, best of 3: 49.3 ns per loop 

Answer 7

पुराने दिनों में वापस हम setdefault प्रयोग किया है:

data_dict.setdefault(keyStr, []).append(load_val) 

Answer 8

के रूप में कई अन्य लोगों का उल्लेख किया है, समस्या तथ्य key in data_dict.keys() का उपयोग करता है अव्यवस्थित listkeys() विधि से लौटे में निहित है (पायथन 2.x में), जो linear timeओ (एन) खोज करने के लिए लेता है आटा, जिसका अर्थ यह है कि चलने का समय शब्दकोश के आकार के साथ रैखिक रूप से बढ़ता है, साथ ही आकार की बढ़ोतरी के साथ ही चाबियों की सूची उत्पन्न करने में लंबा और लंबा समय लगेगा।

दूसरी ओर, key in data_dict केवल निरंतर समय हे (1), औसतन, एक खोज परवाह किए बिना शब्दकोश के आकार की वजह से आंतरिक रूप से यह एक hash table लुक-अप करता है प्रदर्शन करने की आवश्यकता है। इसके अलावा, शब्दकोशों के आंतरिक प्रतिनिधित्व के अपने हिस्से के बाद से यह हैश तालिका पहले से मौजूद है, और इसलिए इसका उपयोग करने से पहले उत्पन्न नहीं होना चाहिए।

पायथन स्वचालित रूप से ऐसा नहीं करता है क्योंकि in ऑपरेटर केवल अपने दो ऑपरेटरों के प्रकार को जानता है, न कि उनके स्रोत, इसलिए यह स्वचालित रूप से पहले मामले को अनुकूलित नहीं कर सकता है, जहां यह सब कुछ देखता है वह कुंजी और सूची है।

हालांकि, इस मामले में अंतर्निहित collections मॉड्यूल में defaultdict नामक एक शब्दकोश के एक विशेष संस्करण में डेटा संग्रहीत करके खोज गति का मुद्दा संभवतः बचाया जा सकता है। यहाँ अगर आप एक प्रयोग किया जाता है अपने कोड कैसे दिखाई दे सकती है:

from collections import defaultdict 

input_data = defaultdict(float) # (guessing factory type) 
... 
data_dict[keyStr] = input_data[keyStr] + load_val 

वहाँ जब input_data[keyStr] एक के लिए कोई पूर्व प्रविष्टि एक डिफ़ॉल्ट मान (इस उदाहरण में float के लिए 0.0) के साथ बना दी जाएगी। जैसा कि आप देख सकते हैं, कोड कम और बहुत तेज़ है, बिना किसी if परीक्षण या अपवाद हैंडलिंग की आवश्यकता के बिना।