compare lists

hi,

what is the best way to figure out
if all atoms in a list 1 are present in list 2,
i do not want to do a foreach and member,
i am looking for a more civilized solution

e.g.
list1 = ( "a" B" "c")
list 2 = ("a" "c" "e" "F" "X")

TIA
mark

 

This still uses member, but does verify whether ALL elements of one list are
present in another. Order doesn't matter.

(defun list-in-list (list1 list2)
(if (member nil (mapcar '(lambda (x)
(member x list2))
list1))
nil
t
)
)

Jeff

 

not bad at all,
thanks

 

Civilized? Why not just say an easier method you can understand.

The question we must ask yourself is now the list is being generated, or how
what you want to do with the remaining solutions. (T NIL T NIL NIL ETC.)

Or can you filter while in the creation of said list. (if (not (member a
b))(do_this_or_that))

Endless possibilities with several conclusions.
--

AUTODESK
Authorized Developer
http://www.Cadentity.com
MASi

 

i do not want to do a foreach and member,

Mapcar and Foreach are inappropriate here, if you
only want to know if at least one element in the
first list is not present in the second (making
testing of any remaining items in the first list,
needless).

Here is one way:

(defun all-members (source target)
(cond
( (not (and source target)) nil)
( (equal source target))
(t (while (member (car source) target)
(setq source (cdr source))
)
(not source)
)
)
)



AutoCAD based Security Planning Solutions:
http://www.caddzone.com/securityplanning

 

How about:

(defun subsetp (list-1 list-2)
(vl-every
(function (lambda (x) (member x list-2)))
list-1))

 

Very good. (vl-position) instead of (member) would speed it up a lot.

 

This sounds odd, as MEMBER should be doing less work than VL-POSITION.
Do you have actual measurements for this? This would imply that MEMBER
is implemented rather incompetently.

--

 

It's not really odd. The R14 VisualLisp (nee Vital Lisp) equivalent was slower,
but in R15+ it seems logical that a return of an integer vs. a list (of unknown
length and contents) would be faster. No incompetency implied; it's just a
matter of what you need the function to return. In this case, nil vs. T is
ample. IMHO, nil vs. 'INT is the next closest thing.

There are plenty of benchmark functions around to test the theorem. In any
case, unless you need to further evaluate the (member) list, I think you'll find
that (vl-position) is the fastest means of checking the existence of any item in
a list (absence vs. one or more).

Of course, if the list is short, or if the function is called infrequently, then
it really matters not. My comment was posted in the context of reviewing one of
my older pieces of software. I was able to speed it up in the neighborhood of
100x simply by (vl-remove-if)ing impossible conditions and replacing old
(member)s with (vl-position)s. Bear in mind that the comparison list was about
10,000 items of 6 items each. On the average, I've found that (vl-position) is
about 10x faster than (member).

 

Given that in any sensible Lisp implementation returning a list only
means returning a pointer to the first cons cell of the list, it fits in
a single machine word, so it should only take exactly the same time and
space as an integer (unless you print the result), so I still don't see
what should make it any slower.

Oh well, I played with this a little. Using 10000 6-element lists on a
simple benchmark, VL-POSITION took 10 seconds, MEMBER took 20 seconds,
all compiled with "safe" settings. Writing my own MEMBER wasn't
competitive, took about 70 seconds.

For comparision, the same functions on Allegro Common Lisp took 2.6 s,
2.8 s and 2.8 seconds, respectively, so VisualLisp definitely isn't a
very well-performing Lisp implementation.

--

 

Gracias Tony

 

Pointers and foos notwithstanding, please help me understand the following
empirical data:

Given:
(defun timer (fun n / start stop)
(setq start (getvar "date"))
(repeat n (eval fun))
(setq stop (getvar "date"))
(princ (strcat "Elapsed time for " (itoa n) " iterations: " (rtos (* 86400.0
(- stop start)) 2 2) " secs.\n"))
(princ)
)

Try the following:
Command: (setq a nil i 0)(repeat 10000 (setq a (cons i a) i (1+ i)))(princ)

