Tại sao “1000000000000000 trong phạm vi (1000000000000001)” trong Python 3 quá nhanh?

Tôi hiểu rằng range()hàm, thực sự là một kiểu đối tượng trong Python 3 , tạo nội dung của nó một cách nhanh chóng, tương tự như một trình tạo.

Trong trường hợp này, tôi dự kiến ​​dòng sau sẽ mất một khoảng thời gian không đáng kể, bởi vì để xác định xem 1 phần tư tỷ có nằm trong phạm vi hay không, một phần tư tỷ giá trị sẽ phải được tạo:

1000000000000000 in range(1000000000000001)

Hơn nữa: có vẻ như bất kể tôi thêm vào bao nhiêu số 0, việc tính toán ít hay nhiều đều mất cùng một khoảng thời gian (về cơ bản là tức thời).

Tôi cũng đã thử những thứ như thế này, nhưng tính toán vẫn gần như tức thì:

1000000000000000000000 in range(0,1000000000000000000001,10) # count by tens

Nếu tôi cố gắng triển khai hàm phạm vi của riêng mình, kết quả không được tốt cho lắm !!

def my_crappy_range(N):
    i = 0
    while i < N:
        yield i
        i += 1
    return

Là gì range()đối tượng làm dưới mui xe mà làm cho nó nhanh như vậy?

Câu trả lời của Martijn Pieters đã được chọn vì tính hoàn chỉnh của nó, nhưng cũng hãy xem câu trả lời đầu tiên của abarnert để thảo luận tốt về ý nghĩa của rangeviệc trở thành một chuỗi chính thức trong Python 3 và một số thông tin / cảnh báo về sự không nhất quán tiềm ẩn để __contains__tối ưu hóa hàm trên các triển khai Python . Câu trả lời khác của abarnert đi vào một số chi tiết hơn và cung cấp liên kết cho những người quan tâm đến lịch sử đằng sau việc tối ưu hóa trong Python 3 (và thiếu tối ưu hóa xrangetrong Python 2). Các câu trả lời bằng cách poke và bằng wim cung cấp mã nguồn C liên quan và giải thích cho những ai quan tâm.

range()Đối tượng Python 3 không tạo ra số ngay lập tức; nó là một đối tượng chuỗi thông minh tạo ra các số theo yêu cầu . Tất cả những gì nó chứa là giá trị bắt đầu, dừng và bước của bạn, sau đó khi bạn lặp lại đối tượng, số nguyên tiếp theo được tính mỗi lần lặp.

Đối tượng cũng thực hiện object.__contains__hook và tính toán xem số của bạn có nằm trong phạm vi của nó hay không. Tính toán là một hoạt động thời gian không đổi (gần) ^* . Không bao giờ cần phải quét qua tất cả các số nguyên có thể có trong phạm vi.

Từ range()tài liệu đối tượng :

Ưu điểm của các rangeloại trên thường xuyên listhoặc tuplelà một đối tượng phạm vi sẽ luôn đi cùng (nhỏ) dung lượng bộ nhớ, không có vấn đề kích thước của dãy nó đại diện (vì nó chỉ lưu trữ start, stopvà stepcác giá trị, tính toán từng mục và subranges khi cần thiết).

