"R. Alan Monroe" <[EMAIL PROTECTED]> wrote
Any bright ideas on how I can speed this up?
It seems REALLY slow for as little as it does.
I'm not sure its doing so "little"!
In particular, the profiler indicates that {method 'join' of 'str'
objects} is eating an awful lot of time (odd...),
Not odd, consider this snippet from solve()
for letter in nextletterset:
for maybefuture in worddict[letter]:
futurezip = zip(*currentwords+[maybefuture])
futureprefixes = [''.join(z) for z in futurezip]
validprefixes = [f in worddict for f in
futureprefixes]
if not False in validprefixes:
solve( currentwords + [maybefuture], depth + 1 )
Here you call join() at the third level of nested for loops.
And then you call solve recursively at that same level
where join gets called inside 3 more levels of loop.
That effectively means join is getting called at 6 levels
of loop nesting for just one recursive call, but you could
be doing more than that. In fact it would be an interesting
exercise to add a counter just before the join call to see
how many times it gets called altogether - I predict a
very big number.... :-)
However, as to fixing it thats another story.
It may be possibler to reduce the need to cycle over everything
each time by using a combination of pre-sorting the lists and
using a clever regex to select a subset of entries to which the
comparisons need be done. But I'm not sure how much that
would help, if at all.
However I suspect any attempt to improve performance
here needs a new algorithm and probably a clever data
structure to minimise brute force tests.
--
Alan Gauld
Author of the Learn to Program web site
http://www.freenetpages.co.uk/hp/alan.gauld
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
