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

[Bryan Olson]

Tim Peters wrote:
 > [Bryan Olson, on the problem at
 >     http://spoj.sphere.pl/problems/SUPPER/
 > ]
 >
 >>I never intended to submit this program for competition. The
 >>contest ranks in speed order, and there is no way Python can
 >>compete with truly-compiled languages on such low-level code.
 >>I'd bet money that the algorithm I used (coded in C) can run
 >>with the winners. I also think I'd wager that the Python version
 >>outright trumps them on code size.
 >
 > 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

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.

The key to fast Python: use a good algorithm, and keep the inner
loop in C.


-- 
--Bryan