पाइथन tuples कुंजी के रूप में धीमा?

Question

मैं एक शब्दकोश में क्रमबद्ध tuples के लिए एक तेज लुकअप को लागू करने की कोशिश कर रहा हूँ; ऐसा कुछ जो प्रश्न का उत्तर देता है "क्या टुपल (3,8) का एक संबद्ध मूल्य होता है, और यदि हां, तो यह क्या है?"। Tuples में पूर्णांक 0 से नीचे और अधिकतम से max_int द्वारा बाध्य होना चाहिए।

मैं आगे बढ़ गया और पायथन के निर्देश का उपयोग किया लेकिन पाया कि यह बहुत धीमी है। इस समस्या का एक अन्य दृष्टिकोण max_int (अधिकतर खाली) dicts के साथ एक सूची टी बनाना होगा, और प्रत्येक tuple (3,8) के लिए टी [3] [8] = मान डाल दिया जाएगा। हालांकि यह वास्तव में बाल्टी-हैश दृष्टिकोण है कि पाइथन डिक्ट्स के साथ लेता है, लेकिन बाद वाला लगभग 30 गुना (!) तेज़ है।

इसके अलावा, यह बदसूरत है (विशेष रूप से जब से मैं अब 3-टुपल्स को लागू करने वाला हूं), इसलिए मैं यहां कुछ संकेतों की सराहना करता हूं।

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

print d 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    (3,8) in d.keys() 
elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

print t 

# do some lookups 
m = 10000 
start_time = time.time() 
for k in xrange(m): 
    8 in t[3].keys() 
elapsed = time.time() - start_time 
print elapsed 

Answer 1

यहाँ कर रहे हैं अजगर 2.7 के साथ सटीक समय परिणाम:

>>> %timeit (3, 8) in d.keys() # Slow, indeed 
100000 loops, best of 3: 9.58 us per loop 

>>> %timeit 8 in t[3].keys() # Faster 
1000000 loops, best of 3: 246 ns per loop 

>>> %timeit (3, 8) in d # Even faster! 
10000000 loops, best of 3: 117 ns per loop 

>>> %timeit 8 in t[3] # Slightly slower 
10000000 loops, best of 3: 127 ns per loop 

वे बताते हैं कि मानक (3, 8) in d (कोई .keys() सूची निर्माण) वास्तव में एक बालक तेजी से (कम सामान्य) 8 in t[3] दृष्टिकोण, और से दोगुने से है तेजी से प्रश्न के अपेक्षाकृत तेज़ 8 in t[3].keys() के रूप में। यह .keys/कोई .keys अंतर यह है कि (3, 8) in d.keys() एक सूची चाबियों का (अजगर 2 में) बनाता है और फिर इस सूची है, जो शब्दकोश d के हैश तालिका में (3, 8) की तलाश तुलना में बहुत धीमी है में (3, 8) के लिए लग रहा है से आता है।

के रूप में टिप्पणी में बताया गया है, समय परिणामों अजगर 3 के साथ अलग कर रहे हैं: अजगर 3 के keys() एक तेजी से in परीक्षण क्योंकि बजाय keys() रिटर्न कुंजी पर एक दृश्य, इसी ताकि in ऑपरेटर के हैश तालिका का उपयोग कर सकते है शब्दकोश।

मूल प्रश्न में गति अंतर इस तथ्य से आता है कि d.keys()t[3].keys() की तुलना में अपेक्षाकृत लंबी सूची बनाता है।

पीएस: %timeit फ़ंक्शन उत्कृष्ट IPython खोल द्वारा प्रदान किया जाता है। मूल प्रोग्राम को %run prog.py के साथ आईपीथन के माध्यम से निष्पादित किया जा सकता है।

Answer 2

आप विभिन्न मूल्यों के लिए परीक्षण कर रहे हैं:

संदर्भ के लिए, यहाँ कोड मैं समय प्राप्त करने के लिए प्रयोग किया जाता है। शब्दकोश संस्करण में, 100,000 कुंजी के लिए एक लुकअप है, जबकि बाल्टी-सूची संरचना में, लुकअप केवल 10,000 कुंजी के लिए है।

इसके अलावा, कोड का यह स्निपेट चीजों को धीमा कर रहा है: (3,8) in d.keys() यदि आपने अभी (3,8) in d लिखा है, तो दोनों संस्करणों में लुकअप समय काफी समान होगा, और अंतर नगण्य होगा। इस संशोधित परीक्षण की कोशिश करो और खुद के लिए देखें:

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if (3,8) in d: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if 8 in t[3]: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

मनाया व्यवहार के लिए कारण यह है कि (3,8) in d.keys() और 8 in t[3].keys() दोनों हर बार चाबियों का एक नया अस्थायी सूची बना रहे हैं, लेकिन दूसरे संस्करण में कम सूचियों बनाता है। यदि आपने बस idiom key in dictionary का उपयोग किया था, तो अस्थायी सूचियां अब नहीं बनाई गई हैं और प्रदर्शन दोनों दृष्टिकोणों के समान दिखने लगता है।

मैं पहले संस्करण के साथ जाऊंगा, बहुत आसान, पढ़ने और समझने और बेवकूफ बनाने में आसान है - और जब सही तरीके से उपयोग किया जाता है, तो साथ ही साथ दूसरे संस्करण भी करता है।

Answer 3

यह क्योंकि बाद मानता है कि a मौजूद होना चाहिए b in t[a] को (a, b) in d की गति की तुलना में थोड़ा अजीब है।

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