efficiently accumulating values

Hi,

I have a small lisp program to solve the boggle puzzle
(http://weboggle.shackworks.com/) and it generates a lot of lists.

This is the main part of the solving code:

(defun find-words (matrix)
"Given MATRIX find all possible words."
(destructuring-bind (m n) (array-dimensions matrix)
;; Find words starting at every position in the matrix
(loop with result = ()
as i from 0 to (1- m)
do (loop as j from 0 to (1- n)
do (setq result (nconc result ; <-- major consing
(get-words matrix i j))))
finally (return result))))

(defun get-words (matrix i j)
"Find all possible words starting from MATRIX position I J"
(labels ((rec (i j prefix acc)
(loop for (ni nj) in (adjacent matrix i j)
as next = (aref matrix ni nj)
as word = (concatenate 'string prefix next)
if (and (>= (length word) *minimum-length*)
(wordp word))
do (push word acc)
when (prefixp word)
do (let ((old (aref matrix i j)))
(setf (aref matrix i j) 'nil
acc (rec ni nj word acc)
(aref matrix i j) old))
finally (return acc))))
(rec i j (aref matrix i j) '())))

;;;;;;;;

Running the problem as it is, takes 2.713 seconds. Throwing away the
results obtained takes only 0.176 seconds. I changed find-words to

(defun find-words (matrix)
"Given MATRIX find all possible words."
(destructuring-bind (m n) (array-dimensions matrix)
(loop with result = (make-hash-table)
as i from 0 to (1- m)
do (loop as j from 0 to (1- n)
;; Find words starting at every position in the
matrix
do (loop as word in (get-words matrix i j)
do (setf (gethash word result) t)))
finally (return (loop as key being the hash-key in result
collect key)))))

This takes 1.786 seconds.

Is there an efficient way to accumulate values in lisp? I translated
this program almost sexp by sexp to Python and that runs in 0.61
seconds and in 0.49 seconds discarding the results.

Lisp is clearly faster except for the consing part. Any suggestions
on improving value accumulation welcome.

Cheers,
Vijay

Can we quote you on that?
A long time ago, someone in the Lisp industry told me it was poor form
quote people; it suggests that they lack value.
-- Kent M Pitman <pitman@xxxxxxxxxxxxx> in comp.lang.lisp

.

Relevant Pages

  • How to Speed up Cellular Automata [was Re: How to speed up an OpenGL application?]
    ... In the loop you hit aref a dozen times, god knows what else, without an iota of optimization. ... Lisp does more by default, so if you need to write ... (if (zerop cell) ...
    (comp.lang.lisp)
  • Re: A style question
    ... "The loop macro was originally designed to help inexperienced Lisp ... than its designers ever intended...to understand it in the abstract is ... I started playing with it, but I am just an elder, not a Lisp elder. ...
    (comp.lang.lisp)
  • Re: Very poor Lisp performance
    ... Observe LOOP, ... than many Lisp users, as LOOP is offensive to a percentage of Lisp ... >>> natural and programming languages have complicated grammars precisely ... do you agree that languages are evolving to be more concise? ...
    (comp.lang.lisp)
  • Re: YANQ - When to map, when to iterate, when to recurse? And why CLOS?
    ... Is it just LOOP allergy, ... > lot of iteration constructs in other languagesis it just a matter of taste, ... controversial Common Lisp form, in that there are a fair number of Lisp ... There's also a more obscure solution involving the PROG1 form, ...
    (comp.lang.lisp)
  • Re: Pretty-print question
    ... Is there a way to get lisp to print this with the columns lining up? ... for directed graphs works by putting a 1 in (aref matrix x y) if there ... is a directed edge from x to y, ...
    (comp.lang.lisp)