python - "1000000000000000 रेंज में(1000000000000001)" पायथन 3 में इतना तेज क्यों है?
performance python-3.x (6)
यह मेरी समझ है कि
range()
फ़ंक्शन, जो वास्तव
में पायथन 3 में एक ऑब्जेक्ट प्रकार है
, जनरेटर के समान मक्खी पर अपनी सामग्री उत्पन्न करता है।
यह मामला होने के नाते, मुझे उम्मीद है कि निम्नलिखित पंक्ति समय की एक विषम राशि लेगी, क्योंकि यह निर्धारित करने के लिए कि क्या 1 क्वाड्रिलियन सीमा में है, एक क्वाडरिलिन मान उत्पन्न करना होगा:
1000000000000000 in range(1000000000000001)
इसके अलावा: ऐसा लगता है कि कोई फर्क नहीं पड़ता कि मैं कितने शून्य जोड़ता हूं, गणना अधिक या कम समय में (मूल रूप से तात्कालिक) समान समय लेती है।
मैंने भी इस तरह की चीजों की कोशिश की है, लेकिन गणना अभी भी लगभग तत्काल है:
1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens
अगर मैं अपने स्वयं के रेंज फ़ंक्शन को लागू करने का प्रयास करता हूं, तो परिणाम इतना अच्छा नहीं है !!
def my_crappy_range(N):
i = 0
while i < N:
yield i
i += 1
return
हूड के तहत कर रही
range()
ऑब्जेक्ट क्या है जो इसे इतना तेज़ बनाता है?
मार्टिज़न पीटरर्स का उत्तर
इसकी पूर्णता के लिए चुना गया था, लेकिन पायथन 3 में एक पूर्ण
अनुक्रम
होने के लिए इसका क्या मतलब है, इसकी अच्छी चर्चा के लिए
अबर्नर्ट का पहला उत्तर
भी देखें, और
__contains__
फ़ंक्शन अनुकूलन के लिए संभावित असंगतता के बारे में कुछ जानकारी / चेतावनी। पायथन कार्यान्वयन।
एब्नर्ट का अन्य उत्तर
कुछ और विस्तार में जाता है और पायथन 3 में अनुकूलन के पीछे के इतिहास में रुचि रखने वालों के लिए लिंक प्रदान करता है (और पायथन 2 में
xrange
के अनुकूलन की कमी)।
प्रहार
और
वाइम के
उत्तर प्रासंगिक सी स्रोत कोड और रुचि रखने वालों के लिए स्पष्टीकरण प्रदान करते हैं।
टी एल; डॉ
range()
द्वारा लौटाया गया ऑब्जेक्ट वास्तव में एक
range
ऑब्जेक्ट है।
यह ऑब्जेक्ट इटरेटर इंटरफ़ेस को लागू करता है ताकि आप एक जनरेटर की तरह, अपने मूल्यों के माध्यम से क्रमिक रूप से पुनरावृति कर सकें, लेकिन यह
__contains__
इंटरफ़ेस को भी लागू करता है, जो वास्तव में क्या कहा जाता है जब ऑपरेटर
in
दाहिने हाथ की तरफ कोई वस्तु दिखाई देती है।
__contains__()
विधि वस्तु में है या नहीं, इसका एक बूल देता है।
चूंकि
range
ऑब्जेक्ट्स अपनी सीमा और स्ट्राइड को जानते हैं, इसलिए O (1) में इसे लागू करना बहुत आसान है।
अन्य उत्तर इसे पहले से ही अच्छी तरह से समझाते हैं, लेकिन मैं एक और प्रयोग की पेशकश करना चाहूंगा, जो रेंज ऑब्जेक्ट्स की प्रकृति को दर्शाता है:
>>> r = range(5)
>>> for i in r:
print(i, 2 in r, list(r))
0 True [0, 1, 2, 3, 4]
1 True [0, 1, 2, 3, 4]
2 True [0, 1, 2, 3, 4]
3 True [0, 1, 2, 3, 4]
4 True [0, 1, 2, 3, 4]
जैसा कि आप देख सकते हैं, एक श्रेणी वस्तु एक ऐसी वस्तु है जो अपनी सीमा को याद करती है और इसका उपयोग कई बार किया जा सकता है (यहां तक कि इस पर पुनरावृत्ति करते हुए), न केवल एक बार का जनरेटर।
मार्टिज़न के उत्तर में जोड़ने के लिए, यह स्रोत का प्रासंगिक हिस्सा है (सी में, जैसा कि रेंज ऑब्जेक्ट मूल कोड में लिखा गया है):
static int
range_contains(rangeobject *r, PyObject *ob)
{
if (PyLong_CheckExact(ob) || PyBool_Check(ob))
return range_contains_long(r, ob);
return (int)_PySequence_IterSearch((PyObject*)r, ob,
PY_ITERSEARCH_CONTAINS);
}
तो
PyLong
ऑब्जेक्ट्स (जो Python 3 में
int
है) के लिए, यह परिणाम निर्धारित करने के लिए
range_contains_long
फ़ंक्शन का उपयोग करेगा।
और यह फ़ंक्शन अनिवार्य रूप से जांचता है कि क्या निर्दिष्ट सीमा में है (हालांकि यह सी में थोड़ा अधिक जटिल दिखता है)।
यदि यह एक
int
ऑब्जेक्ट नहीं है, तो यह तब तक पुनरावृत्त हो जाता है जब तक कि यह मान नहीं पाता (या नहीं)।
पूरे तर्क को इस तरह से छद्म-पायथन में अनुवाद किया जा सकता है:
def range_contains (rangeObj, obj):
if isinstance(obj, int):
return range_contains_long(rangeObj, obj)
# default logic by iterating
return any(obj == x for x in rangeObj)
def range_contains_long (r, num):
if r.step > 0:
# positive step: r.start <= num < r.stop
cmp2 = r.start <= num
cmp3 = num < r.stop
else:
# negative step: r.start >= num > r.stop
cmp2 = num <= r.start
cmp3 = r.stop < num
# outside of the range boundaries
if not cmp2 or not cmp3:
return False
# num must be on a valid step inside the boundaries
return (num - r.start) % r.step == 0
यदि आप सोच रहे हैं
कि
इस अनुकूलन को श्रेणी
range.__contains__
क्यों जोड़ा गया है
xrange.__contains__
range.__contains__
, और इसे
xrange.__contains__
क्यों
नहीं
जोड़ा गया है।
सबसे पहले, जैसा कि अश्विनी चौधरी ने
खोजा
था,
मुद्दा 1766304
को स्पष्ट रूप से अनुकूलित करने के लिए खोला गया था
[x]range.__contains__
शामिल__
।
इसके लिए एक पैच को
3.2 में स्वीकार किया
गया था
और जांचा
गया था, लेकिन इसे 2.7 में वापस नहीं लाया गया क्योंकि "xrange ने इतने लंबे समय से इस तरह का व्यवहार किया है कि मैं यह नहीं देखता कि यह इस देर से पैच करने के लिए हमें क्या खरीदता है।"
(2.7 उस समय लगभग बाहर था।)
इस दौरान:
मूल रूप से,
xrange
एक काफी-अनुक्रम अनुक्रम नहीं था।
3.1 डॉक्स के अनुसार
:
रेंज ऑब्जेक्ट में बहुत कम व्यवहार होता है: वे केवल अनुक्रमण, पुनरावृत्ति और
len
फ़ंक्शन का समर्थन करते हैं।
यह बिल्कुल सच नहीं था;
xrange
ऑब्जेक्ट ने वास्तव में कुछ अन्य चीजों का समर्थन किया है जो स्वचालित रूप से अनुक्रमण और
len
साथ आते हैं,
*
__contains__
(रैखिक के माध्यम से) सहित।
लेकिन किसी ने भी यह नहीं सोचा था कि यह उस समय उन्हें पूर्ण अनुक्रम बनाने के लायक था।
फिर,
एब्सट्रैक्ट बेस क्लास
पीईपी को लागू करने के हिस्से के रूप में, यह पता लगाना महत्वपूर्ण था कि किन एबीसी के कार्यान्वयन के रूप में
xrange
प्रकारों को चिह्नित किया जाना चाहिए और
collections.Sequence
को लागू करने के लिए
xrange
/
range
दावा किया गया। हालांकि, यह अभी भी केवल उसी को संभाला है " थोड़ा व्यवहार ”।
9213 के अंक
तक किसी ने भी उस समस्या पर ध्यान नहीं दिया।
उस इश्यू के लिए पैच न केवल
index
और 3.2 की
range
count
जाता है, यह अनुकूलित
__contains__
(जो
index
साथ एक ही गणित साझा करता है, और सीधे
count
द्वारा उपयोग किया जाता
count
) पर भी काम करता है।
**
यह परिवर्तन
3.2 के रूप में अच्छी तरह से चला गया, और 2.x पर वापस नहीं भेजा गया, क्योंकि "यह एक बगफिक्स है जो नए तरीके जोड़ता है"।
(इस बिंदु पर, 2.7 पहले से ही आरसी स्थिति था।)
इसलिए, इस अनुकूलन को 2.7 में वापस लाने के लिए दो मौके थे, लेकिन वे दोनों खारिज कर दिए गए थे।
* वास्तव में, आपको अकेले ही इंडेक्सिंग के साथ मुफ्त में पुनरावृति मिलती है, लेकिन
2.3
xrange
ऑब्जेक्ट्स में एक कस्टम
xrange
मिला।
** पहले संस्करण ने वास्तव में इसे फिर से लागू किया, और विवरण गलत
MyIntSubclass(2) in range(5) == False
जैसे, यह आपको
MyIntSubclass(2) in range(5) == False
।
लेकिन डैनियल स्टुट्ज़बैच के पैच के अपडेट किए गए संस्करण ने पिछले कोड के अधिकांश हिस्से को बहाल कर दिया, जिसमें जेनेरिक, धीमी
_PySequence_IterSearch
जो कि प्री-3.2
range.__contains__
का उपयोग तब किया गया जब अनुकूलन लागू नहीं होता है।
यहां मूलभूत गलतफहमी इस सोच में है कि
range
एक जनरेटर है।
यह।
वास्तव में, यह किसी भी प्रकार का पुनरावृत्ति नहीं है।
आप इसे बहुत आसानी से बता सकते हैं:
>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]
यदि यह एक जनरेटर था, तो इसे एक बार पुनरावृत्त करने से यह समाप्त हो जाएगा:
>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]
वास्तव में क्या
range
है, एक अनुक्रम है, एक सूची की तरह।
आप इसका परीक्षण भी कर सकते हैं:
>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True
इसका मतलब यह है कि इसे अनुक्रम होने के सभी नियमों का पालन करना है:
>>> a[3] # indexable
3
>>> len(a) # sized
5
>>> 3 in a # membership
True
>>> reversed(a) # reversible
<range_iterator at 0x101cd2360>
>>> a.index(3) # implements 'index'
3
>>> a.count(3) # implements 'count'
1
एक
range
और
list
बीच का अंतर यह है कि एक
range
एक
आलसी
या
गतिशील
अनुक्रम है;
यह अपने सभी मूल्यों को याद नहीं करता है, यह सिर्फ
__getitem__
पर मांग को
start
,
stop
और
step
याद
stop
, और मूल्यों को बनाता है।
(एक साइड नोट के रूप में, यदि आप
print(iter(a))
करते हैं, तो आप ध्यान देंगे कि वह
range
list
के समान ही एक
list
listiterator
प्रकार का उपयोग करती है। वह काम कैसे करता है? एक
list
इस तथ्य को छोड़कर
list
बारे में कुछ विशेष का उपयोग नहीं करता है। यह
__getitem__
का C कार्यान्वयन प्रदान करता है, इसलिए यह
range
भी ठीक काम करता है।)
अब, ऐसा कुछ भी नहीं है जो कहता है कि
Sequence.__contains__
निरंतर समय होना चाहिए - वास्तव में,
list
जैसे अनुक्रमों के स्पष्ट उदाहरणों के
list
, यह नहीं है।
लेकिन ऐसा कुछ नहीं है जो कहता है कि यह
नहीं
हो सकता है।
और यह
range.__contains__
को लागू करना आसान है
range.__contains__
केवल गणितीय रूप से (
(val - start) % step
, लेकिन वास्तव में सभी मूल्यों को उत्पन्न करने और परीक्षण करने की तुलना में नकारात्मक चरणों से निपटने के लिए कुछ अतिरिक्त जटिलता के साथ, इसलिए ऐसा क्यों
नहीं करना चाहिए
यह बेहतर तरीका है?
लेकिन भाषा में ऐसा कुछ भी नहीं प्रतीत होता है जो इसकी गारंटी देता हो। जैसा कि अश्विनी चौधरी बताते हैं, यदि आप इसे पूर्णांक में परिवर्तित करने और गणितीय परीक्षण करने के बजाय इसे एक अभिन्न मूल्य देते हैं, तो यह सभी मूल्यों को पुनरावृत्त करने और एक-एक करके उनकी तुलना करने के लिए वापस आ जाएगा। और सिर्फ इसलिए कि CPython 3.2+ और PyPy 3.x संस्करणों में यह अनुकूलन होता है, और यह एक स्पष्ट अच्छा विचार है और इसे करना आसान है, कोई कारण नहीं है कि IronPython या NewKickAssPython 3.x इसे छोड़ नहीं सकता। (और वास्तव में CPython 3.0-3.1 में यह शामिल नहीं था ।)
यदि
range
वास्तव में एक जनरेटर थे, जैसे
my_crappy_range
, तो यह इस तरह से
__contains__
का परीक्षण करने के लिए समझ में नहीं आता है, या कम से कम जिस तरह से यह समझ में आता है वह स्पष्ट नहीं होगा।
यदि आप पहले से ही पहले 3 मानों की पुनरावृत्ति कर चुके हैं, तो क्या जनरेटर
in
अभी भी
1
?
1
लिए परीक्षण करने के लिए इसे पुनरावृत्त करना चाहिए और
1
(या पहले मूल्य
>= 1
) तक के सभी मूल्यों का उपभोग करना चाहिए?
source उपयोग करें, ल्यूक!
CPython में,
range(...).__contains__
(एक विधि आवरण) अंततः एक साधारण गणना में प्रतिनिधि होगा जो जाँचता है कि मान संभवतः सीमा में हो सकता है।
यहां गति का कारण हम
सीमा वस्तु के प्रत्यक्ष पुनरावृत्ति के बजाय सीमा के बारे में गणितीय तर्क
का उपयोग कर रहे हैं।
प्रयुक्त तर्क की व्याख्या करने के लिए:
-
जाँच लें कि संख्या
start
औरstop
बीच है, और - जाँचें कि स्ट्राइड वैल्यू हमारी संख्या को "स्टेप ओवर" नहीं करती है।
उदाहरण के लिए,
994
range(4, 1000, 2)
क्योंकि:
-
4 <= 994 < 1000
, और -
(994 - 4) % 2 == 0
।
पूर्ण सी कोड नीचे शामिल किया गया है, जो कि स्मृति प्रबंधन और संदर्भ गिनती विवरण के कारण थोड़ा अधिक क्रिया है, लेकिन मूल विचार यह है:
static int
range_contains_long(rangeobject *r, PyObject *ob)
{
int cmp1, cmp2, cmp3;
PyObject *tmp1 = NULL;
PyObject *tmp2 = NULL;
PyObject *zero = NULL;
int result = -1;
zero = PyLong_FromLong(0);
if (zero == NULL) /* MemoryError in int(0) */
goto end;
/* Check if the value can possibly be in the range. */
cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
if (cmp1 == -1)
goto end;
if (cmp1 == 1) { /* positive steps: start <= ob < stop */
cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
}
else { /* negative steps: stop < ob <= start */
cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
}
if (cmp2 == -1 || cmp3 == -1) /* TypeError */
goto end;
if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
result = 0;
goto end;
}
/* Check that the stride does not invalidate ob's membership. */
tmp1 = PyNumber_Subtract(ob, r->start);
if (tmp1 == NULL)
goto end;
tmp2 = PyNumber_Remainder(tmp1, r->step);
if (tmp2 == NULL)
goto end;
/* result = ((int(ob) - start) % step) == 0 */
result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
end:
Py_XDECREF(tmp1);
Py_XDECREF(tmp2);
Py_XDECREF(zero);
return result;
}
static int
range_contains(rangeobject *r, PyObject *ob)
{
if (PyLong_CheckExact(ob) || PyBool_Check(ob))
return range_contains_long(r, ob);
return (int)_PySequence_IterSearch((PyObject*)r, ob,
PY_ITERSEARCH_CONTAINS);
}
विचार का "मांस" लाइन में उल्लिखित है:
/* result = ((int(ob) - start) % step) == 0 */
अंतिम नोट के रूप में - कोड स्निपेट के निचले भाग में
range_contains
फ़ंक्शन देखें।
यदि सटीक प्रकार की जाँच विफल हो जाती है, तो हम वर्णित चतुर एल्गोरिथ्म का उपयोग नहीं करते हैं, इसके बजाय
_PySequence_IterSearch
का उपयोग करके सीमा के गूंगे पुनरावृत्ति खोज पर वापस
_PySequence_IterSearch
!
आप दुभाषिया में इस व्यवहार की जाँच कर सकते हैं (मैं यहाँ v3.5.0 का उपयोग कर रहा हूँ):
>>> x, r = 1000000000000000, range(1000000000000001)
>>> class MyInt(int):
... pass
...
>>> x_ = MyInt(x)
>>> x in r # calculates immediately :)
True
>>> x_ in r # iterates for ages.. :(
^\Quit (core dumped)