Massoc, cdrs & C.

[Anonymous]

I am trying of to get better performances to elaborate
very big lists but I have not had resulted appreciable,
where am I being wrong?


; Michael Puckett
(defun cdrs (DxfKey ImpLst / TmpLst OutLst)
(while (setq TmpLst (assoc DxfKey ImpLst))
(setq OutLst (cons (cdr TmpLst) OutLst)
ImpLst (cdr (member TmpLst ImpLst))
)
)
(reverse OutLst)
)

(defun ALE_MASSOC2 (DxfKey ImpLst / OutLst)
(
(eval
(function
(lambda (x / TmpLst)
(while (setq TmpLst (assoc DxfKey x))
(setq OutLst (cons (cdr TmpLst) OutLst)
x (cdr (member TmpLst x))
)
)
)
)
)
ImpLst
)
(reverse OutLst)
)

(defun ALE_MASSOC3 (DxfKey ImpLst / OutLst)
(
(lambda (x / TmpLst)
(while (setq TmpLst (assoc DxfKey x))
(setq OutLst (cons (cdr TmpLst) OutLst)
x (cdr (member TmpLst x))
)
)
)
ImpLst
)
(reverse OutLst)
)

(defun ALE_MASSOC4 (DxfKey ImpLst / OutLst)
(apply
(function
(lambda ( / TmpLst)
(while (setq TmpLst (assoc DxfKey ImpLst))
(setq OutLst (cons (cdr TmpLst) OutLst)
ImpLst (cdr (member TmpLst ImpLst))
)
)
)
)
nil
)
(reverse OutLst)
)

(defun ALE_MASSOC5 (DxfKey ImpLst / OutLst)
(apply
(function
(lambda (x / TmpLst)
(while (setq TmpLst (assoc DxfKey x))
(setq OutLst (cons (cdr TmpLst) OutLst)
x (cdr (member TmpLst x))
)
)
)
)
(list ImpLst)
)
(reverse OutLst)
)

--
________________________________________________

Marc'Antonio Alessi (TV) Italy - maalessi@tin.it
(strcat "NOT a " (substr (ver) (if (= 15
(atoi (getvar "acadver"))) 8 5) 4) " guru.")

O.S. = XP Pro 2002 - Sp.1 - Ita
AutoCAD = 2002 Ita - Sp.1
_VERNUM = "K.0.44"
ACADVER = "15.06s (LMS Tech)"
(ver) = "Visual LISP 2000 (it)"
________________________________________________

[Anonymous]

Marc,

Try these:

;I don't know if someone else has penned this
;before, but this one should be quite fast
(defun es:cdrs (Key In / Out)
(foreach itm In
(if (= (car itm) key)
(setq Out (cons (cdr itm) Out))
)
)
(reverse Out)
)

;;;Eric Schneider
;;;Added mapcar 'cdr
;;;Bobby Jones
;;;My version of massoc
;;;The keys are left with the data
;;;but can easily be removed with:
;;;(mapcar 'cdr (massoc lst key))
(defun massoc (key lst)
(mapcar 'cdr (vl-remove-if-not '(lambda (x) (= (car x) key)) lst))
) ;_ end of defun

--

Regards,
Eric S.
A2k/W2k

[Anonymous]

OK. So I was wrong. It's probably the slowest of all.
--

Regards,
Eric S.
A2k/W2k

[Anonymous]

I have a collection of "massoc" but the fastest is:

;M. Puckett
(defun cdrs (DxfKey ImpLst / TmpLst OutLst)
(while (setq TmpLst (assoc DxfKey ImpLst))
(setq OutLst (cons (cdr TmpLst) OutLst)
ImpLst (cdr (member TmpLst ImpLst))
)
)
(reverse OutLst)
)

and it works in <2000 also.

I tried to have better performance using lambda but
the result is "about" 1-3% less in big lists
(3000-8000 vertex in lwpolyline data), also in
normal compiled form.

Thanks anyway.

Marco

____________________________________________________________

;T. Tanzillo
(defun vlisp-remove-if-not (key lst)
(mapcar 'cdr
(vl-remove-if-not
'(lambda (e) (eq (car e) key))
lst
)
)
)

; this one I post for fun only, in
; the category of obfuscated lisp,
; as it is recursive. Secretly posted
; for Frank and Robert who find
; recursion interesting.
;Michael Puckett
(defun CDRS2 (DxfKey ImpLst / TmpLst)
(if ImpLst
(if (setq TmpLst (assoc DxfKey ImpLst))
(cons (cdr TmpLst)
(CDRS2 DxfKey (cdr (member TmpLst ImpLst)) )
)
)
)
)

(defun ALE_MASSOC (DxfKey ImpLst / OutLst TmpLst)
(while (setq TmpLst (member (assoc DxfKey ImpLst) ImpLst))
(setq
ImpLst (cdr TmpLst)
OutLst (cons (cdar TmpLst) ImpLst)
)
)
(reverse OutLst)
)

(defun ALE_MASSOC4 (DxfKey ImpLst / OutLst TmpLst)
(while
(setq TmpLst
(vl-member-if '(lambda (x) (= (car x) DxfKey)) ImpLst)
)
(setq
ImpLst (cdr TmpLst)
OutLst (cons (cdar TmpLst) ImpLst)
)
)
(reverse OutLst)
)

;John Uhden
(defun @cv_dxflist (dxf in)
(mapcar
'cdr
(vl-remove-if
(function
(lambda (x)
(/= (car x) dxf)
)
)
in
)
)
)

;Jaysen Long
(defun massoc_J (key alist / nlist) ; ex / x nlist)
(foreach x alist
(if (eq key (car x))
(setq nlist (cons (cdr x) nlist))
)
)
(reverse nlist)
)

