python - لماذا "1000000000000000 في النطاق(1000000000000001)" بسرعة كبيرة في بيثون 3؟




performance python-3.x (6)

أفهم أن الدالة range() ، والتي هي في الواقع نوع كائن في Python 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() أسفل الغطاء الذي يجعله سريعًا؟

تم اختيار إجابة Martijn Pieters لإكمالها ، ولكن انظر أيضًا إجابة abarnert الأولى للحصول على مناقشة جيدة لما يعنيه أن يكون range سلسلة كاملة في Python 3 ، وبعض المعلومات / التحذير فيما يتعلق بعدم الاتساق المحتمل __contains__ across تطبيقات بيثون. تتطرق الإجابة الأخرى من abarnert إلى مزيد من التفاصيل وتوفر روابط للمهتمين بالتاريخ وراء التحسين في Python 3 (والافتقار إلى تحسين xrange في Python 2). الإجابات من الوخزة وبواسطة wim توفر شفرة المصدر C ذات الصلة وشروحات لأولئك الذين يهتمون.


TL، DR

الكائن الذي تم إرجاعه بواسطة range() هو في الواقع كائن range . ينفّذ هذا الكائن واجهة التكرار حتى تتمكن من التكرار من خلال قيمه بالتتابع ، تمامًا مثل المولد ، لكنه ينفذ أيضًا واجهة __contains__ والتي يتم استدعاؤها بالفعل عندما يظهر كائن على الجانب الأيمن من عامل التشغيل. إرجاع الأسلوب __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]

كما ترون ، كائن النطاق هو كائن يتذكر نطاقه ويمكن استخدامه عدة مرات (حتى أثناء التكرار فوقه) ، وليس مجرد مولد لمرة واحدة.


استخدم source ، لوقا!

في CPython ، سيتم تفويض range(...).__contains__ (برنامج التفاف) إلى عملية حسابية بسيطة تتحقق مما إذا كان من الممكن أن تكون القيمة في النطاق. سبب السرعة هنا هو أننا نستخدم التفكير الرياضي حول الحدود ، بدلاً من التكرار المباشر لكائن النطاق . لشرح المنطق المستخدم:

  1. تحقق من أن الرقم بين start stop ، و
  2. تحقق من أن قيمة الخطوة لا "تتجاوز" رقمنا.

على سبيل المثال ، 994 في range(4, 1000, 2) بسبب:

  1. 4 <= 994 < 1000 ، و
  2. (994 - 4) % 2 == 0 .

يتم تضمين رمز C الكامل أدناه ، وهو مطوّل قليلاً نظرًا لإدارة الذاكرة وتفاصيل عد المرجع ، لكن الفكرة الأساسية موجودة:

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 ! يمكنك التحقق من هذا السلوك في المترجم (أنا أستخدم الإصدار 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)

الأمر كله يتعلق بنهج كسول للتقييم وبعض التحسين الإضافي range . القيم في النطاقات لا تحتاج إلى حساب حتى الاستخدام الحقيقي ، أو حتى بسبب التحسين الإضافي.

بالمناسبة ، العدد الصحيح ليس كبيرًا ، خذ sys.maxsize الاعتبار sys.maxsize

sys.maxsize in range(sys.maxsize) سريع جداً

نظرًا للتحسين - من السهل مقارنة عدد صحيح معطى بالحد الأدنى والحد الأقصى للنطاق.

لكن:

float(sys.maxsize) in range(sys.maxsize) بطيء جداً .

(في هذه الحالة ، لا يوجد أي تحسين في range ، لذلك إذا تلقت python تعويمًا غير متوقع ، فسيقارن python جميع الأرقام)

يجب أن تكون على دراية بتفاصيل التنفيذ ولكن لا يجب الاعتماد عليها ، لأن هذا قد يتغير في المستقبل.


كائن Python 3 range() لا يُنتج أرقامًا على الفور ؛ إنه كائن تسلسل ذكي ينتج أرقام عند الطلب . كل ما يحتويه هو قيم البداية والوقوف والخطوة ، ثم كلما قمت بالتكرار على الكائن ، يتم حساب العدد الصحيح التالي لكل تكرار.

يقوم الكائن أيضًا بتنفيذ object.__contains__ ربط ، ويحسب ما إذا كان رقمك جزءًا من نطاقه. حساب هو عملية O (1) وقت ثابت. ليست هناك حاجة أبدًا للمسح من خلال جميع الأعداد الصحيحة الممكنة في النطاق.

من وثائق كائن range() :

تتمثل ميزة نوع range على list أو tuple أن كائن النطاق سيستغرق دائمًا نفس مقدار الذاكرة (صغير) ، بغض النظر عن حجم النطاق الذي يمثله (لأنه يخزن فقط قيم 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() الحقيقي range() (مثل .index() أو .count() ، أو التجزئة ، أو اختبار المساواة ، أو التقطيع) ، ولكن يجب أن يعطيك فكرة.

قمت أيضًا بتبسيط تطبيق __contains__ للتركيز فقط على اختبارات عدد صحيح. إذا قمت بإعطاء كائن range() حقيقي range() قيمة غير عدد صحيح (بما في ذلك الفئات الفرعية من int ) ، يتم بدء فحص بطيء لمعرفة ما إذا كان هناك تطابق ، تمامًا كما لو كنت تستخدم اختبار احتواء مقابل قائمة بجميع القيم المضمنة . تم ذلك لمواصلة دعم الأنواع الرقمية الأخرى التي تحدث للتو لدعم اختبار المساواة مع الأعداد الصحيحة ولكن ليس من المتوقع أن تدعم عددًا صحيحًا أيضًا. انظر قضية بيثون الأصلية التي طبقت اختبار الاحتواء.


للإضافة إلى إجابة Martijn ، هذا هو الجزء ذو الصلة من المصدر (في C ، حيث يتم كتابة كائن النطاق في الكود الأصلي):

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 (والتي هي int في Python 3) ، range_contains_long الدالة range_contains_long لتحديد النتيجة. وتتحقق هذه الوظيفة بشكل أساسي إذا كان ob في النطاق المحدد (على الرغم من أنه يبدو أكثر تعقيدًا في C).

إذا لم يكن كائن 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




python-internals