Vì vậy, ở mức tối thiểu, range()đối tượng của bạn sẽ làm:

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, step = stop, start, -step
        else:
            lo, hi = start, stop
        self.length = 0 if lo > hi else ((hi - lo - 1) // 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

Điều này vẫn còn thiếu một số thứ mà một thực range()hỗ trợ (chẳng hạn như .index()hoặc .count()các phương pháp, băm, kiểm tra bình đẳng hoặc cắt), nhưng sẽ cung cấp cho bạn một ý tưởng.

Tôi cũng đã đơn giản hóa việc __contains__triển khai để chỉ tập trung vào các bài kiểm tra số nguyên; nếu bạn cung cấp cho một range()đối tượng thực một giá trị không phải là số nguyên (bao gồm các lớp con của int), quá trình quét chậm được bắt đầu để xem liệu có khớp hay không, giống như khi bạn sử dụng kiểm tra ngăn chặn đối với danh sách tất cả các giá trị được chứa. Điều này được thực hiện để tiếp tục hỗ trợ các kiểu số khác chỉ xảy ra để hỗ trợ kiểm tra bình đẳng với số nguyên nhưng không được mong đợi cũng hỗ trợ số học nguyên. Xem sự cố Python ban đầu đã triển khai kiểm tra ngăn chặn.

* Gần thời gian không đổi vì số nguyên Python là không bị giới hạn và do đó các phép toán cũng phát triển theo thời gian khi N lớn lên, làm cho đây là một phép toán O (log N). Vì tất cả được thực thi trong mã C được tối ưu hóa và Python lưu trữ các giá trị số nguyên trong các khối 30 bit, bạn sẽ hết bộ nhớ trước khi thấy bất kỳ tác động hiệu suất nào do kích thước của các số nguyên liên quan ở đây.

Sự hiểu lầm cơ bản ở đây là trong suy nghĩ rằng đó rangelà một máy phát điện. Nó không thể. Trên thực tế, nó không phải là bất kỳ loại trình lặp nào.

Bạn có thể nói điều này khá dễ dàng:

>>> a = range(5)
>>> print(list(a))
[0, 1, 2, 3, 4]
>>> print(list(a))
[0, 1, 2, 3, 4]

Nếu nó là một máy phát điện, việc lặp lại nó một lần sẽ khiến nó kiệt sức:

>>> b = my_crappy_range(5)
>>> print(list(b))
[0, 1, 2, 3, 4]
>>> print(list(b))
[]

Có gì rangethực sự là, là một chuỗi, giống như một danh sách. Bạn thậm chí có thể kiểm tra điều này:

>>> import collections.abc
>>> isinstance(a, collections.abc.Sequence)
True

Điều này có nghĩa là nó phải tuân theo tất cả các quy tắc để trở thành một chuỗi:

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

Sự khác biệt giữa a rangevà a listlà a rangelà một chuỗi lười biếng hoặc động ; nó không nhớ tất cả các giá trị của nó, nó chỉ nhớ nó start, stopvà step, và tạo ra các giá trị theo yêu cầu trên __getitem__.

(Lưu ý thêm, nếu bạn print(iter(a)), bạn sẽ nhận thấy rằng rangesử dụng cùng listiteratorloại với list. Nó hoạt động như thế nào? A listiteratorkhông sử dụng bất kỳ điều gì đặc biệt listngoại trừ thực tế là nó cung cấp triển khai C __getitem__, vì vậy nó hoạt động tốt cho rangequá.)

Bây giờ, không có gì nói rằng Sequence.__contains__phải là thời gian không đổi - trên thực tế, đối với các ví dụ rõ ràng về các chuỗi như list, thì không. Nhưng không có gì nói rằng nó không thể được. Và việc range.__contains__chỉ kiểm tra bằng toán học sẽ dễ thực hiện hơn ( (val - start) % stepnhưng với một số phức tạp hơn để xử lý các bước tiêu cực) hơn là thực sự tạo và kiểm tra tất cả các giá trị, vậy tại sao không nên làm theo cách tốt hơn?

Nhưng dường như không có bất cứ thứ gì trong ngôn ngữ đảm bảo điều này sẽ xảy ra. Như Ashwini Chaudhari đã chỉ ra, nếu bạn cung cấp cho nó một giá trị không tích phân, thay vì chuyển đổi thành số nguyên và thực hiện bài kiểm tra toán học, nó sẽ quay lại lặp lại tất cả các giá trị và so sánh từng giá trị một. Và chỉ vì các phiên bản CPython 3.2+ và PyPy 3.x có chứa tối ưu hóa này, và đó là một ý tưởng hay và dễ thực hiện, không có lý do gì mà IronPython hoặc NewKickAssPython 3.x lại không thể loại bỏ nó. (Và trên thực tế, CPython 3.0-3.1 không bao gồm nó.)

Nếu rangethực sự là một máy phát điện, chẳng hạn my_crappy_range, thì sẽ không hợp lý khi kiểm tra __contains__theo cách này, hoặc ít nhất cách nó có ý nghĩa sẽ không rõ ràng. Nếu bạn đã lặp lại 3 giá trị đầu tiên, 1vẫn là intrình tạo? Thử nghiệm có nên làm cho 1nó lặp lại và sử dụng tất cả các giá trị lên đến 1(hoặc lên đến giá trị đầu tiên >= 1) không?

Sử dụng nguồn , Luke!

Trong CPython, range(...).__contains__(một trình bao bọc phương thức) cuối cùng sẽ ủy quyền cho một phép tính đơn giản để kiểm tra xem giá trị có thể nằm trong phạm vi hay không. Lý do cho tốc độ ở đây là chúng tôi đang sử dụng lý luận toán học về các giới hạn, thay vì lặp lại trực tiếp đối tượng phạm vi . Để giải thích logic được sử dụng:

1. Kiểm tra để đảm bảo rằng con số nằm giữa startvà stopvà
2. Kiểm tra xem giá trị sải chân không "vượt qua" số của chúng tôi.

Ví dụ, 994là range(4, 1000, 2)bởi vì:

1. 4 <= 994 < 1000và
2. (994 - 4) % 2 == 0.

Mã C đầy đủ được bao gồm bên dưới, dài dòng hơn một chút vì quản lý bộ nhớ và chi tiết đếm tham chiếu, nhưng ý tưởng cơ bản là ở đó:

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);
}

