Speed quirk: redundant line gives six-fold speedup

Mark Dickinson dickinsm at verizon.net
Thu Aug 25 21:20:38 CEST 2005


In article <mailman.3532.1124995353.10512.python-list at python.org>, Bill 
Mill <bill.mill at gmail.com> wrote:
 
> I'm also pretty sure I've caught a bug in his code, though I'm not
> sure how it works exactly. I replaced the 'min' built-in with my own
> min, and he's going to get nondeterministic results from this line:
> 
>        mm = min((c.S, c) for c in rowitems(h))[1].D
> 
> because 'c' is often the exact same object. A snippet from my
> debugging version of 'min', which prints out the tuple its handed:
> 
> (1, <  main  .LLentry object at 0x00969710>)
> (1, <  main  .LLentry object at 0x00969710>)
> (4, <  main  .LLentry object at 0x00969710>)
> <snip more 4s from the same object>
> (4, <  main  .LLentry object at 0x00969710>)
> (3, <  main  .LLentry object at 0x00969710>)
> (3, <  main  .LLentry object at 0x00969710>)
> (3, <  main  .LLentry object at 0x00969710>)
> (2, <  main  .LLentry object at 0x00969710>)
> <snip more 2s, same object>

The c's returned by any one call to rowitems(h) should all be distinct. 
This seems to work in my code---I can't reproduce your results above, and
I don't *think* there's a bug there.

> Although they appear in order here, they don't always. Often, multiple
> objects have a value of 1, and he's going to get one of them at random
> as the 'min' object. I'm pretty sure.

I agree entirely---this is where my bug, and the source of 
all the confusion comes from.  I was briefly aware as I wrote this that the
result would be nondeterministic, but persuaded myself after two second's
thought that it didn't matter, then forgot all about it.

So mild changes in the rest of the program give rise to a different `random'
choice in the min, and choosing to eunumerate all 3 possibilities for position 5,7
instead of the 3 possibilities for position 2, 1 (say) makes a huge diffference
to the running time.  I'm still surprised by the magnitude of the differences, though.

I've learnt my lesson :)  Thank you for your help, and apologies 
for wasting other people's time with this as well as my own!

Mark



More information about the Python-list mailing list