On Tue, Feb 19, 2013 at 8:54 AM, Ian Kelly <ian.g.ke...@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.

ChrisA
-- 
http://mail.python.org/mailman/listinfo/python-list

Reply via email to