python - পাইথন 3 এ এত দ্রুত কেন "1000000000000000 পরিসীমা(1000000000000001)"?

অন্য উত্তরগুলি এটিকে ভালভাবেই ব্যাখ্যা করেছে, তবে আমি পরিসর বস্তুর প্রকৃতির বর্ণনা করে আরেকটি পরীক্ষা দিতে চাই:

>>> 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]

আপনি দেখতে পারেন যে, একটি পরিসীমা বস্তু এমন একটি বস্তু যা তার পরিসীমা মনে রাখে এবং এটি এক সময় জেনারেটর নয় বরং এটি অনেক বার (এমনকি এটি পুনরাবৃত্তির সময়) ব্যবহার করা যেতে পারে।

আপনি যদি এই অপ্টিমাইজেশানটি range.__contains__ কেন যোগ করা হয় তা নিয়ে xrange.__contains__ হয়ে থাকেন xrange.__contains__ এটি range.__contains__ এবং কেন এটি xrange.__contains__ যোগ করা হয়নি xrange.__contains__ মধ্যে xrange.__contains__ ২7:

প্রথমত, যেমন অশ্বিনী চৌধুরী আবিষ্কার করেছিলেন, 1766304 ইস্যু স্পষ্টভাবে খোলা হয়েছিল [x]range.__contains__ । এর জন্য একটি প্যাচ গৃহীত হয়েছিল এবং 3.2 এর জন্য চেক করা হয়েছিল , কিন্তু 2.7 তে ব্যাকপোর্ট করা হয়নি কারণ "xrange এত দীর্ঘ সময়ের জন্য এটির মতো আচরণ করেছে, যা আমি দেখেছি না যে এটি আমাদের দেরিতে এই প্যাচটি কেনার জন্য কিনেছে।" (2.7 যে সময়ে প্রায় আউট ছিল।)

এদিকে:

মূলত, xrange একটি নন-বেশ ক্রম-বস্তু ছিল। 3.1 ডক্স বলেছেন:

বিন্যাস বস্তুর খুব ছোট আচরণ আছে: তারা কেবল সূচী, পুনরাবৃত্তি এবং len ফাংশন সমর্থন করে।

এই বেশ সত্য ছিল না; একটি xrange বস্তু প্রকৃতপক্ষে ইন্ডেক্সিং এবং len সহ স্বয়ংক্রিয়ভাবে আসা কিছু অন্যান্য জিনিসগুলিকে সমর্থন করে, ^* __contains__ সহ (রৈখিক অনুসন্ধানের মাধ্যমে)। কিন্তু কেউ এ সময় তাদের সম্পূর্ণ ক্রম তৈরীর মূল্য ছিল চিন্তা।

তারপরে, বিমূর্ত বেস ক্লাস PEP বাস্তবায়ন করার অংশ হিসাবে, এটি তৈরি করা উচিত যে কোন xrange এবং xrange / range collections.Sequence বাস্তবায়নের xrange প্রয়োগ করা উচিত তা চিহ্নিত করা গুরুত্বপূর্ণ। xrange যদিও এটি এখনও "একই" সামান্য আচরণ "। 9213 ইস্যু পর্যন্ত সমস্যাটি কেউ লক্ষ্য করেনি । সেই সমস্যাটির জন্য প্যাচটি কেবল index যোগ করেনি এবং 3.2 এর range count করে, এটি অপ্টিমাইজ করা __contains__ পুনরায় কাজ করে (যা index সহ একই গণিত ভাগ করে এবং সরাসরি count করে ব্যবহৃত হয়)। ^** এই পরিবর্তন 3.2 এর জন্যও গিয়েছিল এবং 2.x তে ব্যাকপোর্ট করা হয়নি কারণ "এটি একটি বাগফিক্স যা নতুন পদ্ধতি যোগ করে"। (এই সময়ে, 2.7 ইতিমধ্যে গত আরসি অবস্থা ছিল।)

সুতরাং, এই অপ্টিমাইজেশান 2.7 ব্যাকপোর্ট করার দুটি সুযোগ ছিল, কিন্তু তারা উভয় প্রত্যাখ্যাত হয়।

_{* আসলে, আপনি এমনকি len এবং সূচকের সাথে বিনামূল্যে পুনরাবৃত্তি পান, কিন্তু 2.3 xrange বস্তুগুলিতে একটি কাস্টম ইটারারেটর পেয়েছে। যা পরে তারা 3.x হারিয়ে গেছে, যা list হিসাবে একই list listiterator টাইপ ব্যবহার করে।}

_{** প্রথম সংস্করণটি আসলে এটি পুনঃপ্রতিষ্ঠিত করেছে, এবং বিশদটি ভুল পেয়েছে - যেমন, এটি আপনাকে MyIntSubclass(2) in range(5) == False । কিন্তু ড্যানিয়েল স্টুটজ্যাচের প্যাচের আপডেট হওয়া সংস্করণটি পূর্ববর্তী কোডটি সর্বাধিক পূর্ববর্তী পুনরুদ্ধার করে, জেনারিক, ধীর _PySequence_IterSearch যা পূর্ব _PySequence_IterSearch range.__contains__ ।}

এটা মূল্যায়ন সম্পর্কে অলস পদ্ধতির, এবং range কিছু অতিরিক্ত অনুকূলিতকরণ। রেঞ্জের মানগুলির প্রকৃত ব্যবহার না হওয়া পর্যন্ত বা অতিরিক্ত অপটিমাইজেশনের কারণে এমনকি ফিশারটি গণনা করার প্রয়োজন নেই।

