<br><br><div><span class="gmail_quote">On 9/4/07, <b class="gmail_sendername">&quot;Martin v. L÷wis&quot;</b> &lt;<a href="mailto:martin@v.loewis.de">martin@v.loewis.de</a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
&gt; (assuming d[x] is&nbsp;&nbsp;O(log n))<br><br>In Python, d[x] is typically considered to be O(1) (unlike in C++,<br>where it is O(log n)). Of course, with Python using a hashtable,<br>performance may decrease in the presence of collisions. In the
<br>normal case, dict((x, d[x]) for x in d) will be O(n) in Python.</blockquote><div><br>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.&nbsp; I do not expect that to ever to matter as code can just loop using the appropriate iterator instead.
<br></div><br></div>-gps<br>