"Thịt" của ý tưởng được đề cập trong dòng :

/* result = ((int(ob) - start) % step) == 0 */ 

Lưu ý cuối cùng - hãy xem range_containshàm ở cuối đoạn mã. Nếu việc kiểm tra loại chính xác không thành công thì chúng tôi không sử dụng thuật toán thông minh được mô tả, thay vào đó quay trở lại tìm kiếm lặp lại ngu ngốc của phạm vi bằng cách sử dụng _PySequence_IterSearch! Bạn có thể kiểm tra hành vi này trong trình thông dịch (tôi đang sử dụng v3.5.0 tại đây):

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

Để thêm vào câu trả lời của Martijn, đây là phần có liên quan của nguồn (trong C, vì đối tượng phạm vi được viết bằng mã gố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);
}

Vì vậy, đối với PyLongcác đối tượng ( inttrong Python 3), nó sẽ sử dụng range_contains_longhàm để xác định kết quả. Và về cơ bản, hàm đó sẽ kiểm tra xem obcó nằm trong phạm vi được chỉ định hay không (mặc dù nó trông phức tạp hơn một chút trong C).

Nếu nó không phải là một intđối tượng, nó sẽ quay trở lại lặp cho đến khi nó tìm thấy giá trị (hoặc không).

Toàn bộ logic có thể được dịch sang Python giả như thế này:

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

Nếu bạn đang thắc mắc tại sao tối ưu hóa này được thêm vào range.__contains__và tại sao nó không được thêm vào xrange.__contains__trong 2.7:

Đầu tiên, như Ashwini Chaudhary đã phát hiện ra, vấn đề 1766304 đã được mở một cách rõ ràng để tối ưu hóa [x]range.__contains__. Một bản vá cho điều này đã được chấp nhận và đăng ký cho 3.2 , nhưng không được báo cáo trở lại 2.7 bởi vì "xrange đã hoạt động như vậy trong một thời gian dài đến nỗi tôi không thấy nó mua gì để chúng tôi thực hiện bản vá muộn này." (2,7 đã gần hết vào thời điểm đó.)

Trong khi đó:

Ban đầu, xrangelà một đối tượng không hoàn toàn theo trình tự. Như tài liệu 3.1 nói:

Các đối tượng phạm vi có rất ít hành vi: chúng chỉ hỗ trợ lập chỉ mục, lặp lại và lenhàm.

Điều này không hoàn toàn đúng; một xrangeđối tượng thực sự được hỗ trợ một vài điều khác đi kèm với tự động lập chỉ mục và len, ^* bao gồm __contains__(thông qua tìm kiếm tuyến tính). Nhưng không ai nghĩ rằng việc tạo ra chúng đầy đủ các chuỗi là điều đáng giá vào thời điểm đó.

Sau đó, là một phần của việc triển khai PEP các lớp cơ sở trừu tượng , điều quan trọng là phải tìm ra loại nội trang nào nên được đánh dấu là triển khai ABC và xrange/ được rangeyêu cầu triển khai collections.Sequence, mặc dù nó vẫn chỉ xử lý cùng một "hành vi rất ít". Không ai nhận thấy vấn đề đó cho đến khi phát hành 9213 . Bản vá cho vấn đề đó không chỉ được thêm vào indexvà countcho 3.2 range, nó còn làm việc lại được tối ưu hóa __contains__(chia sẻ cùng một phép toán indexvà được sử dụng trực tiếp bởi count). ^** Thay đổi này cũng áp dụng cho 3.2 và không được báo cáo lại cho 2.x, vì "đó là một bản sửa lỗi bổ sung các phương pháp mới". (Tại thời điểm này, 2.7 đã quá trạng thái rc.)

