Re: efficiently accumulating values

liyer.vijay@xxxxxxxxx wrote:
Here is the lisp I wrote when I fisrt came with my questions.

I see the problem now. Our machines are of similar speed and we are both
using sbcl, so I get results quite close to yours on your code.

The problem is that you are timing the entire boggle function, and
almost all the time is being spent in the final delete-duplicates of the
return value from find-words. Without the delete-duplicates, you see the
tenth of a second run time that you have in the "discarding results"
case. Since our run times are so similar I can say with confidence that
almost all of that tenth of a second is spent in get-words, mostly in
the hash table lookups in the calls to wordp and prefixp. find-words
itself is very fast, so when you try out variations you are only seeing
speed variations on the order of one or two hundredths of a second.

The odd fast timing in the hash-table version is because the hash-table
based find-words does not produce any duplicates. The call to
delete-duplicates still takes a long time in that case, but it is being
passed a much shorter list and is therefore faster than in the other
cases. You can experiment with variations that also have that property
such as adding a word to the accumulated list using pushnew, or using
nunion instead of nconc to see if the overall savings makes up for the
extra operations each time you add words to the accumulated results. Or
perhaps you could have some extra slot in the dictionary items to record
when a word has been used in a particular run, skipping it if it is
encountered again in that run.

In any case, with the bulk of your time being spent eliminating
duplicates, your biggest immediate savings are to be had avoiding adding
duplicates in the first place.

When I was timing I was doing the equivalent of

(setf *testgraph* (make-graph (string-downcase letters)))
(time (find-words *testgraph*)

which avoided including the setup time for the graph or the
delete-duplicates that I did not know about until you posted the boggle
function.

That reveals the next biggest candidate for optimization, which is the
get-hash calls in get-word. That's where using a trie might help.


--
Sidney Markowitz
http://www.sidney.com
.