O(1) containment testing with Py3 range objects (was Re: Make len() usable on a generator)
On 4 October 2014 22:39, Andrew Barnert <abarnert@yahoo.com> wrote:
I've seen a few transition guides that oversimplify the situation as "Python 3 range is the same as Python 2 xrange". Those transition guides are wrong (xrange has many limitations compared to the more full featured Python 3 range implementation), but we don't have the capacity to chase down every occurrence and ask people to fix it. One nice trick with Py3 range for example, is to work with ranges that Py2 could never hope to handle: $ python3 -m timeit -s "seq = range(-(10**24), 10**24)" "0 in seq" 1000000 loops, best of 3: 0.295 usec per loop $ python -m timeit -s "seq = range(-(10**24), 10**24)" "0 in seq" Traceback (most recent call last): File "/usr/lib64/python2.7/timeit.py", line 300, in main x = t.timeit(number) File "/usr/lib64/python2.7/timeit.py", line 195, in timeit timing = self.inner(it, self.timer) File "<timeit-src>", line 3, in inner seq = range(-(10**24), 10**24) OverflowError: range() result has too many items There's still an unfortunate technical limitation in Py3 where *len* is restricted to 64 bit integers, but start/stop/step are exposed on range objects these days, so you can do the calculation directly if you really need to. (That workaround severely reduces the motivation for anyone to put together a backwards compatible proposal for an alternative C level length API that uses a Python object rather than a C sssize_t value)
For example, at least half a dozen times, I've written an answer on StackOverflow showing someone that `n in range(start, stop)` is what they were trying to write, and explaining that it means the same thing as `start <= n < stop` (with various caveats about Python 2, and `step`, etc.) only for someone to edit or comment on my answer claiming that range.__contents__ has to be linear and should never be used. I explain that it's a sequence, and can be indexed, and show them a quick timing test, and they still insist that's just an accidental optimization that shouldn't be relied on, because it's really just meant to be Python 2's xrange. Once someone insisted that if you want this functionality you should use a multi-interval class off PyPI, even though the docs for that class explicitly say that a single interval is just an empty subclass of range in Py 3. People who stick with 2.x just really want to believe you got this wrong, I guess.
Containment tests on range() are guaranteed to be O(1) when suing CPython to test against true int and bool objects. Other implementations may not offer the same guarantee (although it's a simple enough optimisation that I believe they should). CPython itself will currently fall back to O(n) behaviour for int subclasses and other objects to handle backwards compatibility issues in relation to custom __eq__ methods (see http://bugs.python.org/issue1766304 for history and details - note that this *was* under consideration for 2.7 xrange as well, and merely didn't make the release deadline). For those that haven't seen the kind of timing examples Andrew mentioned, one easy way to see the difference is by comparing integer lookup performance with a numeric type that isn't an integer at all: $ python3 -m timeit -s "seq = range(10**6)" "10e5 in seq" 10 loops, best of 3: 118 msec per loop $ python3 -m timeit -s "seq = range(10**6)" "int(10e5) in seq" 1000000 loops, best of 3: 0.348 usec per loop You cop a small constant-time hit for the float->int conversion, but gain back 6 orders of magnitude (in this particular example) through the switch to an O(1) containment check. This optimisation is particularly useful in cases that can't easily be converted to comparison operations, such as when the range has a step magnitude other than 1. I thought I had an open issue proposing to expand the O(1) optimisation to any type that implements index (as well as making it a documented guarantee all implementations are expected to provide), but it looks like I may have only thought about filing that rather than actually doing it. (Or perhaps it's hiding in the python-ideas archives somewhere)
I've seen similar things with, e.g., people not believing that dict.keys() returns a set that's a view into the dict's storage rather than some kind of magical iterator that knows how to be used multiple times. (I'm not even sure how that would work; how could __iter__ know when you were trying to get self and when you were trying to start over?)
That at least has an authoritative reference in PEP 3106 (along with the standard library docs). Unfortunately, the more convinced someone is that they already understand a change, the less likely they are to read the references to the relevant design discussions and decisions :P Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
participants (1)
-
Nick Coghlan