List of integers & L.I.S. (SPOILER)

[Tim Peters]

[Tim Peters, on the problem at
     http://spoj.sphere.pl/problems/SUPPER/
]
>> Oh, it's not that bad <wink>.  I took a stab at a Python program for
>> this, and it passed (3.44 seconds).
>> ...
>> I didn't make any effort to speed this, beyond picking a reasonable
>> algorithm, so maybe someone else can slash the runtime

[Bryan Olson]
> Hmmm ... I used the Theta(n lg n) algorithm ... how the heck...
> Aha! The 'bisect' module changed since last I looked. It still
> has the Python implementation, but then the last few lines say:
>
>     # Overwrite above definitions with a fast C implementation
>     try:
>         from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
>     except ImportError:
>         pass
> 
> Binary-search is the inner-loop in this algorithm. I wrote my
> own binary-search, so I was executing Theta(n lg n) Python
> statements. Tim's use of bisect means that his inner-loop is
> in C, so he does Theta(n) Python statements and Theta(n lg n) C
> statement.

That's part of it, but doesn't account for enough.  If I disable the C
implementation of bisect (replace the "from ..." import above with a
"pass"), the program takes about 50% longer, which would still leave
it well under the 9-second SPOJ time limit.  That's without psyco. 
With psyco, it takes about the same time with the Python
implementation of bisect as with the C implementation.

Proably more important was my findall() routine.  It does redundant
work, and its runtime seems hard to analyze, but it's conceptually
simple and actual timing showed it takes about a third of the time
consumed by my crack() on random 100,000-element permutations.  In
fact, findall() takes very close to the amount of time needed just to
read a giant line of input and convert it to a list of ints (without
psyco; with psyco converting the input takes longer than findall()).

Possible surprise:  there's a simple trick that allows rewriting
findall() to produce the result list in sorted order directly, instead
of building it in "random" order and sorting it at the end.  That made
no measurable difference.

> The key to fast Python: use a good algorithm,

Absolutely!

> and keep the inner loop in C.

Usually ;-)

Add another:  especially for long-term maintenance, readability,
stability and performance, use a library function instead of rolling
your own.  The chance that Raymond Hettinger is going to recode _your_
functions in C is approximately 0 ;-)