My aim was to maintain two lists with the same elements sorted by cadr
and cddr (a point is (cons x y)) then tag ('tag (x . y)) them so that I
can change the tags in one list and they'll change in the other. The
point is to split both lists in kd-aux based on the data in one list and
never have to re-sort them.
The first problem seems to arise in the inner let of kd-tree which is
where the hairy(?) mutation begins. It seems that cmucl and sbcl (debian
unstable versions) like to give a truncated y-points list most (but not
all) of the time. I think that there is more horror like this in kd-aux
but I haven't had time to look into it yet. The funny thing is I
actually developed this on a Clisp + XP machine and it works fine there.
(defun tag-points (points)
(mapcar (lambda (point) (cons t point)) points))
(defun kd-tree (points)
(let ((tagged-points (tag-points points)))
(let ((x-points (sort tagged-points #'> :key #'cadr))
(y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
(print x-points)
(print y-points)
(kd-aux x-points y-points))))
(defun kd-aux (x-points y-points)
(let* ((rx) (ry) (lx) (ly)
(mid (ash (length x-points) -1))
(count 0)
(node))
(dolist (pt x-points)
(cond
((> count mid) (setf (car pt) 'r) (push pt rx))
((< count mid) (setf (car pt) 'l) (push pt lx))
(t (setq node pt) (setf (car pt) nil)))
(incf count))
(dolist (pt y-points)
(case (car pt)
('r (push pt ry))
('l (push pt ly))))
(if (zerop mid)
(list (point node))
(list (point node)
(kd-aux (reverse ly) (reverse lx))
(kd-aux (reverse ry) (reverse rx))))))
(defun random-points (num)
(let ((res))
(dotimes (i num res)
(push (cons (random 400)
(random 400))
res))))
Try (kd-tree (random-points 10)) and look at the prints' output. They
might have different lengths.
Charlieb.
From: Marco Baringer
Subject: Re: Am I pushing my luck with this?
Date:
Message-ID: <m23c06ycio.fsf@bese.it>
just a few quick notes, i haven't actually tried runnig it.
charlieb <··@privacy.net> writes:
> (defun kd-tree (points)
> (let ((tagged-points (tag-points points)))
> (let ((x-points (sort tagged-points #'> :key #'cadr))
> (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
1) sort is a destructive operation.
2) copy-list only copyies the list of cons cells, not their contents.
> (print x-points)
> (print y-points)
> (kd-aux x-points y-points))))
> (defun kd-aux (x-points y-points)
> (let* ((rx) (ry) (lx) (ly)
in this let* none of the inits depend on a previous init, i'd use let
(just so that people don't keep trying to see what init depends on
what).
> (mid (ash (length x-points) -1))
what's wrong with (/ (length x-points) 2)?
> (count 0)
> (node))
> (dolist (pt x-points)
> (cond
> ((> count mid) (setf (car pt) 'r) (push pt rx))
> ((< count mid) (setf (car pt) 'l) (push pt lx))
> (t (setq node pt) (setf (car pt) nil)))
> (incf count))
> (dolist (pt y-points)
> (case (car pt)
> ('r (push pt ry))
> ('l (push pt ly))))
the values in case clauses are not evaluated. what you've actually
written is:
(case (car pt)
((quote r) (push pt ry))
((quote l) (push pt ly)))
the presence of the symbol QUOTE in both clauses gives (afair)
undefined behaviour.
> (if (zerop mid)
> (list (point node))
> (list (point node)
> (kd-aux (reverse ly) (reverse lx))
> (kd-aux (reverse ry) (reverse rx))))))
>
> (defun random-points (num)
> (let ((res))
> (dotimes (i num res)
> (push (cons (random 400)
> (random 400))
> res))))
>
> Try (kd-tree (random-points 10)) and look at the prints' output. They
> might have different lengths.
hth.
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
"Marco Baringer" <··@bese.it> writes:
> (case (car pt)
> ((quote r) (push pt ry))
> ((quote l) (push pt ly)))
>
> the presence of the symbol QUOTE in both clauses gives (afair)
> undefined behaviour.
"Each of the normal-clauses is then considered in turn."
So I think the first QUOTE merely hides the second one.
On Fri, 22 Oct 2004 16:30:29 +0100, charlieb wrote:
> The first problem seems to arise in the inner let of kd-tree which is
> where the hairy(?) mutation begins. It seems that cmucl and sbcl (debian
> unstable versions) like to give a truncated y-points list most (but not
> all) of the time. I think that there is more horror like this in kd-aux
> but I haven't had time to look into it yet. The funny thing is I
> actually developed this on a Clisp + XP machine and it works fine there.
> (defun tag-points (points)
> (mapcar (lambda (point) (cons t point)) points))
> (defun kd-tree (points)
> (let ((tagged-points (tag-points points)))
> (let ((x-points (sort tagged-points #'> :key #'cadr))
This call to SORT destroys TAGGED-POINTS.
> (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
This call to COPY-LIST copies the list you just destroyed.
--
Malum est consilium quod mutari non potest -- Publilius Syrus
(setq reply-to
(concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
Thanks for the info, everyone. Does this mean that destructive
operations like sort can not only mess with the top-level of the list
they are dealing with but also the elements in the list so copying the
list both times is also unsafe:
(let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
(y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
...)
Cheers for the case info as well.
Thanks
Charlieb
charlieb wrote:
> Thanks for the info, everyone. Does this mean that destructive
> operations like sort can not only mess with the top-level of the list
> they are dealing with but also the elements in the list so copying the
> list both times is also unsafe:
>
No, sort only moves around the top-level elements of a list; it doesn't
touch any sublists except for reading the key.
The point was that copy-list will only copy the top level, but that's enough
to make sort work without altering the original list.
> (let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
> (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
> ...)
This should work just fine.
charlieb wrote:
> (let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
> (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
> ...)
This works fine, but FYI x-points and y-points will share structure in the
sub-lists. This isn't neccessarily a problem, but you ought to be aware of
it.
Svein Ove Aas <·········@aas.no> wrote in message news:<············@services.kq.no>...
> charlieb wrote:
>
> > (let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
> > (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
> > ...)
>
> This works fine, but FYI x-points and y-points will share structure in the
> sub-lists. This isn't neccessarily a problem, but you ought to be aware of
> it.
Excellent, that was my plan.
Cheers,
Charlie