[Tutor] 6x6 word square solver too slow

Alan Gauld alan.gauld at btinternet.com
Fri Apr 25 01:22:20 CEST 2008

"R. Alan Monroe" <amonroe at columbus.rr.com> 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 
                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

More information about the Tutor mailing list