python - यह लूप एक शब्दकोश बनाने के लिए एक शब्दकोश समझ से अधिक तेज़ क्यों है?




python-3.x performance (2)

मैं एक सॉफ्टवेयर / कंप्यूटर विज्ञान पृष्ठभूमि से नहीं आता, लेकिन मैं पायथन में कोड करना पसंद करता हूं और आमतौर पर समझ सकता हूं कि चीजें तेजी से क्यों होती हैं मैं यह जानने के लिए वास्तव में उत्सुक हूं कि लूप के लिए यह शब्दकोष की समझ से ज्यादा तेज क्यों चलता है। कोई अंतर्दृष्टि?

समस्या: इन कुंजियों और मूल्यों के साथ एक शब्दकोश को देखते हुए, मानों को कुंजी के रूप में और मानों के साथ एक शब्दकोश लौटाएं। (चुनौती: इसे एक पंक्ति में करें)

और कोड

a = {'a':'hi','b':'hey','c':'yo'}

b = {}
for i,j in a.items():
    b[j]=i

%% timeit 932 ns ± 37.2 ns per loop

b = {v: k for k, v in a.items()}

%% timeit 1.08 µs ± 16.4 ns per loop

आप रास्ते में बहुत छोटे इनपुट के साथ परीक्षण कर रहे हैं; जबकि एक शब्दकोश समझ किसी सूची समझ की तुलना में लूप के for एक प्रदर्शन लाभ के रूप में ज्यादा नहीं होती है, यथार्थवादी समस्या के आकार के लिए यह लूप के for हरा सकता है और करता है, खासकर जब एक वैश्विक नाम को लक्षित करता है।

आपके इनपुट में सिर्फ 3 कुंजी-मूल्य जोड़े हैं। इसके बजाय 1000 तत्वों के साथ परीक्षण, हम देखते हैं कि इसके बजाय समय बहुत करीब हैं:

>>> import timeit
>>> from random import choice, randint; from string import ascii_lowercase as letters
>>> looped = '''\
... b = {}
... for i,j in a.items():
...     b[j]=i
... '''
>>> dictcomp = '''b = {v: k for k, v in a.items()}'''
>>> def rs(): return ''.join([choice(letters) for _ in range(randint(3, 15))])
...
>>> a = {rs(): rs() for _ in range(1000)}
>>> len(a)
1000
>>> count, total = timeit.Timer(looped, 'from __main__ import a').autorange()
>>> (total / count) * 1000000   # microseconds per run
66.62004760000855
>>> count, total = timeit.Timer(dictcomp, 'from __main__ import a').autorange()
>>> (total / count) * 1000000   # microseconds per run
64.5464928005822

अंतर वहाँ है, तानाशाही COMP तेजी से है, लेकिन सिर्फ इस पैमाने पर। कई महत्वपूर्ण-मूल्य वाले जोड़े के साथ 100 गुना का अंतर थोड़ा बड़ा है:

>>> a = {rs(): rs() for _ in range(100000)}
>>> len(a)
98476
>>> count, total = timeit.Timer(looped, 'from __main__ import a').autorange()
>>> total / count * 1000  # milliseconds, different scale!
15.48140200029593
>>> count, total = timeit.Timer(dictcomp, 'from __main__ import a').autorange()
>>> total / count * 1000  # milliseconds, different scale!
13.674790799996117

जब आप दोनों लगभग 100k कुंजी-मूल्य वाले जोड़े पर विचार करते हैं, तो यह उतना बड़ा अंतर नहीं है । फिर भी, लूप के लिए स्पष्ट रूप से धीमा है

तो 3 तत्वों के साथ गति में अंतर क्यों? क्योंकि एक समझ (शब्दकोश, सेट, सूची समझ या एक जनरेटर अभिव्यक्ति) एक नए फ़ंक्शन के रूप में लागू किए गए हुड के नीचे है, और उस फ़ंक्शन को कॉल करने का आधार लागत है सादे लूप का भुगतान नहीं करना पड़ता है।

यहाँ दोनों विकल्पों के लिए बायटेकोड के लिए disassembly है; उच्च MAKE_FUNCTION लिए MAKE_FUNCTION और CALL_FUNCTION opcodes को ध्यान में MAKE_FUNCTION , यह समझने के लिए कि क्या कार्य करता है, के लिए एक अलग खंड है, और यहाँ दोनों के बीच वास्तव में बहुत कम अंतर हैं:

>>> import dis
>>> dis.dis(looped)
  1           0 BUILD_MAP                0
              2 STORE_NAME               0 (b)

  2           4 SETUP_LOOP              28 (to 34)
              6 LOAD_NAME                1 (a)
              8 LOAD_METHOD              2 (items)
             10 CALL_METHOD              0
             12 GET_ITER
        >>   14 FOR_ITER                16 (to 32)
             16 UNPACK_SEQUENCE          2
             18 STORE_NAME               3 (i)
             20 STORE_NAME               4 (j)

  3          22 LOAD_NAME                3 (i)
             24 LOAD_NAME                0 (b)
             26 LOAD_NAME                4 (j)
             28 STORE_SUBSCR
             30 JUMP_ABSOLUTE           14
        >>   32 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             36 RETURN_VALUE