;Tony Tanzillo
(defun massoc_T (key alist /)
(apply 'append
(mapcar '(lambda (x)
(if (eq (car x) key)
(list (cdr x))))
alist))
)

;R. Bell
(defun rrbI:MAssoc (Key theList / valList)
(reverse
(progn
(while
(setq theList (member (assoc Key theList) theList))
(setq
valList (cons (cdar theList) valList)
theList (cdr theList)
)
)
valList
)
)
)

[Anonymous]

Marco:

I made a 9000+ vertex LWPOLYLINE, and tried using Ken Alexander's (pair-up)
function with (vlax-get object 'Coordinates), but Puckett's function with the
entity data was faster by about 29%.

Based on Ken's (cdxxx) approach, I tried the following which is about 33% faster
than Puckett's approach.
Ent is the entity data list for a LWPolyline only:
(defun LWCoords (Ent / N Coords)
(setq N (cdr (assoc 90 Ent))
Ent (member (assoc 10 Ent) Ent)
)
(repeat N
(setq Coords (cons (cdar Ent) Coords)
Ent (cddddr Ent)
)
)
(reverse Coords)
)

--
John Uhden, Cadlantic/formerly CADvantage
http://www.cadlantic.com
Sea Girt, NJ


"Marc'Antonio Alessi" wrote in message
news:5D5C4A543BBB0AF2AC1469B481114508@in.WebX.maYIadrTaRb...
> I have a collection of "massoc" but the fastest is:
>
> ;M. Puckett
> (defun cdrs (DxfKey ImpLst / TmpLst OutLst)
> (while (setq TmpLst (assoc DxfKey ImpLst))
> (setq OutLst (cons (cdr TmpLst) OutLst)
> ImpLst (cdr (member TmpLst ImpLst))
> )
> )
> (reverse OutLst)
> )
>
> and it works in <2000 also.
>
> I tried to have better performance using lambda but
> the result is "about" 1-3% less in big lists
> (3000-8000 vertex in lwpolyline data), also in
> normal compiled form.
>
> Thanks anyway.
>
> Marco
>
> ____________________________________________________________
>
> ;T. Tanzillo
> (defun vlisp-remove-if-not (key lst)
> (mapcar 'cdr
> (vl-remove-if-not
> '(lambda (e) (eq (car e) key))
> lst
> )
> )
> )
>
> ; this one I post for fun only, in
> ; the category of obfuscated lisp,
> ; as it is recursive. Secretly posted
> ; for Frank and Robert who find
> ; recursion interesting.
> ;Michael Puckett
> (defun CDRS2 (DxfKey ImpLst / TmpLst)
> (if ImpLst
> (if (setq TmpLst (assoc DxfKey ImpLst))
> (cons (cdr TmpLst)
> (CDRS2 DxfKey (cdr (member TmpLst ImpLst)) )
> )
> )
> )
> )
>
> (defun ALE_MASSOC (DxfKey ImpLst / OutLst TmpLst)
> (while (setq TmpLst (member (assoc DxfKey ImpLst) ImpLst))
> (setq
> ImpLst (cdr TmpLst)
> OutLst (cons (cdar TmpLst) ImpLst)
> )
> )
> (reverse OutLst)
> )
>
> (defun ALE_MASSOC4 (DxfKey ImpLst / OutLst TmpLst)
> (while
> (setq TmpLst
> (vl-member-if '(lambda (x) (= (car x) DxfKey)) ImpLst)
> )
> (setq
> ImpLst (cdr TmpLst)
> OutLst (cons (cdar TmpLst) ImpLst)
> )
> )
> (reverse OutLst)
> )
>
> ;John Uhden
> (defun @cv_dxflist (dxf in)
> (mapcar
> 'cdr
> (vl-remove-if
> (function
> (lambda (x)
> (/= (car x) dxf)
> )
> )
> in
> )
> )
> )
>
> ;Jaysen Long
> (defun massoc_J (key alist / nlist) ; ex / x nlist)
> (foreach x alist
> (if (eq key (car x))
> (setq nlist (cons (cdr x) nlist))
> )
> )
> (reverse nlist)
> )
>
> ;Tony Tanzillo
> (defun massoc_T (key alist /)
> (apply 'append
> (mapcar '(lambda (x)
> (if (eq (car x) key)
> (list (cdr x))))
> alist))
> )
>
> ;R. Bell
> (defun rrbI:MAssoc (Key theList / valList)
> (reverse
> (progn
> (while
> (setq theList (member (assoc Key theList) theList))
> (setq
> valList (cons (cdar theList) valList)
> theList (cdr theList)
> )
> )
> valList
> )
> )
> )

[Anonymous]

John,

now I remember and I have found some discussions, but:

1) I think CDRS (Puckett's) is reasonable fast in all
situations

2) What I was trying is to optimize that code
or find a new solution with some new "Visual" Lisp
funtions to work in any kind of lists or in Lwpolines
lists but with no restrictions.

Thank for your contribution.

Cheers.

Marco

_____________________________________________________________________

