`xrange(2**100)` -> OverflowError: 整数过大无法转换为int

Question

xrange 函数在处理大整数时无法正常工作：

>>> N = 10**100
>>> xrange(N)
Traceback (most recent call last):
...
OverflowError: long int too large to convert to int
>>> xrange(N, N+10)
Traceback (most recent call last):
...
OverflowError: long int too large to convert to int

Python 3.x:

>>> N = 10**100
>>> r = range(N)
>>> r = range(N, N+10)
>>> len(r)
10

有没有可以在 Python 2.x 中使用的 py3k 内置 range() 函数的版本？

编辑

我希望找到一个完整的“懒惰” range() 实现，而不仅仅是它某些功能的部分实现。

Answer 1

来自文档的说明：

注意

xrange() 这个函数的设计目标是简单和快速。为了实现这个目标，可能会对它的使用做一些限制。Python 的 C 语言实现对所有参数都限制为本地的 C 长整型（也就是“短” Python 整数），并且还要求元素的数量必须能放进一个本地的 C 长整型。如果需要更大的范围，可以使用 itertools 模块中的另一个版本来实现：islice(count(start, step), (stop-start+step-1)//step)。

另外，你也可以用生成器重新实现 xrange：

def myxrange(a1, a2=None, step=1):
    if a2 is None:
        start, last = 0, a1
    else:
        start, last = a1, a2
    while cmp(start, last) == cmp(0, step):
        yield start
        start += step

以及

N = 10**100
len(list(myxrange(N, N+10)))

Answer 2

我觉得没有办法把这个功能移植到旧版本上（毕竟Python 3完全去掉了整数和长整数的区别，而在2.*版本中这个区分还会继续存在；-)）。不过，自己动手实现这个功能并不难，比如说……：

import operator

def wowrange(start, stop, step=1):
  if step == 0:
    raise ValueError('step must be != 0')
  elif step < 0:
    proceed = operator.gt
  else:
    proceed = operator.lt
  while proceed(start, stop):
    yield start
    start += step

补充：看起来提问者不仅想要循环（这就是xrange和Python 3中range的正常用途），还想要用到len和in操作符（后者在上面的生成器上是可以用的，但速度比较慢——可以进行一些优化）。为了实现这些功能，使用一个类会更好……：

import operator

class wowrange(object):
  def __init__(self, start, stop=None, step=1):
    if step == 0: raise ValueError('step must be != 0')
    if stop is None: start, stop = 0, start
    if step < 0:
      self.proceed = operator.gt
      self.l = (stop-start+step+1)//step
    else:
      self.proceed = operator.lt
      self.l = (stop-start+step-1)//step
    self.lo = min(start, stop)
    self.start, self.stop, self.step = start, stop, step
  def __iter__(self):
    start = self.start
    while self.proceed(start, self.stop):
      yield start
      start += self.step
  def __len__(self):
    return self.l
  def __contains__(self, x):
    if x == self.stop:
      return False
    if self.proceed(x, self.start):
      return False
    if self.proceed(self.stop, x):
      return False
    return (x-self.lo) % self.step == 0

我不会感到惊讶，如果这里面有个越界或类似的小错误，但我希望这些能帮到你！

再次补充：我看到还需要索引功能。自己写一个__getitem__是不是太难了？我想确实有点难，所以这里也给你准备好了……：

 def __getitem__(self, i):
   if i < 0:
     i += self.l
     if i < 0: raise IndexError
   elif if i >= self.l:
     raise IndexError
   return self.start + i * self.step

我不知道Python 3.0的range是否支持切片（最近的2.*版本中的是不支持的——以前是支持的，但因为太复杂且容易出错所以去掉了），不过我想我得在某个地方划个界限，所以我不会添加这个功能；-）。

Answer 3

好的，下面是一个更完整的重新实现。

class MyXRange(object):
    def __init__(self, a1, a2=None, step=1):
        if step == 0:
            raise ValueError("arg 3 must not be 0")
        if a2 is None:
            a1, a2 = 0, a1
        if (a2 - a1) % step != 0:
            a2 += step - (a2 - a1) % step
        if cmp(a1, a2) != cmp(0, step):
            a2 = a1
        self.start, self.stop, self.step = a1, a2, step

    def __iter__(self):
        n = self.start
        while cmp(n, self.stop) == cmp(0, self.step):
            yield n
            n += self.step

    def __repr__(self):
        return "MyXRange(%d,%d,%d)" % (self.start, self.stop, self.step)

    # NB: len(self) will convert this to an int, and may fail
    def __len__(self):
        return (self.stop - self.start)//(self.step)

    def __getitem__(self, key):
        if key < 0:
            key = self.__len__() + key
            if key < 0:
                raise IndexError("list index out of range")
            return self[key]
        n = self.start + self.step*key
        if cmp(n, self.stop) != cmp(0, self.step):
            raise IndexError("list index out of range")
        return n

    def __reversed__(self):
        return MyXRange(self.stop-self.step, self.start-self.step, -self.step)

    def __contains__(self, val):
        if val == self.start: return cmp(0, self.step) == cmp(self.start, self.stop)
        if cmp(self.start, val) != cmp(0, self.step): return False
        if cmp(val, self.stop) != cmp(0, self.step): return False
        return (val - self.start) % self.step == 0

还有一些测试：

def testMyXRange(testsize=10):
    def normexcept(f,args):
        try:
            r = [f(args)]
        except Exception, e:
            r = type(e)
        return r

    for i in range(-testsize,testsize+1):
        for j in range(-testsize,testsize+1):
            print i, j
            for k in range(-9, 10, 2):
                r, mr = range(i,j,k), MyXRange(i,j,k)

                if r != list(mr):
                    print "iter fail: %d, %d, %d" % (i,j,k)

                if list(reversed(r)) != list(reversed(mr)):
                    print "reversed fail: %d, %d, %d" % (i,j,k)

                if len(r) != len(mr):
                    print "len fail: %d, %d, %d" % (i,j,k)

                z = [m for m in range(-testsize*2,testsize*2+1)
                      if (m in r) != (m in mr)]
                if z != []:
                    print "contains fail: %d, %d, %d, %s" % (i,j,k,(z+["..."])[:10])

                z = [m for m in range(-testsize*2, testsize*2+1) 
                      if normexcept(r.__getitem__, m) != normexcept(mr.__getitem__, m)]
                if z != []:
                    print "getitem fail: %d, %d, %d, %s" % (i,j,k,(z+["..."])[:10])