`xrange(2**100)` -> 오버플로 오류:long int가 너무 커서 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

파이썬 3.x:

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

py3k 내장 백포트가 있나요? range() Python 2.x용 함수?

편집하다

나는 "게으른"의 완전한 구현을 찾고 있습니다 range(), 일부 기능의 부분적 구현이 아닙니다.

Answer 1

좋아요, 여기에 더 많은 상환이 있습니다.

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

Answer 2

나는 백포트가 없다고 생각합니다(Py 3에서는 결국 int/long 구별이 완전히 제거되었지만 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

편집하다 OP는 루핑을 원하지 않고 (Xrange의 일반적인 목적 및 PY3의 범위) 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

여기에 오프바이원(off-by-one) 또는 이와 유사한 결함이 숨어 있어도 놀라지 않을 것입니다. 하지만 이것이 도움이 되기를 바랍니다!

편집하다 다시:인덱싱도 필요하다는 것을 알았습니다.직접 작성하기가 너무 어려운가요? __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

3.0이면 모르겠는데 range 슬라이싱 지원(xrange 최근 2.* 릴리스는 그렇지 않습니다. 예전에는 그랬지만 문제가 터무니없고 버그가 발생하기 쉽기 때문에 제거되었습니다. 하지만 모래 어딘가에 선을 그려야 할 것 같아서 추가하지 않겠습니다. -).

Answer 3

문서에서 :

메모

xrange ()는 단순하고 빠르기위한 것입니다. 구현은이를 달성하기 위해 제한을 부과 할 수 있습니다. Python의 C 구현은 모든 인수를 기본 C Long ( "Short"Python Integers)으로 제한하며, 요소의 수는 기본 C Long에 적합해야합니다. 더 넓은 범위가 필요한 경우 itertools 모듈을 사용하여 대체 버전을 제작할 수 있습니다 (count (start, step), (stop-start+step-1) // 단계).

대안 적으로 생성기를 사용하여 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 4

편집하다

1546078 발행 : "긴 장기 등을 지원하는 xrange" Python 문제 추적기에는 Neal Norwitz (NNORWITZ)가 작성한 무제한 XRANGE의 C 패치 및 Pure Python 구현이 포함되어 있습니다. 보다 xrange.py

편집하다

최신 버전 irange (이름이 바뀌었다 lrange)에 있습니다 github.

---

PY3K를 기반으로 한 구현 RangeObject.c

irange.py

"""Define `irange.irange` class

`xrange`, py3k's `range` analog for large integers

See help(irange.irange)

>>> r = irange(2**100, 2**101, 2**100)
>>> len(r)
1
>>> for i in r:
...     print i,
1267650600228229401496703205376
>>> for i in r:
...     print i,
1267650600228229401496703205376
>>> 2**100 in r
True
>>> r[0], r[-1]
(1267650600228229401496703205376L, 1267650600228229401496703205376L)
>>> L = list(r)
>>> L2 = [1, 2, 3]
>>> L2[:] = r
>>> L == L2 == [2**100]
True
"""


def toindex(arg): 
    """Convert `arg` to integer type that could be used as an index.

    """
    if not any(isinstance(arg, cls) for cls in (long, int, bool)):
        raise TypeError("'%s' object cannot be interpreted as an integer" % (
            type(arg).__name__,))
    return int(arg)


class irange(object):
    """irange([start,] stop[, step]) -> irange object

    Return an iterator that generates the numbers in the range on demand.
    Return `xrange` for small integers 

    Pure Python implementation of py3k's `range()`.

    (I.e. it supports large integers)

    If `xrange` and py3k `range()` differ then prefer `xrange`'s behaviour

    Based on `[1]`_

    .. [1] http://svn.python.org/view/python/branches/py3k/Objects/rangeobject.c?view=markup

    >>> # on Python 2.6
    >>> N = 10**80
    >>> len(range(N, N+3))
    3
    >>> len(xrange(N, N+3))
    Traceback (most recent call last):
    ...
    OverflowError: long int too large to convert to int
    >>> len(irange(N, N+3))
    3
    >>> xrange(N)
    Traceback (most recent call last):
    ...
    OverflowError: long int too large to convert to int
    >>> irange(N).length() == N
    True
    """
    def __new__(cls, *args):
        try: return xrange(*args) # use `xrange` for small integers
        except OverflowError: pass

        nargs = len(args)
        if nargs == 1:
            stop = toindex(args[0])
            start = 0
            step = 1
        elif nargs in (2, 3):
            start = toindex(args[0]) 
            stop = toindex(args[1])
            if nargs == 3:
                step = args[2]
                if step is None: 
                    step = 1

                step = toindex(step)
                if step == 0:
                    raise ValueError("irange() arg 3 must not be zero")
            else:
                step = 1
        else:
            raise ValueError("irange(): wrong number of arguments," +
                             " got %s" % args)

        r = super(irange, cls).__new__(cls)
        r._start, r._stop, r._step = start, stop, step
        return r

    def length(self):
        """len(self) might throw OverflowError, this method shouldn't."""
        if self._step > 0:
            lo, hi = self._start, self._stop
            step = self._step
        else:
            hi, lo = self._start, self._stop
            step = -self._step
            assert step

        if lo >= hi:
            return 0
        else:
            return (hi - lo - 1) // step + 1

    __len__ = length

    def __getitem__(self, i): # for L[:] = irange(..)
        if i < 0:
            i = i + self.length() 
        if i < 0 or i >= self.length():
            raise IndexError("irange object index out of range")

        return self._start + i * self._step

    def __repr__(self):
        if self._step == 1:
            return "irange(%r, %r)" % (self._start, self._stop)
        else:

            return "irange(%r, %r, %r)" % (
                self._start, self._stop, self._step)

    def __contains__(self, ob):
        if type(ob) not in (int, long, bool): # mimic py3k
            # perform iterative search
            return any(i == ob for i in self)

        # if long or bool
        if self._step > 0:
            inrange = self._start <= ob < self._stop
        else:
            assert self._step
            inrange = self._stop < ob <= self._start

        if not inrange:
            return False
        else:
            return ((ob - self._start) % self._step) == 0

    def __iter__(self):
        len_ = self.length()
        i = 0
        while i < len_:
            yield self._start + i * self._step
            i += 1

    def __reversed__(self):
        len_ = self.length()
        new_start = self._start + (len_ - 1) * self._step
        new_stop = self._start
        if self._step > 0:
            new_stop -= 1
        else:
            new_stop += 1
        return irange(new_start, new_stop, -self._step) 

test_irange.py

"""Unit-tests for irange.irange class.

Usage:

    $ python -W error test_irange.py --with-doctest --doctest-tests
"""
import sys

from nose.tools import raises

from irange import irange


def eq_irange(a, b):
    """Assert that `a` equals `b`.

    Where `a`, `b` are `irange` objects
    """
    try:
        assert a.length() == b.length()
        assert a._start == b._start
        assert a._stop == b._stop
        assert a._step == b._step
        if a.length() < 100:
            assert list(a) == list(b)
            try:
                 assert list(a) == range(a._start, a._stop, a._step)
            except OverflowError:
                pass
    except AttributeError:
        if type(a) == xrange:
            assert len(a) == len(b)
            if len(a) == 0: # empty xrange
                return
            if len(a) > 0:
                assert a[0] == b[0]
            if len(a) > 1:
                a = irange(a[0], a[-1], a[1] - a[0])
                b = irange(b[0], b[-1], b[1] - b[0])
                eq_irange(a, b)
        else:
            raise


def _get_short_iranges_args():
    # perl -E'local $,= q/ /; $n=100; for (1..20)
    # >    { say map {int(-$n + 2*$n*rand)} 0..int(3*rand) }'
    input_args = """\
    67
    -11
    51
    -36
    -15 38 19
    43 -58 79
    -91 -71
    -56
    3 51
    -23 -63
    -80 13 -30
    24
    -14 49
    10 73
    31
    38 66
    -22 20 -81
    79 5 84
    44
    40 49
    """
    return [[int(arg) for arg in line.split()]
            for line in input_args.splitlines() if line.strip()]


def _get_iranges_args():
    N = 2**100
    return [(start, stop, step)
            for start in range(-2*N, 2*N, N//2+1)
            for stop in range(-4*N, 10*N, N+1)
            for step in range(-N//2, N, N//8+1)]



def _get_short_iranges():
    return [irange(*args) for args in _get_short_iranges_args()]


def _get_iranges():
    return (_get_short_iranges() +
            [irange(*args) for args in _get_iranges_args()])


@raises(TypeError)
def test_kwarg():
    irange(stop=10)


@raises(TypeError, DeprecationWarning)
def test_float_stop():
    irange(1.0)


@raises(TypeError, DeprecationWarning)
def test_float_step2():
    irange(-1, 2, 1.0)


@raises(TypeError, DeprecationWarning)
def test_float_start():
    irange(1.0, 2)


@raises(TypeError, DeprecationWarning)
def test_float_step():
    irange(1, 2, 1.0)


@raises(TypeError)
def test_empty_args():
    irange()


def test_empty_range():
    for args in (
        "-3",
        "1 3 -1",
        "1 1",
        "1 1 1",
        "-3 -4",
        "-3 -2 -1",
        "-3 -3 -1",
        "-3 -3",
        ):
        r = irange(*[int(a) for a in args.split()])
        assert len(r) == 0
        L = list(r)
        assert len(L) == 0


def test_small_ints():
    for args in _get_short_iranges_args():
        ir, r = irange(*args), xrange(*args)
        assert len(ir) == len(r)
        assert list(ir) == list(r)


def test_big_ints():
    N = 10**100
    for args, len_ in [
        [(N,), N],
        [(N, N+10), 10],
        [(N, N-10, -2), 5],
        ]:
        try:
            xrange(*args)
            assert 0
        except OverflowError:
            pass

        ir = irange(*args)
        assert ir.length() == len_
        try:
            assert ir.length() == len(ir)
        except OverflowError:
            pass
        #
        ir[ir.length()-1]
        #
        if len(args) >= 2:
            r = range(*args)
            assert list(ir) == r
            assert ir[ir.length()-1] == r[-1]
            assert list(reversed(ir)) == list(reversed(r))
        #


def test_negative_index():
    assert irange(10)[-1] == 9
    assert irange(2**100+1)[-1] == 2**100


def test_reversed():
    for r in _get_iranges():
        if type(r) == xrange: continue # known not to work for xrange
        if r.length() > 1000: continue # skip long
        assert list(reversed(reversed(r))) == list(r)
        assert list(r) == range(r._start, r._stop, r._step)


def test_pickle():
    import pickle
    for r in _get_iranges():
        rp = pickle.loads(pickle.dumps(r))
        eq_irange(rp, r)


def test_equility():
    for args in _get_iranges_args():
        a, b = irange(*args), irange(*args)
        assert a is not b
        assert a != b 
        eq_irange(a, b)


def test_contains():
    class IntSubclass(int):
        pass

    r10 = irange(10)
    for i in range(10):
        assert i in r10
        assert IntSubclass(i) in r10

    assert 10 not in r10
    assert -1 not in r10
    assert IntSubclass(10) not in r10
    assert IntSubclass(-1) not in r10


def test_repr():
    for r in _get_iranges():
        eq_irange(eval(repr(r)), r)


def test_new():
    assert repr(irange(True)) == repr(irange(1))


def test_overflow():
    lo, hi = sys.maxint-2, sys.maxint+3
    assert list(irange(lo, hi)) == list(range(lo, hi))


def test_getitem():
    r = irange(sys.maxint-2, sys.maxint+3)
    L = []
    L[:] = r
    assert len(L) == len(r)
    assert L == list(r)


if __name__ == "__main__":
    import nose 
    nose.main() 

Answer 5

백 포트가 있더라도 수정해야 할 것입니다. 여기서 근본적인 문제는 Python 2.x에서입니다 int 그리고 long 그래도 별도의 데이터 유형입니다 intS는 자동으로 업 캐스트됩니다 long필요에 따라 s. 그러나 이것이 작성된 방식에 따라 C로 작성된 기능에서 반드시 발생하는 것은 아닙니다.