On Nov 15, 12:46 pm, Tim Chase <python.l...@tim.thechases.com> wrote: > On 11/15/2010 12:39 AM, Dmitry Groshev wrote: > > > x in range optimisation > > I've often thought this would make a nice O(1)-test lookup on an > xrange() generator.
An O(1) test for 'x in <range_object>' is implemented in Python 3.2, at least provided that x has type 'int', 'long' or 'bool'. (If x is an instance of a subclass of int or long, then there's a risk that the semantics of the membership test have been changed by an explicitly overridden __eq__, so Python wimps out and falls back to the O(n) algorithm in that case.) Python 3.2a4+ (py3k:86635:86636M, Nov 21 2010, 19:22:18) [GCC 4.2.1 (Apple Inc. build 5664)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> -1 in range(10**9) False >>> 5 in range(0, 10**100, 2) False >>> 10**99 in range(0, 10**100, 2) True IIRC, there wasn't sufficient interest to get it backported to Python 2.7 in time for its release. Though as a pure optimization, one could argue that it would still be possible to get this into Python 2.7.2. Mark -- http://mail.python.org/mailman/listinfo/python-list
