(original) (raw)
On 9/4/07, "Martin v. L�wis" <martin@v.loewis.de> wrote:
And if the speed of d[x] were ever an issue that shows up on python performance profiles when used in a loop like that it would be pretty easy to optimize the common case internally by having the key iteration retain an optional (weak?) reference in the dict object to the most recently looked up key+value for a short circuit quickly returning its value. I do not expect that to ever to matter as code can just loop using the appropriate iterator instead.
-gps
> (assuming d[x] is O(log n))
In Python, d[x] is typically considered to be O(1) (unlike in C++,
where it is O(log n)). Of course, with Python using a hashtable,
performance may decrease in the presence of collisions. In the
normal case, dict((x, d[x]) for x in d) will be O(n) in Python.
And if the speed of d[x] were ever an issue that shows up on python performance profiles when used in a loop like that it would be pretty easy to optimize the common case internally by having the key iteration retain an optional (weak?) reference in the dict object to the most recently looked up key+value for a short circuit quickly returning its value. I do not expect that to ever to matter as code can just loop using the appropriate iterator instead.