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
--
http://mail.python.org/mailman/listinfo/python-list
