[Python-3000] optimizing [x]range

[Guido van Rossum]

Do we really need another way to spell a <= x < b? Have you got a
real-world use case in mind for the version with step > 1?

I'm at most lukewarm; I'd be willing to look at a patch to the C code
in the py3k-struni branch, plus unit tests though.

--Guido

On 7/28/07, tomer filiba <tomerfiliba at gmail.com> wrote:
> 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
>
> _______________________________________________
> Python-3000 mailing list
> Python-3000 at python.org
> http://mail.python.org/mailman/listinfo/python-3000
> Unsubscribe:
> http://mail.python.org/mailman/options/python-3000/guido%40python.org
>
>


-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)