আপনার পূর্ণসংখ্যা এত বড় না ভাবে, sys.maxsize বিবেচনা sys.maxsize

sys.maxsize in range(sys.maxsize) বেশ দ্রুত

অপ্টিমাইজেশনের কারণে - এটি কেবলমাত্র মিনিট এবং পরিসীমা সর্বাধিক প্রদত্ত পূর্ণসংখ্যা তুলনা করা সহজ।

কিন্তু:

float(sys.maxsize) in range(sys.maxsize) বেশ ধীর ।

(এই ক্ষেত্রে range কোন অপ্টিমাইজেশান আছে, তাই অপ্রত্যাশিত ভাসা পাবেন, পাইথন সব সংখ্যা তুলনা করা হবে)

পাইথন 3 range() অবজেক্ট অবিলম্বে সংখ্যা উত্পাদন করে না; এটি একটি স্মার্ট ক্রম বস্তু যে চাহিদা সংখ্যা উত্পন্ন করে । এটিতে আপনার শুরু, স্টপ এবং ধাপের মান রয়েছে, তারপর আপনি বস্তুর উপর পুনরাবৃত্তি হিসাবে পরবর্তী পূর্ণসংখ্যা প্রতিটি পুনরাবৃত্তি গণনা করা হয়।

বস্তু এছাড়াও বস্তু প্রয়োগ করে object.__contains__ হুক , এবং আপনার সংখ্যা তার পরিসীমা অংশ যদি গণনা করে । গণনা একটি O (1) ধ্রুবক সময় অপারেশন। পরিসীমা সব সম্ভব পূর্ণসংখ্যার মাধ্যমে স্ক্যান করার প্রয়োজন নেই।

range() থেকে range() বস্তু ডকুমেন্টেশন :

একটি নিয়মিত list বা tuple উপর range টাইপের সুবিধা হল যে পরিসরের বস্তুটি সর্বদা একই (ছোট) পরিমাণে মেমরি গ্রহণ করবে, এটি পরিসরের আকারের মাপসই হোক না কেন (এটি কেবল start , stop এবং step মানগুলি সংরক্ষণ করে , প্রয়োজন হিসাবে পৃথক আইটেম এবং subranges গণনা)।

তাই সর্বনিম্ন, আপনার range() বস্তু করবে:

class my_range(object):
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = start, stop, step
        if step < 0:
            lo, hi = stop, start
        else:
            lo, hi = start, stop
        self.length = ((hi - lo - 1) // abs(step)) + 1

    def __iter__(self):
        current = self.start
        if self.step < 0:
            while current > self.stop:
                yield current
                current += self.step
        else:
            while current < self.stop:
                yield current
                current += self.step

    def __len__(self):
        return self.length

    def __getitem__(self, i):
        if i < 0:
            i += self.length
        if 0 <= i < self.length:
            return self.start + i * self.step
        raise IndexError('Index out of range: {}'.format(i))

    def __contains__(self, num):
        if self.step < 0:
            if not (self.stop < num <= self.start):
                return False
        else:
            if not (self.start <= num < self.stop):
                return False
        return (num - self.start) % self.step == 0

এটি এখনও অনেকগুলি জিনিস অনুপস্থিত রয়েছে যা একটি আসল range() (যেমন .index() অথবা .count() পদ্ধতি, হ্যাশিং, সমতা পরীক্ষার, বা slicing) সমর্থন করে তবে আপনাকে একটি ধারণা দিতে হবে।

আমি __contains__ বাস্তবায়নকে কেবলমাত্র পূর্ণসংখ্যা পরীক্ষাগুলিতে ফোকাস করার জন্য সরলীকৃত করেছি; যদি আপনি একটি বাস্তব range() int একটি পূর্ণসংখ্যা মান (অন্তর্নিবেশের উপশ্রেণী সহ range() অবজেক্ট দেন তবে একটি মন্থর স্ক্যান শুরু হয় কিনা তা দেখার জন্য শুরু হয়, ঠিক যেমন আপনি যদি সমস্ত অন্তর্ভুক্ত মানের তালিকাগুলির বিরুদ্ধে একটি সুরক্ষা পরীক্ষা ব্যবহার করেন । এটি অন্যান্য সংখ্যাসূচক প্রকারগুলিকে সমর্থন করে যা কেবলমাত্র পূর্ণসংখ্যার সাথে সমতা পরীক্ষার সমর্থন করার জন্য ঘটতে পারে তবে পূর্ণসংখ্যা গাণিতিক সমর্থন করার জন্য প্রত্যাশিত নয়। সংক্রমণ পরীক্ষা বাস্তবায়ন যে মূল পাইথন সমস্যা দেখুন।

source ব্যবহার করুন, লুক!

সিপিথন ইন, range(...).__contains__ (একটি পদ্ধতি মোড়ক) অবশেষে একটি সহজ হিসাবের প্রতিনিধিত্ব করবে যা মানটি পরিসীমা হতে পারে কিনা তা যাচাই করে। গতির কারণ এখানে আমরা সীমার বিষয়ে গাণিতিক যুক্তি ব্যবহার করছি , পরিসরের বস্তুর সরাসরি পুনরাবৃত্তি করার পরিবর্তে । ব্যবহৃত যুক্তি ব্যাখ্যা করার জন্য:

1. সংখ্যা start এবং stop , এবং মধ্যে মধ্যে চেক করুন
2. Stride মান আমাদের সংখ্যা "ধাপে" না চেক করুন।

উদাহরণস্বরূপ, 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 পুনরাবৃত্তি অনুসন্ধানে ফিরে _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)