[Python-3000] optimizing [x]range (original) (raw)

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

More information about the Python-3000 mailing list