>>> dis.dis(dictcomp)
  1           0 LOAD_CONST               0 (<code object <dictcomp> at 0x11d6ade40, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<dictcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (a)
              8 LOAD_METHOD              1 (items)
             10 CALL_METHOD              0
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 STORE_NAME               2 (b)
             18 LOAD_CONST               2 (None)
             20 RETURN_VALUE

Disassembly of <code object <dictcomp> at 0x11d6ade40, file "<dis>", line 1>:
  1           0 BUILD_MAP                0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                14 (to 20)
              6 UNPACK_SEQUENCE          2
              8 STORE_FAST               1 (k)
             10 STORE_FAST               2 (v)
             12 LOAD_FAST                1 (k)
             14 LOAD_FAST                2 (v)
             16 MAP_ADD                  2
             18 JUMP_ABSOLUTE            4
        >>   20 RETURN_VALUE

सामग्री का अंतर: लूप किए गए कोड का उपयोग करता है LOAD_NAME प्रत्येक पुनरावृत्ति के लिए LOAD_NAME , और STORE_SUBSCR को कुंजी-लोड किए गए युग्म को प्रमुख लोड में संग्रहीत करने के लिए। शब्दकोश की समझ MAP_ADD जैसी ही चीज को प्राप्त करने के लिए MAP_ADD का उपयोग MAP_ADD है, लेकिन हर बार उस b नाम को लोड नहीं करना पड़ता है।

लेकिन केवल 3 पुनरावृत्तियों के साथ, MAKE_FUNCTION / CALL_FUNCTION कॉम्बो को जिस व्यापक समझ के साथ निष्पादित करना है वह प्रदर्शन पर वास्तविक ड्रैग है:

>>> make_and_call = '(lambda i: None)(None)'
>>> dis.dis(make_and_call)
  1           0 LOAD_CONST               0 (<code object <lambda> at 0x11d6ab270, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<lambda>')
              4 MAKE_FUNCTION            0
              6 LOAD_CONST               2 (None)
              8 CALL_FUNCTION            1
             10 RETURN_VALUE

Disassembly of <code object <lambda> at 0x11d6ab270, file "<dis>", line 1>:
  1           0 LOAD_CONST               0 (None)
              2 RETURN_VALUE
>>> count, total = timeit.Timer(make_and_call).autorange()
>>> total / count * 1000000
0.12945385499915574

एक तर्क के साथ एक फ़ंक्शन ऑब्जेक्ट बनाने के लिए 0.1 μs से अधिक, और इसे कॉल करें (हम जो None पास करते हैं, LOAD_CONST लिए एक अतिरिक्त LOAD_CONST साथ)! और यह सिर्फ 3 मुख्य-मूल्य वाले जोड़े के लिए लूप और समझ के समय के बीच अंतर के बारे में है।

आप इसे आश्चर्यचकित करने के लिए कह सकते हैं कि फावड़ा वाला आदमी एक बेकहो की तुलना में तेजी से एक छोटा छेद खोद सकता है। बैकहो निश्चित रूप से तेजी से खुदाई कर सकता है, लेकिन फावड़ा वाला आदमी तेजी से शुरू कर सकता है यदि आपको बैकहो शुरू करने और पहले स्थिति में स्थानांतरित करने की आवश्यकता है!

कुछ प्रमुख-मूल्य वाले जोड़े (एक बड़ा छेद खोदने) से परे, फ़ंक्शन बनाने और कॉल लागत शून्य में दूर हो जाती है। इस बिंदु पर स्पष्ट समझ और स्पष्ट लूप मूल रूप से एक ही काम करते हैं:

  • अगली कुंजी-मूल्य जोड़ी लें, जो स्टैक पर पॉप करें
  • स्टैक पर शीर्ष दो वस्तुओं (या तो STORE_SUBSCR या MAP_ADD साथ एक dict.__setitem__ ऑपरेशन के माध्यम से dict.__setitem__ हुक को कॉल करें। यह 'फ़ंक्शन कॉल' के रूप में नहीं गिना जाता है क्योंकि यह सभी इंटरप्रेटर लूप में आंतरिक रूप से नियंत्रित होता है।

यह एक सूची समझ से अलग है, जहां सादा लूप संस्करण में एक विशेषता लुकअप को शामिल करते हुए list.append() का उपयोग करना होगा, और एक फ़ंक्शन प्रत्येक लूप पुनरावृत्ति को कॉल करेगा । सूची अंतर गति लाभ इस अंतर से आता है; देखें पायथन लिस्ट की समझ महंगी

एक तानाशाही समझ जो कुछ जोड़ता है, वह यह है कि लक्ष्य शब्दकोश नाम को केवल एक बार देखने की जरूरत है, जब अंतिम शब्दकोश वस्तु के लिए बाध्यकारी b । यदि लक्ष्य शब्दकोश एक स्थानीय चर के बजाय एक वैश्विक है , तो समझ जीत जाती है, नीचे हाथ:

>>> a = {rs(): rs() for _ in range(1000)}
>>> len(a)
1000
>>> namespace = {}
>>> count, total = timeit.Timer(looped, 'from __main__ import a; global b', globals=namespace).autorange()
>>> (total / count) * 1000000
76.72348440100905
>>> count, total = timeit.Timer(dictcomp, 'from __main__ import a; global b', globals=namespace).autorange()
>>> (total / count) * 1000000
64.72114819916897
>>> len(namespace['b'])
1000

तो बस एक संक्षिप्त समझ का उपयोग करें। प्रक्रिया करने के लिए <30 तत्वों के साथ अंतर की देखभाल के लिए बहुत छोटा है, और जिस पल आप एक वैश्विक पैदा कर रहे हैं या अधिक आइटम हैं, वैसे भी तानाशाही समझ से बाहर जीतता है।


कुछ इंद्रियों में यह सवाल, काफी हद तक एक सूची में शामिल करने की तुलना में एक सूची समझ क्यों इतनी तेजी से समान है ? जो मैंने बहुत पहले उत्तर दिया है। हालाँकि, यह कारण कि यह व्यवहार आपके लिए आश्चर्यजनक है, जाहिर है क्योंकि आपका शब्दकोश एक नया फ़ंक्शन फ़्रेम बनाने और स्टैक में इसे खींचने / खींचने की लागत को दूर करने के लिए बहुत छोटा है। यह समझने के लिए कि चलो टो स्निपेट्स की त्वचा के नीचे बेहतर है:

In [1]: a = {'a':'hi','b':'hey','c':'yo'}
   ...: 
   ...: def reg_loop(a):
   ...:     b = {}
   ...:     for i,j in a.items():
   ...:         b[j]=i
   ...:         

In [2]: def dict_comp(a):
   ...:     b = {v: k for k, v in a.items()}
   ...:     

In [3]: 

In [3]: %timeit reg_loop(a)
529 ns ± 7.89 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: 

In [4]: %timeit dict_comp(a)
656 ns ± 5.39 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [5]: 

In [5]: import dis

In [6]: dis.dis(reg_loop)
  4           0 BUILD_MAP                0
              2 STORE_FAST               1 (b)

  5           4 SETUP_LOOP              28 (to 34)
              6 LOAD_FAST                0 (a)
              8 LOAD_METHOD              0 (items)
             10 CALL_METHOD              0
             12 GET_ITER
        >>   14 FOR_ITER                16 (to 32)
             16 UNPACK_SEQUENCE          2
             18 STORE_FAST               2 (i)
             20 STORE_FAST               3 (j)

  6          22 LOAD_FAST                2 (i)
             24 LOAD_FAST                1 (b)
             26 LOAD_FAST                3 (j)
             28 STORE_SUBSCR
             30 JUMP_ABSOLUTE           14
        >>   32 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             36 RETURN_VALUE

In [7]: 

In [7]: dis.dis(dict_comp)
  2           0 LOAD_CONST               1 (<code object <dictcomp> at 0x7fbada1adf60, file "<ipython-input-2-aac022159794>", line 2>)
              2 LOAD_CONST               2 ('dict_comp.<locals>.<dictcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_FAST                0 (a)
              8 LOAD_METHOD              0 (items)
             10 CALL_METHOD              0
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 STORE_FAST               1 (b)
             18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

दूसरे MAKE_FUNCTION कोड ( MAKE_FUNCTION समझ) पर आपके पास MAKE_FUNCTION opcode होता है, जैसा कि प्रलेखन में भी कहा गया है कि यह स्टैक पर एक नई फ़ंक्शन ऑब्जेक्ट को धकेलता है। और बाद में CALL_FUNCTION जो CALL_FUNCTION तर्कों के साथ एक कॉल करने योग्य ऑब्जेक्ट को कॉल करता है। और फिर:

स्टैक से सभी तर्कों और कॉल करने योग्य ऑब्जेक्ट को पॉप करता है, उन तर्कों के साथ कॉल करने योग्य ऑब्जेक्ट को कॉल करता है, और कॉल करने योग्य ऑब्जेक्ट द्वारा दिए गए रिटर्न वैल्यू को धक्का देता है।

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

इसके अलावा, ध्यान दें कि निश्चित रूप से इस मामले में कई अन्य ऑपरेशन (OP_CODES) हैं जो इस खेल में एक महत्वपूर्ण भूमिका निभाते हैं, जो मुझे लगता है कि जांच के लायक है और जिस पर विचार करने के लिए मैं इसे अभ्यास के रूप में आपके लिए जीवित हूं;)।







dictionary-comprehension