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

Guido van Rossum guido at python.org
Sun Jul 29 00:04:02 CEST 2007

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

More information about the Python-3000 mailing list