<div class="gmail_quote">On Thu, Nov 5, 2009 at 5:02 PM, Raymond Hettinger <span dir="ltr"><<a href="mailto:python@rcn.com">python@rcn.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
def first(iterable):<br>
'Return the first value from a container or iterable. If empty, raises LookupError'<br>
for value in iterable:<br>
return value<br>
raise LookupError('no first value; iterable is empty')<br></blockquote></div><br>(This email should not be construed to mean that I support adding a .pick method; I do not.)<br>
<br>I realized this morning that the "for i in s: break" idiom can be O(n), even assuming no hash collisions. Observe this subtly O(n**2) algorithm:<br><br>Cashew:~$ cat > test.py<br>while s:<br> for i in s:<br>
break<br> # Imagine a complex algorithm here that depends on i still being in s<br> s.remove(i)<br><br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(20000))' "`cat test.py`"<br>
10 loops, best of 3: 31.2 msec per loop<br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(40000))' "`cat test.py`"<br>10 loops, best of 3: 124 msec per loop<br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(80000))' "`cat test.py`"<br>
10 loops, best of 3: 491 msec per loop<br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(160000))' "`cat test.py`"<br>10 loops, best of 3: 1.96 sec per loop<br><br>Doubling n quadruples the run-time, i.e., O(n**2) behavior. <br>
<br>I wonder if those clamoring for a pick() method and complaining about efficiency are inadvertently running into this?<br><br>The problem arises because we're systematically unbalancing the hash table. The iterator returns the first valid entry in the hash table, which we remove. Repeat several times and pretty soon the iterator has to spend O(n) time scanning through empty entries to find the first remaining valid entry.<br>
<br>On the other hand, the pop/add idiom is O(1), since the .pop implementation contains some voodoo to remember where it left off. Consequently, the following algorithm is O(n) instead of O(n**2):<br><br>Cashew:~$ cat > test.py<br>
while s:<br> i = s.pop()<br> s.add(i)<br> # Imagine a complex algorithm here that depends on i still being in s<br>
s.remove(i)<br><br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(400000))' "`cat test.py`"<br>10 loops, best of 3: 28 msec per loop<br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(800000))' "`cat test.py`"<br>
10 loops, best of 3: 56.2 msec per loop<br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(1600000))' "`cat test.py`"<br>10 loops, best of 3: 113 msec per loop<br>Cashew:~$ python2.5 /usr/lib/python2.5/timeit.py -s 's=set(range(3200000))' "`cat test.py`"<br>
10 loops, best of 3: 227 msec per loop<br><br>Doubling n doubles the run-time, i.e., O(n) behavior.<br>
<blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>