Command: (timer '(member 5000 a) 10000)
Elapsed time for 10000 iterations: 32.14 secs.

Command: (timer '(vl-position 5000 a) 10000)
Elapsed time for 10000 iterations: 4.01 secs.

Of course this is using 2002 on a PIII/1.2GHz/384Mb laptop.

I picked 5000 'cause it's in the middle of the list. My apologies for
exaggerating; the factor appears to be maximum 8X, not 10X. Results vary with
the position of the item in the list. So what am I doing wrong?

 

I wasn't disputing the fact that vl-position is
faster than member.

What I was disputing, was the presumed reason why
that is so.

There's no question that vl-position has some
kind of optimization, but the reason it is faster
than member has nothing to do with the fact that
member returns a list.




AutoCAD based Security Planning Solutions:
http://www.caddzone.com/securityplanning

 

Thanks for the confirmation. Yeah, maybe I'm all wet, and maybe Peter Petrov is
just an optimization kinda guy. Maybe he didn't optimize it at all. Hey...
220, 221, whatever it takes.

 

Results vary with the position of the item in the list.

....and the kind of the lists:

(defun Test_vl-position (InLst)
(foreach ForElm InLst (vl-position ForElm InLst))
)

(defun Test_member (InLst)
(foreach ForElm InLst (member ForElm InLst))
)

(setq alist1 (atoms-family 1))
(setq alist1 (append alist1 alist1 alist1 alist1))

(length alist1) > 3076

TEST_VL-POSITION > 100 iterations: 3.7 secs.
TEST_MEMBER > 100 iterations: 23.47 secs.

(setq alist1 nil) (setq alist '(1 2 3 4 4 5 5 5 6 7 8 9 9 9 9))
(setq alist1 (repeat 205 (setq alist1 (append alist1 alist))))

(length alist1) > 3075

TEST_VL-POSITION > 100 iterations: 0.28 secs.
TEST_MEMBER > 100 iterations: 0.64 secs.

---------------------------------------------------------------

Practical applications:

; removes all the duplicated elements leaving originals,
; faster on lists with low number of duplicates
; example:
; (setq alist2 (atoms-family 1))
; (setq alist2 (append alist2 alist2 alist2 alist2))
;
(defun ALE_RemoveDupOnLst (InLst / OutLst)
(reverse
(foreach ForElm InLst
(if (vl-position ForElm OutLst)
OutLst
(setq OutLst (cons ForElm OutLst))
)
)
)
)
;
; removes all the duplicated elements leaving originals,
; faster on lists with high number of duplicates
; example:
; (setq alst2 nil) (setq alist '(1 2 3 4 4 5 5 5 6 7 8 9 9 9 9))
; (setq alist2 (repeat 500 (setq alist2 (append alist2 alist))))
;
(defun ALE_RemoveDupOnLst2 (InLst / OutLst CarElm)
(while InLst
(setq
InLst (vl-remove (setq CarElm (car InLst)) (cdr InLst))
OutLst (cons CarElm OutLst)
)
)
(reverse OutLst)
)
;
; removes all the duplicated elements leaving originals,
; for R14
;
(defun ALE_RemoveDupOnLst14 (InLst / OutLst)
(reverse
(foreach ForElm InLst
(if (member ForElm OutLst)
OutLst
(setq OutLst (cons ForElm OutLst))
)
)
)
)

--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

thanks Tony,

If I understand your explanations

(setq A (list 1 2 3))
(setq B (cons 0 A)) ; here no creation
(setq C (cons -1 A)) ; no creation
(setq A (list "a" "b")) ; here creation , but the B and C lists remain
intact , so
the A and B and C list are created
or the A list is created and a fictive list (the old a) remain in memory ,
for all the time while an element point to it
or I don't know

Can you confirm the right explanation please ?

If you have other like information , it is very interresting for big
software writing.

Thanks

 

To clarify (or obfuscate...) this, in Lisp there actually doesn't exist
a low level data type called list! They are just groups of cons cells:
if the cdr field contains an atom, you've got a dotted pair, if it
contains a pointer to another cons cell or nil, you've got a list.

So, the low-level primitive doing memory allocation is the CONS
function. What (list 1 2 3) does is exactly the same as
(cons 1 (cons 2 (cons 3 nil)))

--

 

To put it more formally, if the CDR of the last cons cell
in a chain (e.g. 'list') points to anything other than NIL
or another cons cell, what you have is a dotted list.

A dotted pair is by coincidence, a dotted list that consists
of two elements in one cons cell.

(a b c . d)

The above list uses 3 cons cells. The last cell's CAR is the
symbol C and its CDR is the symbol D.



AutoCAD based Security Planning Solutions:
http://www.caddzone.com/securityplanning