Python 3.3 vs. MSDOS Basic
rosuav at gmail.com
Mon Feb 18 23:01:06 CET 2013
On Tue, Feb 19, 2013 at 8:54 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
> Well, I don't see anything that looks especially slow in that code,
> but the algorithm that you're using is not very efficient. I rewrote
> it using dynamic programming (details left as an exercise), which got
> the runtime down to about 4 seconds.
Did it involve a dictionary, mapping a value to its count, so that any
time you hit a value you've seen, you can short-cut it? That was my
first optimization consideration, though I didn't implement it in any
version, so as to keep the timings comparable.
More information about the Python-list