[Python-3000] optimizing [x]range

[tomer filiba]

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