From: Tony Tanzillo
Date: Sep/30/99 - 11:44 (GMT)
Not really. The documentation you're quoting is fairly ancient.
In fact, most post-R12 objects (the ones with the (100 . AcDbXxxxx)
subclass data markers in them), are largely order-dependent,
as there is no other way to interpret them in cases where multiple
fields with the same group code appear. One thing is certain, and
that is the group 10 vertices of objects like LWPolylines are always
order dependent, and you could count on that remaining the same.
Unfortunately, the whole DXF-based entget/entmod and entmake way
of doing things is a total mess, woefull inadequate, and confusing.
The fact that ActiveX can work up to 10X faster than (entxxxx)
functions, and is far easier to work with, would make the decision
to switch to it in cases where it would work, is a no-brainer.

Phil Kenewell wrote:
>
> Eugene,
>
> That's not a good idea. Here is a quote from the "AutoCAD Customization
> Guide" to explain:
>
> Note: Do not write programs that rely on the order shown in these DXF code
> tables. Although these tables show the order of group codes as they
usually
> appear, the order can change under certain conditions or in a future
AutoCAD
> release. The code that controls an entity should be driven by a case
> (switch) or a table so that it can process each group correctly even if
the
> order is unexpected."
>
> It's better to extract the vertices out first - before you query them. In
> "special conditions" or future releases Autodesk may decide to change the
> order in which (entget) returns the Entity List.
> > -- > Phillip Kenewell

From: Bill Wilkerson
Date: Sep/07/01 - 05:40 (GMT)
They are in order of fastest from the top down.
I realize this is an old post, "but"....
Since you seem comfortable with using superlatives here,
you can just put the following at the *top* of your list:

(defun get-vertices (data / vlist points)
(setq vlist (member (assoc 10 data) data))
(repeat (cdr (assoc 90 data))
(setq points (cons (cdar vlist) points) vlist (cddddr vlist))
)
(reverse points)
)

;; Usage: ;; ;; (get-vertices (entget (car (entsel "\nPolyline: "))))
According to my data (lwpolys with 1000 vertices),
it is at least 2X faster than the (cdrs) function quoted above.
Reason: When you know how many items you must fetch from a list,
and you know their relative location, you shouldn't use search
functions (like assoc or member) to locate them. In the case of
an LWPolyline's data list, the number of vertices is stored in
the 90 group and the vertices appear at a constant frequency
(every 4th element). So, we those assumptions can avoid the
(ASSOC) nonsense altogether, and simply use (CDDDDR) to skip
to each subsequent vertex. While the (cdrs) function you posted
may be efficient for generic association lists where these kind
of assumptions cannot be made, for getting an lwpolyline's
vertices it isn't nearly the most efficient solution.
Regards, Bill



From: Tony Tanzillo
Date: Apr/11/02 - 21:14 (GMT)
You can safely assume that the structure of the
list returned by (entget) for LWPOLYLINES will
not change any time in the near future (at least,
not the part that contains the vertex data).

The reason why you can count on the list structure
not changing is because (entget) is just a programmatic
way of doing a DXFOUT on a single entity, and just as
the DXF format is not likely to change for existing
entities, the same holds true for (entget).

If the format did change, it would break much more
than just your code, it would create widespread
incompatibility and wreak havoc on anything that
worked with DXF files.

Trust me, with all things considered, this is a
perfectly reasonable assumption.

[Anonymous]

Below is an old post that contains a faster solution
for LWPOLYLINES only.

For other types of data, the performance of Michael's
CDRS (which is in fact, borrows the from my own as was
demonstrated here some time ago), is largely dependent
on the relative number of matching cars in the list
(verses the total number of items).

So, testing Michael's CDRS with LWPOLYINES is not really
a very intelligent evaluation to begin with, and does not
yield a valid charcterization of its true performance,
which can be vastly better than any other solution you
posted, depending on the factors mentioned above.

I'll see if I can dig up the original thread which
demonstrates why optimizing via (assoc) and (member)
can blow away any other solution depending on the
nature of the data involved, but in short, if you have
a very large list, but very few elements with matching
car's, then Michael's CDRS can be faster by an order
of magnitude.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Reply-To: "Tony Tanzillo" <(deleted)>
From: "Tony Tanzillo" <(deleted)>
Newsgroups: autodesk.autocad.customization
References: <3BF993C8.E2AC8F50@eweb.eugene.or.us>
<3BF9ADDE.B8603D90@eweb.eugene.or.us> <104A3798901DB902BA1C8E8E812E7418@in.WebX.maYIadrTaRb>
<408D3103EC221BD8F8C6DD78BF13ACC8@in.WebX.maYIadrTaRb> <8DEF8EB3FB05425324D7C69AB1D26DEA@in.WebX.maYIadrTaRb>
Subject: Re: Polyline Assoc 10
Date: Wed, 28 Nov 2001 23:49:12 -0500
Lines: 23
Organization: caddzone.com
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.50.4522.1200
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200

"Reinaldo Togores" wrote in message
news:8DEF8EB3FB05425324D7C69AB1D26DEA@in.WebX.maYIadrTaRb...
> Also tested several other solutions, and found Michael's the fastest one,
> but only in case it is not optimized on compilation!
> A slower one if not optimized was the fastest one once optimized & linked.
>
> These were some of the alternatives explored:

I think you'll find this faster than any of those
you've tried:

