python - क्यों[] सूची से तेज है()?




performance list (4)

क्यों [] list() से तेज है list() ?

सबसे बड़ा कारण यह है कि पायथन एक उपयोगकर्ता-परिभाषित फ़ंक्शन की तरह list() इलाज करता है, जिसका अर्थ है कि आप इसे किसी अन्य चीज़ को list और कुछ अलग करने के list इसे रोक सकते हैं (जैसे कि अपनी खुद की उप-सूचीबद्ध सूची या शायद एक छल का उपयोग करें)।

यह तुरंत [] साथ एक अंतर्निहित सूची का एक नया उदाहरण बनाता है।

मेरी व्याख्या आपको इसके लिए अंतर्ज्ञान देना चाहती है।

व्याख्या

[] आमतौर पर शाब्दिक वाक्य रचना के रूप में जाना जाता है।

व्याकरण में, इसे "सूची प्रदर्शन" के रूप में संदर्भित किया जाता है। डॉक्स से :

एक सूची प्रदर्शन वर्ग कोष्ठक में संलग्न भावों की संभवतः एक खाली श्रृंखला है: 

list_display ::=  "[" [starred_list | comprehension] "]"

एक सूची प्रदर्शन एक नई सूची ऑब्जेक्ट, अभिव्यक्तियों की एक सूची या एक समझ द्वारा निर्दिष्ट की जा रही सामग्री देता है। जब भावों की अल्पविराम से अलग की गई सूची की आपूर्ति की जाती है, तो उसके तत्वों का मूल्यांकन बाएं से दाएं किया जाता है और उस क्रम में सूची ऑब्जेक्ट में रखा जाता है। जब एक समझ की आपूर्ति की जाती है, तो सूची का निर्माण उन तत्वों से किया जाता है जो समझ से उत्पन्न होते हैं।

संक्षेप में, इसका मतलब है कि प्रकार list का एक अंतर्निहित ऑब्जेक्ट बनाया गया है।

इसको दरकिनार नहीं किया जाता है - जिसका अर्थ है कि पायथन इसे जल्दी से जल्दी कर सकता है।

दूसरी ओर, list() को बिलिन सूची के निर्माणकर्ता का उपयोग करके एक बिलिन list बनाने से रोका जा सकता है।

उदाहरण के लिए, मान लें कि हम चाहते हैं कि हमारी सूचियाँ उत्तरोत्तर बनाई जाएं: 

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

हम तब मॉड्यूल स्तर के वैश्विक दायरे पर नाम list को रोक सकते हैं, और फिर जब हम एक list बनाते हैं, तो हम वास्तव में हमारी उप-सूची सूची बनाते हैं: 

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

इसी तरह हम इसे वैश्विक नाम स्थान से हटा सकते हैं 

del list

और इसे बिलियन नेमस्पेस में रखा: 

import builtins
builtins.list = List

और अब: 

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

और ध्यान दें कि सूची प्रदर्शन बिना शर्त के एक सूची बनाता है: 

>>> list_1 = []
>>> type(list_1)
<class 'list'>

हम शायद केवल यह अस्थायी रूप से करते हैं, इसलिए हमारे परिवर्तनों को पूर्ववत करें - पहले बिलिंस से नई List ऑब्जेक्ट निकालें: 

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

ओह, नहीं, हमने मूल का ट्रैक खो दिया है।

चिंता न करें, हम अभी भी list प्राप्त कर सकते हैं - यह सूची शाब्दिक का प्रकार है: 

>>> builtins.list = type([])
>>> list()
[]

इसलिए...

क्यों [] list() से तेज है list() ?

जैसा कि हमने देखा है - हम list को ओवरराइट कर सकते हैं - लेकिन हम शाब्दिक प्रकार के निर्माण को रोक नहीं सकते हैं। जब हम list उपयोग करते हैं तो हमें यह देखने के लिए कि क्या कुछ है, देखने के लिए क्या करना है।

फिर हमें जो भी कॉल करने योग्य है, उसे देखना होगा। व्याकरण से:

एक कॉल कॉलिबल ऑब्जेक्ट (उदाहरण के लिए, एक फ़ंक्शन) को संभवतः तर्कों की खाली श्रृंखला के साथ कहता है: 

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

हम देख सकते हैं कि यह किसी भी नाम के लिए समान कार्य करता है, न कि केवल सूची के लिए: 

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

[] लिए पायथन बाइटकोड स्तर पर कोई फ़ंक्शन कॉल नहीं है: 

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

यह बस सीधे किसी भी लुकअप या कॉल के बिना सूची को बनाने के लिए जाता है।

निष्कर्ष

हमने प्रदर्शित किया है कि स्कोपिंग नियमों का उपयोग करके उपयोगकर्ता कोड के साथ list को इंटरसेप्ट किया जा सकता है, और वह list() एक कॉल करने योग्य लगती है और फिर उसे कॉल करती है।

