Re: efficiently accumulating values


Pascal Bourguignon wrote:
liyer.vijay@xxxxxxxxx writes:

liyer.vijay@xxxxxxxxx wrote:
[snip my own stuff]

Hi,

I found the reference in PCL (Peter, if you're reading this, thanks)
to VECTOR-PUSH-EXTEND which dramatically reduces time to 0.346
seconds. Here is the program:

(defun find-words (graph)
"Given GRAPH find all possible words."
(destructuring-bind (m n) (array-dimensions graph)
(loop with result = (make-array 0 :adjustable t :fill-pointer 0)
as i from 0 to (1- m)

I'd write:

:for i :from 0 :below m

Some would write:

for i below m

do (loop as j from 0 to (1- n)
do (loop as word in (get-words graph i j)
if (and (zerop i) (zerop j))
do (vector-push-extend word result)))
finally (return (coerce result '(or cons list))))))

list == (or nil cons) therefore (or cons list) == list

Pascal,

Thank you for both these suggestions, I have changed all places where
I used (loop as i from 0 to (1- m)) to (loop as i from 0 below m).

And thanks for telling me what the N in functions like nconc nreverse
nunion etc was. I'd always wondered :-)

And I now see I originally misunderstood what you meant. I should
have simply typed (coerce result 'list)


However, I'd still like to know if there's a better way, and since I
didn't mention it in my last post, any suggestions, comments,
criticisms on coding style, programming are greatly appreciated.

Now, what you seem to be doing in find-words, is jusd that:

(defun find-words (graph)
"Given GRAPH find all possible words."
(let ((words (get-words graph 0 0)))
(if words
(copy-list words)
'())))

I dont' understand, could you explain more clearly? I search for
words from every position in the graph. Or did you mean that I create
a list and throw it away immediately?

Unless get-words is not a pure function. Do you have any side effect
in get-words?

I don't know if I can say GET-WORDS is a pure function.

These properties of GET-WORDS are definitely true:

(eq matrix (progn (get-words matrix) matrix)) == T

and

(let* ((matrix (make-graph "rstcsdeiaegnlrpeatesmssid"))
(seq (make-array 25 :displaced-to matrix)))
(every #'eq seq (progn (find-words matrix) seq)))

== T

But I make a destructive change to a a cell in MATRIX in GET-WORDS and
later undo that change (so it probably isn't thread-safe).

Here is GET-WORDS

(defun get-words (graph i j)
"Find all possible words starting from GRAPH position I J"
(labels ((rec (i j prefix acc)
(loop for (ni nj) in (adjacent graph i j)
as next = (aref graph 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 graph i j)))
(setf (aref graph i j) 'nil ; change cell
acc (rec ni nj word acc)
(aref graph i j) old)) ; restore change
finally (return acc))))
(rec i j (aref graph i j) '())))

--
__Pascal Bourguignon__ http://www.informatimago.com/

Thank you
Vijay

.

Relevant Pages

  • Re: efficiently accumulating values
    ... (defun find-words (graph) ... "Given GRAPH find all possible words." ... If get-words has no side effect, then the loops are useless, since i ... (loop as word in (get-words graph i j) ...
    (comp.lang.lisp)
  • Re: efficiently accumulating values
    ... to VECTOR-PUSH-EXTEND which dramatically reduces time to 0.346 ... (defun find-words (graph) ... "Given GRAPH find all possible words." ... Unless get-words is not a pure function. ...
    (comp.lang.lisp)