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
एक सीधा आदमी नहीं है जो तुरंत फ़ंक्शन को कॉल करेगा, यह नहीं कर सकता।
इसके बजाय, यह स्टैक से ऑब्जेक्ट को पकड़ता है, स्टैक के सभी तर्कों को पकड़ लेता है और फिर ऑब्जेक्ट के प्रकार के आधार पर स्विच करता है;
क्या यह:
-
PyCFunction_Type
? नहीं, यहlist
,list
प्रकारPyCFunction
-
PyMethodType
? नहीं, पिछले देखें। -
PyFunctionType
? Nopee, पिछले देखें।
हम
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