जबकि [] एक सूची प्रदर्शन, या एक शाब्दिक है, और इस प्रकार नाम देखने और फ़ंक्शन कॉल से बचा जाता है।

मैंने हाल ही में [] और list() की प्रोसेसिंग गति list() की तुलना की और यह जानकर आश्चर्य हुआ कि [] list() तुलना में तीन गुना अधिक तेजी से चलता है। मैंने {} और dict() साथ एक ही परीक्षण चलाया और परिणाम व्यावहारिक रूप से समान थे: [] और {} दोनों ने लगभग 0.128sec / मिलियन चक्र लिया, जबकि list() और तानाशाह dict() ने लगभग 0.428sec / मिलियन चक्र लिया।

ऐसा क्यों है? क्या [] और {} (और शायद () और '' , भी) तुरंत कुछ खाली स्टॉक शाब्दिक की प्रतियां वापस कर देते हैं जबकि उनके स्पष्ट रूप से नामित समकक्षों ( list() , dict() , tuple() , str() ) पूरी तरह से एक वस्तु बनाने के बारे में जाना, चाहे वे वास्तव में तत्व हैं या नहीं?

मुझे नहीं पता कि ये दोनों तरीके कैसे भिन्न हैं, लेकिन मुझे पता लगाना अच्छा लगेगा। मुझे डॉक्स या एसओ में कोई उत्तर नहीं मिला, और खाली कोष्ठक की खोज से मैं उम्मीद से अधिक समस्याग्रस्त हो गया।

मैंने timeit.timeit("[]") और timeit.timeit("list()") , और timeit.timeit("{}") और timeit.timeit("dict()") को कॉल करके अपने समय के परिणाम प्राप्त किए। क्रमशः सूचियों और शब्दकोशों की तुलना करने के लिए। मैं पायथन 2.7.9 चला रहा हूं।

मैंने हाल ही में पाया कि " Why is True Slower if if 1? " जो कि if True से if 1 के प्रदर्शन की तुलना करता है और एक समान शाब्दिक-बनाम-वैश्विक परिदृश्य पर स्पर्श करता है। शायद यह विचार करने लायक भी है।

क्योंकि [] और {} शाब्दिक वाक्यविन्यास हैं । पायथन सिर्फ सूची या शब्दकोश वस्तुओं को बनाने के लिए बायटेकोड बना सकता है: 

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE

list() और dict() अलग-अलग वस्तुएं हैं। उनके नामों को हल करने की आवश्यकता है, तर्कों को धक्का देने के लिए शामिल किया जाना है, बाद में पुनः प्राप्त करने के लिए फ्रेम को संग्रहीत करना होगा, और एक कॉल करना होगा। वह सब अधिक समय लेता है।

खाली मामले के लिए, इसका मतलब है कि आपके पास बहुत कम से कम एक LOAD_NAME (जिसे वैश्विक नामस्थान के साथ-साथ __builtin__ मॉड्यूल के माध्यम से खोजना होगा) इसके बाद एक CALL_FUNCTION , जिसे वर्तमान फ्रेम को संरक्षित करना है: 

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE

आप समय के साथ नाम देखने का समय अलग कर सकते हैं: 

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

समय की विसंगति शायद एक शब्दकोश हैश टक्कर है। उन वस्तुओं को कॉल करने के लिए समय से घटाएं, और शाब्दिक का उपयोग करने के लिए समय के खिलाफ परिणाम की तुलना करें: 

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

तो वस्तु को कॉल करने में अतिरिक्त 1.00 - 0.31 - 0.30 == 0.39 सेकंड प्रति 10 मिलियन कॉल लगता है।

आप स्थानीय नामों के रूप में वैश्विक नामों को अलग करके वैश्विक लुकअप लागत से बच सकते हैं (एक timeit सेटअप का उपयोग करके, आप जो कुछ भी नाम से बांधते हैं वह एक स्थानीय है): 

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

लेकिन आप कभी भी उस CALL_FUNCTION लागत को पार नहीं कर सकते।

यहाँ उत्तर बहुत अच्छे हैं, इस बिंदु पर और इस प्रश्न को पूरी तरह से कवर करते हैं। मैं रुचि रखने वालों के लिए बाइट-कोड से एक और कदम नीचे छोड़ दूँगा। मैं सीपीथॉन के सबसे हालिया रेपो का उपयोग कर रहा हूं; पुराने संस्करण इस संबंध में समान व्यवहार करते हैं लेकिन इसमें थोड़े बदलाव हो सकते हैं।

इनमें से प्रत्येक के लिए निष्पादन का ब्रेक डाउन है, [] लिए CALL_FUNCTION और list() लिए CALL_FUNCTION ।

BUILD_LIST निर्देश:

