python - "1000000000000000 रेंज में(1000000000000001)" पायथन 3 में इतना तेज क्यों है?

टी एल; डॉ

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__ (एक विधि आवरण) अंततः एक साधारण गणना में प्रतिनिधि होगा जो जाँचता है कि मान संभवतः सीमा में हो सकता है। यहां गति का कारण हम सीमा वस्तु के प्रत्यक्ष पुनरावृत्ति के बजाय सीमा के बारे में गणितीय तर्क का उपयोग कर रहे हैं। प्रयुक्त तर्क की व्याख्या करने के लिए:

1. जाँच लें कि संख्या start और stop बीच है, और
2. जाँचें कि स्ट्राइड वैल्यू हमारी संख्या को "स्टेप ओवर" नहीं करती है।

उदाहरण के लिए, 994 range(4, 1000, 2) क्योंकि:

1. 4 <= 994 < 1000 , और
2. (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)