Re: efficiently accumulating values

Ken Tilton wrote:
liyer.vijay@xxxxxxxxx wrote:
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))))

Consing? Where? All I can see is that NCONC needs to read down to the
end of the list each time before it can splice.

Sorry, wrong term. I was under the impression NCONCing was consing
also. I guess only APPENDing is (correct me if I'm wrong).

I suggest you keep also a "tail" variable, initialized to nil.
Then (untested):

(if result
(rplacd tail gotten-words)
(setf result gotten-words))
(setf tail (last1 gotten-words))

I hear LOOP is pretty clever. Maybe it does that for you if you use the
NCONCING accumulation clause (nested in this case)(untested also):

(loop for i below m
nconcing (loop for j below n
nconcing (get-words matrix i j)))

Thanks for both these suggestions. The first one:

(defun find-words (graph)
"Given GRAPH find all possible words."
(destructuring-bind (m n) (array-dimensions graph)
(loop with result = () and tail = ()
as i from 0 to (1- m)
do (loop as j from 0 to (1- n)
as gotten-words = (get-words graph i j)
if result do (rplacd tail gotten-words)
else do (setf result gotten-words)
do (setf tail (last gotten-words))) ; you meant
LAST, right?
finally (return result))))

takes 2.10 seconds and letting LOOP nconc

(defun find-words (graph)
"Given GRAPH find all possible words."
(destructuring-bind (m n) (array-dimensions graph)
(loop as i from 0 to (1- m)
nconcing (loop as j from 0 to (1- n)
nconcing (get-words graph i j)))))

is slightly faster at 2.08 seconds and significantly cleaner.

P.S. Please disregard my previous post where I said using
PUSH-VECTOR-EXTEND is much faster, I had kept an IF for debugging
which I'd forgotten to remove. PUSH-VECTOR-EXTEND takes approximately
the same time as my old NCONCing version. (Nonetheless, many thanks
for the book, Peter).

kenny

Thank you Kenny
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

  • Re: efficiently accumulating values
    ... and it generates a lot of lists. ... do (loop as j from 0 to (1- n) ... (setf result gotten-words)) ... Maybe it does that for you if you use the NCONCING accumulation clause: ...
    (comp.lang.lisp)
  • Re: efficiently accumulating values
    ... "Given GRAPH find all possible words." ... nconcing (loop as j from 0 to (1- n) ... nconcing (get-words graph i j))))) ...
    (comp.lang.lisp)
  • Re: efficiently accumulating values
    ... (defun find-words (matrix) ... do (loop as j from 0 to (1- n) ... (setf result gotten-words)) ... NCONCING accumulation clause: ...
    (comp.lang.lisp)
  • Re: an old worn interview question
    ... I suppose Oracle could implement this in a cheesy fashion: ... the size of the graph, ... I doubt hierarchical query loop detection is possible. ...
    (comp.programming)
  • Re: efficiently accumulating values
    ... (defun find-words (graph) ... "Given GRAPH find all possible words." ... do (loop as word in (get-words graph i j) ...
    (comp.lang.lisp)