xrange是 - xrange python2




為什麼在Python 3中“範圍(1000000000000000(1000000000000001))”這麼快? (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__ 函數優化潛在不一致的信息/警告。 Python實現。 abarnert的其他答案 更加詳細,並為那些對Python 3優化背後的歷史(以及Python 2中缺乏 xrange 優化)感興趣的人提供了鏈接。 poke 和 wim的 答案 為 感興趣的人 提供了相關的C源代碼和說明。


TL; DR

range() 返回的對象實際上是一個 range 對象。 該對象實現了迭代器接口,因此您可以像生成器一樣順序地迭代其值,但是它還實現了 __contains__ 接口,當對像出現在 in 運算符的右側時,實際上是調用該接口。 __contains__() 方法返回該項目是否在對像中的布爾值。 由於 range 對象知道其邊界和步幅,因此在O(1)中非常容易實現。


Python 3 range() 像不會立即產生數字。 它是一個智能序列對象,可 按需 生成數字。 它所包含的只是您的開始,結束和步長值,然後在對對象進行迭代時,每次迭代都會計算出下一個整數。

該對像還實現 object.__contains__ 鉤子 ,併 計算 您的數字是否屬於其範圍。 計算是O(1)恆定時間操作。 永遠不需要掃描範圍內的所有可能整數。

range() 對象文檔中

與常規 listtuple 相比, range 類型的優勢在於,範圍對象將始終佔用相同(少量)的內存,無論其表示的範圍大小如何(因為它僅存儲 startstopstep 值) ,根據需要計算單個項目和子範圍)。

因此,至少,您的 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() 方法,哈希,相等性測試或切片),但應該給您一個提示。

我還簡化了 __contains__ 實現,只專注於整數測試。 如果為實的 range() 對象提供非整數值(包括 int 子類),則會啟動慢速掃描以查看是否存在匹配項,就像您對包含的所有值的列表使用了包含測試。 這樣做是為了繼續支持其他數字類型,這些數字類型恰好支持整數的相等性測試,但預計也不支持整數算術。 請參閱實現收容測試的原始 Python問題


其他答案已經很好地說明了這一點,但是我想提供另一個實驗來說明範圍對象的性質:

>>> 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__ ,為什麼 將其添加到2.7中的 xrange.__contains__

首先,正如Ashwini Chaudhary所發現的那樣,明確打開了 1766304版 以優化 [x]range.__contains__ 接受 了此修補程序 並簽入了3.2版本 ,但沒有回遷到2.7版本,因為“ xrange表現得如此之久,以至於我看不到它為什麼讓我們提交最新的修補程序。” (當時2.7快要淘汰了。)

與此同時:

最初, xrange 是一個非相當序列的對象。 正如 3.1文檔 所說:

範圍對象的行為很少:它們僅支持索引,迭代和 len 函數。

這不是真的。 一個 xrange 對象實際上支持索引和 len 自動附帶的其他一些功能, * 包括 __contains__ (通過線性搜索)。 但是,沒有人認為有必要在那時將它們完整地序列化。

然後,作為實現“ 抽象基類” PEP的一部分,重要的是弄清楚應將哪些內置類型標記為實現哪些ABC,並且 xrange / range 聲稱實現了 collections.Sequence ,即使它仍然只處理相同的“非常小行為”。 在 發布9213 之前,沒有人注意到這個問題。 針對該問題的補丁不僅將 indexcount 添加到3.2的 range ,而且還對經過優化的 __contains__ (與 index 具有相同的數學運算,並直接由 count )進行了重新設計。 ** 此更改 也適用於3.2,並且沒有回遷到2.x,因為“這是一個添加了新方法的錯誤修正”。 (此時,2.7已經超過了rc狀態。)

因此,有兩次機會可以將此優化回溯到2.7,但都被拒絕了。

*實際上,您甚至可以單獨使用索引免費獲得迭代,但是 在2.3 xrange 對像中獲得了自定義迭代器。

**第一個版本實際上重新實現了它,並弄錯了詳細信息,例如,它將為您 MyIntSubclass(2) in range(5) == False 但丹尼爾·斯圖茨巴赫(Daniel Stutzbach)的補丁更新版本恢復了以前的大多數代碼,包括對3.2之前的 range.__contains__ 的通用 _PySequence_IterSearch 的回退。


為了增加Martijn的答案,這是 源代碼 的相關部分(在C中,因為range對像是用本機代碼編寫的):

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 函數確定結果。 該函數實質上檢查 ob 是否在指定範圍內(儘管在C語言中看起來更複雜)。

如果它不是一個 int 對象,它將退回到迭代,直到找到(或沒有)值為止。

整個邏輯可以像這樣轉換為偽Python:

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 一些 額外優化 。 直到實際使用時才需要計算範圍內的值,或者由於額外的優化甚至不需要進一步計算。

順便說一句,您的整數不是那麼大,請考慮 sys.maxsize

sys.maxsize in range(sys.maxsize) 相當快

由於優化-比較給定的整數和範圍的最小值和最大值很容易。

但:

float(sys.maxsize) in range(sys.maxsize) 相當慢

(在這種情況下, range 沒有優化,因此,如果python收到意外的float值,則python將比較所有數字)

您應該了解實現細節,但不應依賴它,因為將來可能會改變。





python-internals