Vì vậy, có hai cơ hội để tối ưu hóa này được báo cáo lại thành 2,7, nhưng cả hai đều bị từ chối.

_{* Trên thực tế, bạn thậm chí có thể lặp lại miễn phí chỉ với việc lập chỉ mục, nhưng trong 2,3 xrange đối tượng có một trình lặp tùy chỉnh.}

_{** Phiên bản đầu tiên thực sự đã hoàn thiện lại nó, và có sai chi tiết — ví dụ: nó sẽ cung cấp cho bạn MyIntSubclass(2) in range(5) == False. Nhưng phiên bản cập nhật của bản vá lỗi của Daniel Stutzbach đã khôi phục hầu hết mã trước đó, bao gồm dự phòng cho mã chung, làm chậm _PySequence_IterSearchmà trước 3.2 range.__contains__đã ngầm sử dụng khi tối ưu hóa không áp dụng.}

Các câu trả lời khác đã giải thích rõ điều đó rồi, nhưng tôi muốn đưa ra một thử nghiệm khác minh họa bản chất của các đối tượng phạm vi:

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

Như bạn có thể thấy, đối tượng phạm vi là đối tượng ghi nhớ phạm vi của nó và có thể được sử dụng nhiều lần (ngay cả khi lặp lại nó), không chỉ là trình tạo một lần.

Đó là tất cả về một cách tiếp cận lười biếng để đánh giá và một số phụ tối ưu hóa của range. Giá trị trong phạm vi không cần phải được tính cho đến khi sử dụng thực sự hoặc thậm chí xa hơn do tối ưu hóa thêm.

Nhân tiện, số nguyên của bạn không lớn như vậy, hãy xem xét sys.maxsize

sys.maxsize in range(sys.maxsize) khá nhanh

do tối ưu hóa - thật dễ dàng để so sánh số nguyên đã cho chỉ với tối thiểu và tối đa của phạm vi.

nhưng:

Decimal(sys.maxsize) in range(sys.maxsize) là khá chậm .

(trong trường hợp này, không có tối ưu hóa trong range, vì vậy nếu python nhận được Số thập phân không mong muốn, python sẽ so sánh tất cả các số)

Bạn nên biết về một chi tiết triển khai nhưng không nên dựa vào vì điều này có thể thay đổi trong tương lai.

TL; DR

Đối tượng được trả về range()thực sự là một rangeđối tượng. Đối tượng này triển khai giao diện trình lặp để bạn có thể lặp lại các giá trị của nó một cách tuần tự, giống như một trình tạo, danh sách hoặc tuple.

Nhưng nó cũng thực hiện __contains__giao diện thực sự là thứ được gọi khi một đối tượng xuất hiện ở phía bên tay phải của intoán tử. Các __contains__()trở về phương pháp một boolhay không các mục trên trái tay bên inlà trong đối tượng. Vì rangecác đối tượng biết giới hạn và sải chân của chúng, điều này rất dễ thực hiện trong O (1).

1. Do tối ưu hóa, rất dễ dàng so sánh các số nguyên đã cho chỉ với phạm vi tối thiểu và tối đa.
2. Lý do mà hàm range () nhanh như vậy trong Python3 là ở đây chúng tôi sử dụng lý luận toán học cho các giới hạn, thay vì lặp lại trực tiếp đối tượng phạm vi.
3. Vì vậy, để giải thích logic ở đây:
   • Kiểm tra xem số có nằm giữa điểm bắt đầu và điểm dừng không.
   • Kiểm tra xem giá trị chính xác của bước có vượt quá số của chúng tôi hay không.

4. Lấy ví dụ, 997 nằm trong phạm vi (4, 1000, 3) vì:

   4 <= 997 < 1000, and (997 - 4) % 3 == 0.

Hãy thử x-1 in (i for i in range(x))các xgiá trị lớn , sử dụng khả năng hiểu của trình tạo để tránh gọi ra range.__contains__tối ưu hóa.

TLDR; range là một chuỗi số học vì vậy nó có thể rất dễ dàng tính toán xem đối tượng có ở đó hay không, thậm chí có thể lấy chỉ số của nó nếu nó được liệt kê một cách thực sự nhanh chóng.