Tough sorting problem: or, I'm confusing myself

david jensen dmj.ccc at gmail.com
Thu Apr 15 13:11:00 CEST 2010


On Apr 14, 6:06 pm, Raymond Hettinger <pyt... at rcn.com> wrote:
> > I'm not sure a heap will help much, and at least to me,
> > doesn't improve readability.
>
> nlargest() should save quite a few comparisons and run much faster
> than sorted().
>
> Not sure what the readability issue is.  The phrase "nlargest(2,
> iterable)" does exactly what it says, finds the 2 largest elements
> from an iterable.  That makes the programmer's intent more clear than
> the slower, but semanticly equivalent form:  sorted(iterable)[:2].
>
> The running time for your algorithm can be very long, depending on the
> inputs.  Do you need an exact answer or can you approximate it with
> sampling random combinations (i.e. choose the best two scores out of
> 10000 samples).
>
> Raymond


You are of course correct. I was running on lack of sleep. Thanks
again for having taken the time to help!
I need an exact answer, but don't anticipate 2**m or n to be huge so
even with e.g. m=10 and n=7 it should still be feasible. I can see how
sampling would become necessary if m is large though. Much larger, and
i'd have to think about optimizing the getValues function first
though.

thank you,
David



More information about the Python-list mailing list