Nitpicking, but this statement doesn't work with large numbers (which xrange() is supposed to handle correctly):
self._len = int(ceil(float(stop - start) / step))
Python supports arbitrary-length integers; you can't just cast those to (fixed-length) floating point numbers without losing precision. It's better to use integer division here, for example:
(A variant like (stop - start + step - 1)//step works only for positive numbers; I guess it could work if you put it in the earlier if-clause and put a corresponding assignment with +1 at the end in the other branch.)
A related nitpick: since Python's integers are arbitrary size, technically operations like - and / are not constant time, so your claim of an implementation "with constant-time and constant-space operations" is not true.
However, I understand if that complaint is just too nitpicky for you to want to mention it. Great post btw.
This is cool. I know this isn't how they actually do it, but seeing it in a language I can understand (Python) and not in C is really pleasing.
You can do tons of examples, but until you figure out how the machine works inside, you'll be completely lost (you could get it with examples, but you won't necessarily know WHY you got it, so you'll be useless in helping other people learn).
I had a _very_ similar question during my Google interview. In the course of the day I was tasked with implementing a generator (although answering with `(x for x in foo)` got a smile I did have to build a class) and later in the day was asked how a sequence manager can maintain constant time.
This is an excellent post and every Python hacker should read it. Kudos to the author.
I feel that this kind of combination of lazy evaluation for sequences, together with eager evaluation for imperative code hits a particular sweet spot. Python and Clojure have very nice lazy sequences.
I would not do such a change to the if step block since its pattern feels noticeably different: "open" checks fit well in a if/else, whereas bunch-of-equalities fit a dispatch map better (plus you can actually modify the map at runtime).
To me your version is less clearer than the explicit if calls:
* Name 'map' for a variable is a poor choice (as it has same
name as the python builtin function map)
* Your version has off by one error, it doesn't give correct results when called with a single element list or if the list has three elements:
>>>mymap = [
lambda args: (0, args[0], 1),
lambda args: (args[0], args[1], 1),
lambda args: args,
]
>>>args = [5]
>>>mymap[len(args)](args)
IndexError
Traceback (most recent call last)
....
# This shouldn't be the case, a list with a single
# element is a valid input
>>>args = [1,6,1]
>>>mymap[len(args)](args)
IndexError Traceback (most recent call last)
...
# This shouldn't be the case, a list with a three
# elements is a valid input
That imho seems like overcomplicating a relatively straight-forward piece of code without noticeable improvement. In the original code the intent is clear from the first line ("check the number of arguments"), but in your version I have to parse 7 lines of code before I find out that. Also in your code I'm required to keep larger, more complicated state (the map array) in my head when reading it. Your version also looks like it would perform worse than the original. Imho code that looks like it performs suboptimally is code that looks ugly, even if the performance difference in reality would be negligible.
I cried a little bit on the inside when he said that that the iterator should not be implemented using generators, etc. Writing iterators by hand forces one to turn the iteration code inside out and it can be a painful experience if the logic is anything nontrivial.
But there's a good motivation here: (x)range objects are supposed to be index-able, while a generator (expression) cannot go back once an element has been consumed.
27 comments
[ 4.1 ms ] story [ 85.3 ms ] threadHowever, I understand if that complaint is just too nitpicky for you to want to mention it. Great post btw.
For example, int(float(10¹⁸ - 1)) != 10¹⁸ - 1, but xrange(1, 10¹⁸) is perfectly valid (even in Python 2).
edit: how do I type two consecutive asterisks on Hacker News? Backslash doesn't seem to work as an escape character.
Edit: failure. That's two stymied people :(
You can do tons of examples, but until you figure out how the machine works inside, you'll be completely lost (you could get it with examples, but you won't necessarily know WHY you got it, so you'll be useless in helping other people learn).
This is an excellent post and every Python hacker should read it. Kudos to the author.
I would not do such a change to the if step block since its pattern feels noticeably different: "open" checks fit well in a if/else, whereas bunch-of-equalities fit a dispatch map better (plus you can actually modify the map at runtime).
* Name 'map' for a variable is a poor choice (as it has same name as the python builtin function map)
* Your version has off by one error, it doesn't give correct results when called with a single element list or if the list has three elements:
As a side-note, here's a related article on implementing a Python generator "for real" using the C API: http://eli.thegreenplace.net/2012/04/05/implementing-a-gener...