# [Python-3000] optimizing [x]range

tomer filiba tomerfiliba at gmail.com
Sat Jul 28 17:06:50 CEST 2007

```currently, testing for "x in xrange(y)" is an O(n) operation.

since xrange objects (which would become range in py3k) are not real lists,
there's no reason that __contains__ be an O(n). it can easily be made into
an O(1) operation. here's a demo code (it should be trivial to implement
this in CPython)

class xxrange(object):
def __init__(self, *args):
if len(args) == 1:
self.start, self.stop, self.step = (0, args[0], 1)
elif len(args) == 2:
self.start, self.stop, self.step = (args[0], args[1], 1)
elif len(args) == 3:
self.start, self.stop, self.step = args
else:
raise TypeError("invalid number of args")

def __iter__(self):
i = self.start
while i < self.stop:
yield i
i += self.step

def __contains__(self, num):
if num < self.start or num > self.stop:
return False
return (num - self.start) % self.step == 0

print list(xxrange(7))            # [0, 1, 2, 3, 4, 5, 6]
print list(xxrange(0, 7, 2))      # [0, 2, 4, 6]
print list(xxrange(1, 7, 2))      # [1, 3, 5]
print 98 in xxrange(100)          # True
print 98 in xxrange(0, 100, 2)    # True
print 99 in xxrange(0, 100, 2)    # False
print 98 in xxrange(1, 100, 2)    # False
print 99 in xxrange(1, 100, 2)    # True

-tomer
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/python-3000/attachments/20070728/3d78c559/attachment.htm
```