आपको बस हॉरर देखना चाहिए: 

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

मैं बहुत जानता हूं। यह कितना सरल है:

  • PyList_New साथ एक नई सूची बनाएं (यह मुख्य रूप से एक नई सूची ऑब्जेक्ट के लिए मेमोरी आवंटित करता है), स्टैक पर तर्कों की संख्या को oparg करते हुए oparg । सीधा मुद्दे पर।
  • जांचें कि if (list==NULL) कुछ भी गलत नहीं हुआ है।
  • PyList_SET_ITEM (मैक्रो) के साथ स्टैक पर स्थित कोई भी तर्क जोड़ें (हमारे मामले में इसे निष्पादित नहीं किया गया है)।

कोई आश्चर्य नहीं कि यह तेज है! यह नई सूची बनाने के लिए कस्टम बनाया गया है, और कुछ नहीं :-)

CALL_FUNCTION निर्देश:

जब आप CALL_FUNCTION हैंडल करने वाले कोड को देखते हैं, तो पहली बात यह है: 

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

बहुत हानिरहित लगता है, है ना? खैर, नहीं, दुर्भाग्य से नहीं, call_function एक सीधा आदमी नहीं है जो तुरंत फ़ंक्शन को कॉल करेगा, यह नहीं कर सकता। इसके बजाय, यह स्टैक से ऑब्जेक्ट को पकड़ता है, स्टैक के सभी तर्कों को पकड़ लेता है और फिर ऑब्जेक्ट के प्रकार के आधार पर स्विच करता है; क्या यह:

हम list प्रकार को कॉल कर रहे हैं, call_function में पारित तर्क call_function है। CPython को अब _PyObject_FastCallKeywords नामक किसी भी कॉल करने योग्य ऑब्जेक्ट को संभालने के लिए एक जेनेरिक फ़ंक्शन को कॉल करना है, और अधिक फ़ंक्शन कॉल करें।

यह फ़ंक्शन फिर से कुछ फ़ंक्शन प्रकारों के लिए कुछ जांच करता है (जो मुझे समझ में नहीं आता है) और फिर, यदि आवश्यक हो तो kwargs के लिए एक _PyObject_FastCallDict बनाने के बाद, _PyObject_FastCallDict पर कॉल करने के लिए जाता है।

_PyObject_FastCallDict आखिरकार हमें कहीं मिलता है! और भी अधिक जाँच करने के बाद यह tp_call स्लॉट को उस type के type से पकड़ लेता है, जिस type हम पास हुए हैं, यानी यह type.tp_call पकड़ लेता है। यह तब _PyStack_AsTuple साथ पारित तर्कों से एक टपल बनाने के लिए आगे _PyStack_AsTuple और अंत में, एक कॉल आखिरकार किया जा सकता है !

tp_call , जो कि type.__call__ मेल खाता है type.__call__ लेता है और अंत में सूची ऑब्जेक्ट बनाता है। यह सूचियों को __new__ कहता है जो __new__ से मेल खाती है और PyType_GenericNew साथ इसके लिए मेमोरी आवंटित PyType_GenericAlloc : यह वास्तव में वह हिस्सा है जहां यह PyList_New साथ अंत में पकड़ लेता है । सभी पिछले एक सामान्य फैशन में वस्तुओं को संभालने के लिए आवश्यक हैं।

अंत में, type_call कॉल list.__init__ और किसी भी उपलब्ध तर्कों के साथ सूची को इनिशियलाइज़ करती है, फिर हम जिस तरह से आए थे, उसी तरह वापस लौटते हैं। :-)

अंत में, LOAD_NAME को LOAD_NAME , यह एक और लड़का है जो यहां योगदान देता है।

यह देखना आसान है कि, हमारे इनपुट के साथ काम करते समय, पायथन को आमतौर पर हुप्स के माध्यम से कूदना पड़ता है ताकि वास्तव में काम करने के लिए उपयुक्त C फ़ंक्शन का पता लगाया जा सके। इसमें तुरंत कॉल करने की शंका नहीं है क्योंकि यह गतिशील है, कोई व्यक्ति नकाब list ( और लड़का कई लोग करते हैं ) और दूसरा रास्ता लेना होगा।

यह वह जगह है जहाँ list() बहुत खो देती है: पायथन की खोज यह जानने के लिए करने की आवश्यकता है कि इसे क्या करना चाहिए।

दूसरी ओर, साहित्यिक वाक्य रचना, वास्तव में एक चीज का मतलब है; इसे बदला नहीं जा सकता है और हमेशा पूर्व-निर्धारित तरीके से व्यवहार किया जाता है।

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

list() लिए एक वैश्विक खोज और एक फ़ंक्शन कॉल की आवश्यकता होती है लेकिन [] एक निर्देश के लिए संकलित करता है। देख: 

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None



python   performance   list   instantiation   literals  


literals