(defun GetVertexList (entlist / vertlist coords)
(setq vertlist (member (assoc 10 entlist) entlist))
(repeat (cdr (assoc 90 entlist))
(setq coords (cons (cdar vertlist) coords)
vertlist (cddddr vertlist)
)
)
(reverse coords)
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

"Marc'Antonio Alessi" wrote in message
news:C3FE740A13C3A9B9BE6B62149BB31688@in.WebX.maYIadrTaRb...
> I am trying of to get better performances to elaborate
> very big lists but I have not had resulted appreciable,
> where am I being wrong?
>
>
> ; Michael Puckett
> (defun cdrs (DxfKey ImpLst / TmpLst OutLst)
> (while (setq TmpLst (assoc DxfKey ImpLst))
> (setq OutLst (cons (cdr TmpLst) OutLst)
> ImpLst (cdr (member TmpLst ImpLst))
> )
> )
> (reverse OutLst)
> )
>
> (defun ALE_MASSOC2 (DxfKey ImpLst / OutLst)
> (
> (eval
> (function
> (lambda (x / TmpLst)
> (while (setq TmpLst (assoc DxfKey x))
> (setq OutLst (cons (cdr TmpLst) OutLst)
> x (cdr (member TmpLst x))
> )
> )
> )
> )
> )
> ImpLst
> )
> (reverse OutLst)
> )
>
> (defun ALE_MASSOC3 (DxfKey ImpLst / OutLst)
> (
> (lambda (x / TmpLst)
> (while (setq TmpLst (assoc DxfKey x))
> (setq OutLst (cons (cdr TmpLst) OutLst)
> x (cdr (member TmpLst x))
> )
> )
> )
> ImpLst
> )
> (reverse OutLst)
> )
>
> (defun ALE_MASSOC4 (DxfKey ImpLst / OutLst)
> (apply
> (function
> (lambda ( / TmpLst)
> (while (setq TmpLst (assoc DxfKey ImpLst))
> (setq OutLst (cons (cdr TmpLst) OutLst)
> ImpLst (cdr (member TmpLst ImpLst))
> )
> )
> )
> )
> nil
> )
> (reverse OutLst)
> )
>
> (defun ALE_MASSOC5 (DxfKey ImpLst / OutLst)
> (apply
> (function
> (lambda (x / TmpLst)
> (while (setq TmpLst (assoc DxfKey x))
> (setq OutLst (cons (cdr TmpLst) OutLst)
> x (cdr (member TmpLst x))
> )
> )
> )
> )
> (list ImpLst)
> )
> (reverse OutLst)
> )
>
> --
> ________________________________________________
>
> Marc'Antonio Alessi (TV) Italy - maalessi@tin.it
> (strcat "NOT a " (substr (ver) (if (= 15
> (atoi (getvar "acadver"))) 8 5) 4) " guru.")
>
> O.S. = XP Pro 2002 - Sp.1 - Ita
> AutoCAD = 2002 Ita - Sp.1
> _VERNUM = "K.0.44"
> ACADVER = "15.06s (LMS Tech)"
> (ver) = "Visual LISP 2000 (it)"
> ________________________________________________
>

[Anonymous]

"Tony Tanzillo" wrote in message
news:FC4AA1E515D6607AB3238EC0A91D4BC8@in.WebX.maYIadrTaRb...
>
> I'll see if I can dig up the original thread which
> demonstrates why optimizing via (assoc) and (member)
> can blow away any other solution depending on the
> nature of the data involved, but in short, if you have
> a very large list, but very few elements with matching
> car's, then Michael's CDRS can be faster by an order
> of magnitude.

And here is one of the posts from that thread (I'm not
sure if the balance is on Google, but maybe someone here
has it handy).

This is also where the (assoc)/(member) optimzation
technique used in Mr. Puckett's CDRS originates from:

-------------------------------------------------------------------------
X-Mozilla-Status: 8011
X-Mozilla-Status2: 00000000
Message-ID: <392D9F5F.996487E7@worldnet.att.net>
Date: Thu, 25 May 2000 17:47:11 -0400
From: Tony Tanzillo
Organization: Design Automation Consulting
X-Mailer: Mozilla 4.61 [en] (WinNT; U)
X-Accept-Language: en
MIME-Version: 1.0
Newsgroups: autodesk.autocad.customization
Subject: Re: Retrieving "LEADER" vertices
References: <392B5BF9.DE797031@worldnet.att.net> <392C9CC5.2DA38D0E@worldnet.att.net>
<392D8487.5C58B99A@worldnet.att.net>
Content-Type: multipart/mixed;
boundary="------------E4202702A176A0D533E94B58"

This is a multi-part message in MIME format.
--------------E4202702A176A0D533E94B58
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Michael Puckett wrote:
>
> I've run the tests exactly the way you say, and I do not observe
> foreach-cdrs's performance dropping below classic-cdrs.

I didn't say foreach-cdr's performance dropped, I said that
it was not a realistic test scenario to test the code in a
virgin editing session.

The results I posted suggests that classic-cdr's performance
improves in a dirty environment.

Never the less, the performance of the following VLISP only
solution will scale to the ratio between the number of list
elements extracted and the total input list length. In the
case of polyline vertex extracton, it's about the same, but
if you use it to get a relatively small number of elements
from a relatively large list, it can be an order of magnitude
faster than any of the other solutions.

(defun recursive-cdrs (key lst)
(recursive-cdrs-aux lst)
)

(defun recursive-cdrs-aux (lst / pair)
(cond
( (not lst) nil)
( (not (setq pair (assoc key lst))) nil)
(t (cons (cdr pair)
(recursive-cdrs-aux
(cdr (member pair lst))
)

)
)
)
)

Command: DENSE-DATA

List length: 1000

Input list length: 1000
Result list length: 250
Found/Total ratio: 0.25
Average of 10 x 50 iterations:
classic-cdrs: 0.3404
foreach-cdrs: 0.3156
remove-if-not: 0.2132
recursive-cdrs: 0.2354

Command:
Command: SPARSE-DATA

List length: 1000

Input list length: 1000
Result list length: 50
Found/Total ratio: 0.05
Average of 10 x 50 iterations:
classic-cdrs: 0.2975
foreach-cdrs: 0.2773
remove-if-not: 0.2034
recursive-cdrs: 0.0940

So, for VLISP only, the recursive solution (penned by my hand),
is the undisputed champ of cdrs.

--
/*********************************************************/
/* Tony Tanzillo Design Automation Consulting */
/* Programming & Customization for AutoCAD & Compatibles */
/* ----------------------------------------------------- */
/* tony.tanzillo@worldnet.att.net */
/* http://www.caddzone.com */
/*********************************************************/
--------------E4202702A176A0D533E94B58
Content-Type: text/plain; charset=us-ascii;
name="cdrs.lsp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="cdrs.lsp"

(defun classic-cdrs (key lst)
(apply 'append
(mapcar
'(lambda (x) (if (eq key (car x)) (list (cdr x))))
lst
)
)
)

(defun foreach-cdrs (key lst / rtn)
(reverse
(foreach x lst
(if (eq key (car x))
(setq rtn (cons (cdr x) rtn))
rtn
)
)
)
)

(defun vlisp-remove-if-not (key lst)
(mapcar 'cdr
(vl-remove-if-not
'(lambda (e) (eq (car e) key))
lst
)
)
)

(defun recursive-cdrs (key lst)
(recursive-cdrs-aux lst)
)

(defun recursive-cdrs-aux (lst / pair)
(cond
( (not lst) nil)
( (not (setq pair (assoc key lst))) nil)
(t (cons (cdr pair)
(recursive-cdrs-aux
(cdr (member pair lst))
)

)
)
)
)

;; (defun recursive-cdrs-aux (lst / pair)
;; (cond
;; ( (not lst) nil)
;; ( (setq pair (assoc key lst))) nil)
;; (t (cons (cdr pair)
;; (recursive-cdrs-aux
;; (cdr (member pair lst))
;; )
;;
;; )
;; )
;; )
;; )


