Re: efficiently accumulating values

liyer.vijay@xxxxxxxxx wrote:
Any other suggestions? What am I doing wrong?

Vijay, I'm not sure what is going on, but something seems wrong about
the numbers you are getting.

I coded up something for the functions that you haven't posted yet,
because it did not make sense to me that get-words good be so fast
compared to the find-words code.

I did a quick and dirty implementation using two hash tables, one to
store all the 262149 words of length between 4 and 25 characters in the
word game dictionary at http://www.gtoal.com/wordgames/yawl/word.list,
and another to store the 416439 prefixes of those words. That made wordp
and prefixp be simple hash lookups, probably not quite as efficient as
using tries, but good enough for this test.

I also did not put effort into optimizing the adjacent function or
avoiding concatenating new strings in get-words.

I did find a bug in your code, which I don't see how you avoided, as it
caused infinite recursion and a crash when I tried to run.

The bug is in the loop in get-words, that you never check if the return
value from (aref matrix ni nj) is nil, which indicates that position (ni
nj) has already been used. Here is how it can cause an infinite loop:

Let's say position (0 0) is "r", (1 1) is "e" and (1 0) is "s". When you
have checked those three and are now in a call to (rec 1 0 "res" acc),
when you then check the adjacent sell (0 0) the variable next is set to
(concatenate 'string "res" nil) which is "res". That is not a word and
is a prefix, resulting in a call to (rec 0 0 "res" acc). When that
checks position (1 0) it also finds a nil value, resulting in the prefix
remaining "res" and another cal to (rec 1 0 "res" acc). And you have an
infinite loop.

Oh, I guess if you check the contents of (aref matrix x y) and if it is
nil don't add (list x y) to the return value in the call to (adjacent
matrix i j) then that would also avoid the bug, but that seems like it
would be more expensive than testing for next being null in get-words.
So maybe you don't have this bug. I can't tell without seeing your
adjacent function.

Another bug is that the hash-table version has different results than
the others. Try looking at the length of the return values from
find-word. The hash-table implementation removes duplicates, which may
give you some speedup. That's probably more correct for a Boggle game
application. The other methods will return a word multiple times if it
can be found in different paths in the matrix.

Anyway, the numbers I got showed little variation between the different
find-word functions, with the loop nconcing one being a bit faster than
the hash-table or vector-push-extend ones. The throw the data away one
was not significantly faster, unlike your result.

I then tried the following implementation of get-words:

I renamed your get-words to get-words-orig, then

(defparameter *graph*)

(defparameter *words*
(make-array '(5 5)))

(defun setgraph ()
(setf *graph*
(make-array '(5 5)
:initial-contents
'(("r" "s" "t" "c" "s")
("d" "e" "i" "a" "e")
("g" "n" "l" "r" "p")
("e" "a" "t" "e" "s")
("m" "s" "s" "i" "d")))))

(defun setwords ()
(setgraph)
(dotimes (i 5)
(dotimes (j 5)
(setf (aref *words* i j) (get-words-orig *graph* i j)))))

(defun get-words (matrix i j)
"Find all possible words starting from MATRIX position I J"
(declare (ignore matrix))
(copy-list (aref *words* i j)))


With this test version of get-words, I get the same results as the
original get-words but much faster. The copy-list is necessary because
nconc is destructive

The original get-words gave me a time result for the nconcing version
using your time function of 0.142 seconds running sbcl on a 2GHz MacBook
(Intel cpu).

With that faked get-words, the same run took 0.0001 seconds.

That indicates that get-words is the bottleneck, not find-words

Could you post a full example showing all of your code and telling us
what you are using as a dictionary and how many words find-word is
returning?


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