Re: efficiently accumulating values

liyer.vijay@xxxxxxxxx writes:

Pascal Bourguignon wrote:
Now, what you seem to be doing in find-words, is just 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?


Let's start again from your function:

1 (defun find-words (graph)
2 "Given GRAPH find all possible words."
3 (destructuring-bind (m n) (array-dimensions graph)
4 (loop with result = (make-array 0 :adjustable t :fill-pointer 0)
5 as i from 0 to (1- m)
6 do (loop as j from 0 to (1- n)
7 do (loop as word in (get-words graph i j)
8 if (and (zerop i) (zerop j))
9 do (vector-push-extend word result)))
10 finally (return (coerce result '(or cons list))))))


On line 8,9 you test if (and (zerop i) (zerop j))
and push the word to the result only when both i and j are 0.

If get-words has no side effect, then the loops are useless, since i
and j will be 0 only once.


If we add some FORMAT expression to have a look at how your function work:

(defun get-words (graph i j)
(if (and (zerop i) (zerop j))
(list "target word")
(list "other word")))

(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)
do (loop as j from 0 to (1- n)
initially (format t "~&~D: " i)
do (format t "~D " j)
(loop as word in (get-words graph i j)
if (and (zerop i) (zerop j))
do (assert (and (zerop i) (zerop j)))
(format t "~&[~D:~D] --> ~S~% " i j word)
(vector-push-extend word result)))
finally (return (coerce result '(or cons list))))))

Here is what we get:

[152]> (find-words (make-array (list 10 10)))
0: 0
[0:0] --> "target word"
1 2 3 4 5 6 7 8 9
1: 0 1 2 3 4 5 6 7 8 9
2: 0 1 2 3 4 5 6 7 8 9
3: 0 1 2 3 4 5 6 7 8 9
4: 0 1 2 3 4 5 6 7 8 9
5: 0 1 2 3 4 5 6 7 8 9
6: 0 1 2 3 4 5 6 7 8 9
7: 0 1 2 3 4 5 6 7 8 9
8: 0 1 2 3 4 5 6 7 8 9
9: 0 1 2 3 4 5 6 7 8 9
("target word")

Only when i=0 and j=0 do we push a word to the result.
Why then should we scan the array?


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

This is always true (as long as get-words hasn't matrix in its lexical
scope to modify its binding).


What may be more interesting is whether:

(equalp (copy-array matrix) (progn (get-words matrix) matrix))


and

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

== T

You cannot ensure that, since EQ for characters may return true or
false randomly.


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).

Ok, so it's essentially side-effect-free, and you don't earn anything
by calling it a hundred times when you keep only the result of
(get-words graph 0 0).



--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
.

Relevant Pages

  • 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)
  • Re: efficiently accumulating values
    ... Here is the lisp I wrote when I fisrt came with my questions. ... (loop as line = (read-line stream nil nil) ... (defun find-words (graph) ... "Given GRAPH find all possible words." ...
    (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)
  • Re: efficiently accumulating values
    ... "Given GRAPH find all possible words." ... do (loop as word in (get-words graph i j) ... do (let ((old (aref graph i j))) ... acc (rec ni nj word acc) ...
    (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)