;; Average a list of numbers after throwing
;; out highest and lowest values:

(defun refine-average (numlist)
(/ (- (apply '+ numlist)
(apply 'max numlist)
(apply 'min numlist)
)
(- (length numlist) 2)
)
)


;; Return time (in seconds) to evaluate quoted expression:
;;
;; (time '(myfunc arg))
;;

(defun time (expr)
(/ (abs (- (getvar "millisecs")
(progn (eval expr) (getvar "millisecs"))
)
)
1000.0
)
)


(defun C:TEST ( / time1 time2 time3 time4 iter *error* l f)
(defun *error* (s) (princ))
(if (not data)
(progn
(princ "\nUSE SPARSE-DATA, DENSE-DATA, OR PLINE-DATA to create test data")
(exit)
)
)
(setq time4 0.0 time3 0.0 time2 0.0 time1 0.0 iter 10)
(repeat iter
(setq time1 (+ time1 (time '(repeat 50 (classic-cdrs 10 data)))))
(setq time2 (+ time2 (time '(repeat 50 (foreach-cdrs 10 data)))))
(setq time3 (+ time3 (time '(repeat 50 (vlisp-remove-if-not 10 data)))))
(setq time4 (+ time4 (time '(repeat 50 (recursive-cdrs 10 data)))))
)
(princ
(strcat
"\nInput list length: " (itoa (setq l (length data)))
"\nResult list length: " (itoa (setq f (length (classic-cdrs 10 data))))
"\nFound/Total ratio: " (rtos (/ (float f) l) 2 2)
)
)

(princ
(strcat "\nAverage of 10 x 50 iterations: "
"\nclassic-cdrs: " (rtos (/ time1 iter) 2 4)
"\nforeach-cdrs: " (rtos (/ time2 iter) 2 4)
"\nremove-if-not: " (rtos (/ time3 iter) 2 4)
"\nrecursive-cdrs: " (rtos (/ time4 iter) 2 4)
)
)
(princ)
)

(defun C:SPARSE-DATA ( / size)
(setq size (getint "\nList length: "))
(setq data nil)
(repeat (/ size 20)
(setq data
(append data
'(
(10 0.0 0.0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
(0 . 0)
)
)
)
)
(c:test)
(princ)
)

(defun C:DENSE-DATA ( / size)
(setq size (getint "\nList length: "))
(setq data nil)
(repeat (/ size 4)
(setq data
(append data
'(
(10 0.0 0.0)
(0 . 0)
(0 . 0)
(0 . 0)
)
)
)
)
(c:test)
(princ)
)

(defun C:PLINE-DATA ( / vertices point )
(setq vertices (getint "\nNumber of vertices: "))
(setq point '(0.0 0.0 0.0))
(setvar "CMDECHO" 0)
(command "._pline" point) ;; plinetype > 0
(repeat (1- vertices)
(command (setq point (polar point 0.0 1.0)))
)
(command "")
(setq data (entget (entlast)))
(c:test)
)




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

[Anonymous]

Tony,

thanks for your contribution always complete, precise and accurate
but... after using yours test functions I think my choice, for
multipurpose use, is the lambda form of cdrs:

(defun ALE_MASSOC4 (DxfKey ImpLst / OutLst)
(apply
(function
(lambda ( / TmpLst)
(while (setq TmpLst (assoc DxfKey ImpLst))
(setq
OutLst (cons (cdr TmpLst) OutLst)
ImpLst (cdr (member TmpLst ImpLst))
)
)
)
)
nil
)
(reverse OutLst)
)

Cheers.

Marco


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Comando: sparse-data

List length: 10000

Input list length: 10000
Result list length: 500
Found/Total ratio: 0.05
Average of 10 x 50 iterations:
CDRS2 : 0.3496
cdrs : 0.3514
remove-if-not : 0.653
recursive-cdrs: 0.3695
ALE_MASSOC2 : 0.3455
ALE_MASSOC3 : 0.3425
ALE_MASSOC4 : 0.3375 <<<
ALE_MASSOC5 : 0.3465

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Comando: dense-data

List length: 10000

Input list length: 10000
Result list length: 2500
Found/Total ratio: 0.25
Average of 10 x 50 iterations:
CDRS2 : 0.6439
cdrs : 0.605
remove-if-not : 0.706
recursive-cdrs: 0.726
ALE_MASSOC2 : 0.6049 <<<
ALE_MASSOC3 : 0.6068
ALE_MASSOC4 : 0.609
ALE_MASSOC5 : 0.6088

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Comando: pline-data

Number of vertices: 10000

Input list length: 40015
Result list length: 10000
Found/Total ratio: 0.25
Average of 10 x 50 iterations:
CDRS2 : 2.6009
cdrs : 2.5013
remove-if-not : 2.9204
recursive-cdrs: 2.9274
ALE_MASSOC2 : 2.4813 <<
ALE_MASSOC3 : 2.4867
ALE_MASSOC4 : 2.5015
ALE_MASSOC5 : 2.4905
GetVertexList : 1.397 <<<

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

*******************************
COMPILED VERSIONS:
*******************************
Comando: (GC)
nil
Comando: dense-data

List length: 10000

Input list length: 10000
Result list length: 2500
Found/Total ratio: 0.25
Average of 10 x 50 iterations:
CDRS2 : 0.5248
cdrs : 0.4556
remove-if-not : 0.7051
recursive-cdrs: 0.5297
ALE_MASSOC2 : 0.4587
ALE_MASSOC3 : 0.4586
ALE_MASSOC4 : 0.4527 <<<
ALE_MASSOC5 : 0.4597

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Comando: (GC)
nil
Comando: sparse-data

List length: 10000

Input list length: 10000
Result list length: 500
Found/Total ratio: 0.05
Average of 10 x 50 iterations:
CDRS2 : 0.3184
cdrs : 0.3125
remove-if-not : 0.6659
recursive-cdrs: 0.3205
ALE_MASSOC2 : 0.3094
ALE_MASSOC3 : 0.3095
ALE_MASSOC4 : 0.3084 <<
ALE_MASSOC5 : 0.3075 <<<


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Comando: (GC)
nil
Comando: pline-data

Input list length: 40015
Result list length: 10000
Found/Total ratio: 0.25
Average of 10 x 50 iterations:
CDRS2 : 2.142
cdrs : 1.887 <<<
remove-if-not : 2.921
recursive-cdrs: 2.168
ALE_MASSOC2 : 1.924
ALE_MASSOC3 : 1.92
ALE_MASSOC4 : 1.9049 <
ALE_MASSOC5 : 1.9211
GetVertexList : 0.613

[Anonymous]

Marco,
Using (apply(function(lambda on an empty list seems useless to me.
It certainly makes the whole thing less readable and I would be
very surprised if it was any faster. What is wrong with? Or just use
Michael's version which is identical to it except for variable names.

(defun ALE_MASSOC4 (DxfKey ImpLst / OutLst tmplist)
(while (setq TmpLst (assoc DxfKey ImpLst))
(setq
OutLst (cons (cdr TmpLst) OutLst)
ImpLst (cdr (member TmpLst ImpLst))
)
)
(reverse OutLst)

)

Regards,
Doug


"Marc'Antonio Alessi" wrote in message
news:2CB9154FDBC98E1D1312055EFF17F296@in.WebX.maYIadrTaRb...
> Tony,
>
> thanks for your contribution always complete, precise and accurate
> but... after using yours test functions I think my choice, for
> multipurpose use, is the lambda form of cdrs:
>
> (defun ALE_MASSOC4 (DxfKey ImpLst / OutLst)
> (apply
> (function
> (lambda ( / TmpLst)
> (while (setq TmpLst (assoc DxfKey ImpLst))
> (setq
> OutLst (cons (cdr TmpLst) OutLst)
> ImpLst (cdr (member TmpLst ImpLst))
> )
> )
> )
> )
> nil
> )
> (reverse OutLst)
> )
>
> Cheers.
>
> Marco
>
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> Comando: sparse-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 500
> Found/Total ratio: 0.05
> Average of 10 x 50 iterations:
> CDRS2 : 0.3496
> cdrs : 0.3514
> remove-if-not : 0.653
> recursive-cdrs: 0.3695
> ALE_MASSOC2 : 0.3455
> ALE_MASSOC3 : 0.3425
> ALE_MASSOC4 : 0.3375 <<<
> ALE_MASSOC5 : 0.3465
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> Comando: dense-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 2500
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 0.6439
> cdrs : 0.605
> remove-if-not : 0.706
> recursive-cdrs: 0.726
> ALE_MASSOC2 : 0.6049 <<<
> ALE_MASSOC3 : 0.6068
> ALE_MASSOC4 : 0.609
> ALE_MASSOC5 : 0.6088
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> Comando: pline-data
>
> Number of vertices: 10000
>
> Input list length: 40015
> Result list length: 10000
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 2.6009
> cdrs : 2.5013
> remove-if-not : 2.9204
> recursive-cdrs: 2.9274
> ALE_MASSOC2 : 2.4813 <<
> ALE_MASSOC3 : 2.4867
> ALE_MASSOC4 : 2.5015
> ALE_MASSOC5 : 2.4905
> GetVertexList : 1.397 <<<
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> *******************************
> COMPILED VERSIONS:
> *******************************
> Comando: (GC)
> nil
> Comando: dense-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 2500
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 0.5248
> cdrs : 0.4556
> remove-if-not : 0.7051
> recursive-cdrs: 0.5297
> ALE_MASSOC2 : 0.4587
> ALE_MASSOC3 : 0.4586
> ALE_MASSOC4 : 0.4527 <<<
> ALE_MASSOC5 : 0.4597
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> Comando: (GC)
> nil
> Comando: sparse-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 500
> Found/Total ratio: 0.05
> Average of 10 x 50 iterations:
> CDRS2 : 0.3184
> cdrs : 0.3125
> remove-if-not : 0.6659
> recursive-cdrs: 0.3205
> ALE_MASSOC2 : 0.3094
> ALE_MASSOC3 : 0.3095
> ALE_MASSOC4 : 0.3084 <<
> ALE_MASSOC5 : 0.3075 <<<
>
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> Comando: (GC)
> nil
> Comando: pline-data
>
> Input list length: 40015
> Result list length: 10000
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 2.142
> cdrs : 1.887 <<<
> remove-if-not : 2.921
> recursive-cdrs: 2.168
> ALE_MASSOC2 : 1.924
> ALE_MASSOC3 : 1.92
> ALE_MASSOC4 : 1.9049 <
> ALE_MASSOC5 : 1.9211
> GetVertexList : 0.613

[Anonymous]

That's fine, but I fail to see the point to wrapping
it in a (lambda) and applying it.

This is really all that's needed:

(defun cdrs (key lst / result pair)
(while (setq pair (assoc key lst))
(setq result (cons (cdr pair) result)
lst (cdr (member pair lst))
)
)
(reverse result)
)


"Marc'Antonio Alessi" wrote in message
news:2CB9154FDBC98E1D1312055EFF17F296@in.WebX.maYIadrTaRb...
> Tony,
>
> thanks for your contribution always complete, precise and accurate
> but... after using yours test functions I think my choice, for
> multipurpose use, is the lambda form of cdrs:
>
> (defun ALE_MASSOC4 (DxfKey ImpLst / OutLst)
> (apply
> (function
> (lambda ( / TmpLst)
> (while (setq TmpLst (assoc DxfKey ImpLst))
> (setq
> OutLst (cons (cdr TmpLst) OutLst)
> ImpLst (cdr (member TmpLst ImpLst))
> )
> )
> )
> )
> nil
> )
> (reverse OutLst)
> )
>
> Cheers.
>
> Marco
>
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> Comando: sparse-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 500
> Found/Total ratio: 0.05
> Average of 10 x 50 iterations:
> CDRS2 : 0.3496
> cdrs : 0.3514
> remove-if-not : 0.653
> recursive-cdrs: 0.3695
> ALE_MASSOC2 : 0.3455
> ALE_MASSOC3 : 0.3425
> ALE_MASSOC4 : 0.3375 <<<
> ALE_MASSOC5 : 0.3465
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> Comando: dense-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 2500
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 0.6439
> cdrs : 0.605
> remove-if-not : 0.706
> recursive-cdrs: 0.726
> ALE_MASSOC2 : 0.6049 <<<
> ALE_MASSOC3 : 0.6068
> ALE_MASSOC4 : 0.609
> ALE_MASSOC5 : 0.6088
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> Comando: pline-data
>
> Number of vertices: 10000
>
> Input list length: 40015
> Result list length: 10000
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 2.6009
> cdrs : 2.5013
> remove-if-not : 2.9204
> recursive-cdrs: 2.9274
> ALE_MASSOC2 : 2.4813 <<
> ALE_MASSOC3 : 2.4867
> ALE_MASSOC4 : 2.5015
> ALE_MASSOC5 : 2.4905
> GetVertexList : 1.397 <<<
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> *******************************
> COMPILED VERSIONS:
> *******************************
> Comando: (GC)
> nil
> Comando: dense-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 2500
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 0.5248
> cdrs : 0.4556
> remove-if-not : 0.7051
> recursive-cdrs: 0.5297
> ALE_MASSOC2 : 0.4587
> ALE_MASSOC3 : 0.4586
> ALE_MASSOC4 : 0.4527 <<<
> ALE_MASSOC5 : 0.4597
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> Comando: (GC)
> nil
> Comando: sparse-data
>
> List length: 10000
>
> Input list length: 10000
> Result list length: 500
> Found/Total ratio: 0.05
> Average of 10 x 50 iterations:
> CDRS2 : 0.3184
> cdrs : 0.3125
> remove-if-not : 0.6659
> recursive-cdrs: 0.3205
> ALE_MASSOC2 : 0.3094
> ALE_MASSOC3 : 0.3095
> ALE_MASSOC4 : 0.3084 <<
> ALE_MASSOC5 : 0.3075 <<<
>
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> Comando: (GC)
> nil
> Comando: pline-data
>
> Input list length: 40015
> Result list length: 10000
> Found/Total ratio: 0.25
> Average of 10 x 50 iterations:
> CDRS2 : 2.142
> cdrs : 1.887 <<<
> remove-if-not : 2.921
> recursive-cdrs: 2.168
> ALE_MASSOC2 : 1.924
> ALE_MASSOC3 : 1.92
> ALE_MASSOC4 : 1.9049 <
> ALE_MASSOC5 : 1.9211
> GetVertexList : 0.613

[Anonymous]

> Using (apply(function(lambda on an empty list seems useless to me.
> It certainly makes the whole thing less readable and I would be
> very surprised if it was any faster. What is wrong with?

I was searching to manage the "TmpLst" local value internally in lambda
expression (maybe it come from a my mental mast########).


> Or just use
> Michael's version which is identical to it except for variable names.

it is Michael's version!

---

Thanks and have a god weekend.

Marco

[Anonymous]

Tony,
Are we on the same wavelength this AM?

"Tony Tanzillo" wrote in message
news:6E08B94E822DA3DB22D6F54106B34061@in.WebX.maYIadrTaRb...
> That's fine, but I fail to see the point to wrapping
> it in a (lambda) and applying it.
>
> This is really all that's needed:
>

[Anonymous]

Here is an illustration of why WHILE MEMBER ASSOC CAR CDR method is much
faster in a "dirty" list.

Given the list:
(setq lst (list (cons "no" 1)(cons "dirt" 1)(cons "yes" 1)(cons "no" 2)(cons
"dirt" 2)(cons "yes" 2)(cons "no" 3)(cons "dirt" 3)(cons "yes" 3)(cons "no"
4)(cons "dirt" 4)(cons "no" 5)(cons "dirt" 5)))

The FOREACH method
(foreach itm lst
(if (eq itm "yes")
(setq rtn (cons (cdr itm) rtn))
)
)


the function must process three pieces of data before it finds a match to
put in its return list.

Similar is true for the VL-REMOVE-IF-NOT method.
(mapcar 'cdr
(vl-remove-if-not
'(lambda (e) (eq (car e) key))
lst
)
)

In both cases of the above cases every piece of data is processed. Not so
for the WHILE method.
(while (setq tmp (assoc "yes" lst))
(setq rtn (cons (cdr tmp) rtn)
lst (cdr (member tmp lst))
)
)

In the case of the above given list, the first two and the last four pieces
(actually any non-matching piece of data) do not fit the ASSOC key and
therefore not processed. WHILE MEMBER ASSOC CAR and CDR are extremely well
suited for this operation.

My explanation here is probably over-simplified, but I don't know how to
explain the nuts and bolts in any greater detail than this.
--

Regards,
Eric S.
A2k/W2k

[Anonymous]

CDRS was the fruit of a long tread (33 posts) where you and I jousted back and
forth with successively more efficient versions of a "cdrs" type function. The
post you quote was the the 20th post in said thread. In the 19th I had posted:



If you review the data you had posted, it indicated foreach-cdrs performance
had dropped below
classic's, thus my response.

Re: recursive-cdrs, That's impressive performance, *and* surprising, as there
is often a performance
penalty with recursive routines (as we've seen before).


Nice one, But undisputed? I don't think so:


Being a fan of recursion when applicable, I penned the following by removing
superfluous tests and
the wrapper approach from recursive-cdrs:


(defun recursesive-cdrs-mp (key lst / pair)
(if (setq pair (assoc key lst))
(cons (cdr pair)
(recursesive-cdrs-mp key (cdr (member pair lst)))
)
)
)


It is faster than recursive-cdrs as one would anticipate (fewer tests), though
not astonishingly so.


But ... It is important to note that neither of these recursive routines
should be used in the
*real* world, as they will blow the stack rather easily (on my PC lists with >
150 pairs of '(10 x y
z) for example). So while a fun and illuminating academic exercise, they
should not be used.


As for undisputed, the following function is not recursive, is stable, is
useable in 14 and A2K, and
bonus - is the current reigning champion.


(defun while-cdrs (key lst / pair rtn)
(reverse
(while (setq pair (assoc key lst))
(setq
rtn (cons (cdr pair) rtn)
lst (cdr (member pair lst))
)
rtn
)
)
)



To summarize, the core algorythm in CDRS as I had penned, and later distilled
to

(defun cdrs ( key lst / pair result )
(while (setq pair (assoc key lst))
(setq result (cons (cdr pair) result)
lst (cdr (member pair lst))
)
)
(reverse result)
)

was developed within the context of the dialog we had participated in, and
derived from

(defun recursive-cdrs (key lst)
(recursive-cdrs-aux lst)
)

(defun recursive-cdrs-aux (lst / pair)
(cond
( (not lst) nil)
( (not (setq pair (assoc key lst))) nil)
(t (cons (cdr pair)
(recursive-cdrs-aux
(cdr (member pair lst))
)

)
)
)
)

If anyone wishes to view the entire thread I have it all in a zip file; just
let me know.

Regards,

Michael.

"Tony Tanzillo" wrote in message
news:96BC74263870B62663BD0050D2B1B7CB@in.WebX.maYIadrTaRb...

"Tony Tanzillo" wrote in message
news:FC4AA1E515D6607AB3238EC0A91D4BC8@in.WebX.maYIadrTaRb...
>
> I'll see if I can dig up the original thread which
> demonstrates why optimizing via (assoc) and (member)
> can blow away any other solution depending on the
> nature of the data involved, but in short, if you have
> a very large list, but very few elements with matching
> car's, then Michael's CDRS can be faster by an order
> of magnitude.

And here is one of the posts from that thread (I'm not
sure if the balance is on Google, but maybe someone here
has it handy).

[Anonymous]

Truly a gem.

> (defun cdrs ( key lst / pair result )
> (while (setq pair (assoc key lst))
> (setq result (cons (cdr pair) result)
> lst (cdr (member pair lst))
> )
> )
> (reverse result)
> )

--

Regards,
Eric S.
A2k/W2k