compare lists

Discussion in 'AutoCAD' started by mark, Jun 14, 2004.

  1. mark

    mark Guest

    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
     
    mark, Jun 14, 2004
    #1
  2. mark

    Jeff Mishler Guest

    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
     
    Jeff Mishler, Jun 14, 2004
    #2
  3. mark

    mark Guest

    not bad at all,
    thanks

     
    mark, Jun 14, 2004
    #3
  4. mark

    Rudy Tovar Guest

    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
     
    Rudy Tovar, Jun 14, 2004
    #4
  5. 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
     
    Tony Tanzillo, Jun 14, 2004
    #5
  6. How about:

    (defun subsetp (list-1 list-2)
    (vl-every
    (function (lambda (x) (member x list-2)))
    list-1))
     
    Martti Halminen, Jun 15, 2004
    #6
  7. mark

    John Uhden Guest

    Very good. (vl-position) instead of (member) would speed it up a lot.
     
    John Uhden, Jun 15, 2004
    #7
  8. 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.

    --
     
    Martti Halminen, Jun 16, 2004
    #8
  9. mark

    John Uhden Guest

    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).
     
    John Uhden, Jun 17, 2004
    #9
  10. 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.

    --
     
    Martti Halminen, Jun 17, 2004
    #10
  11. Gracias Tony


     
    José Luis Garcia Galán, Jun 17, 2004
    #11
  12. mark

    John Uhden Guest

    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?
     
    John Uhden, Jun 18, 2004
    #12
  13. 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
     
    Tony Tanzillo, Jun 18, 2004
    #13
  14. mark

    John Uhden Guest

    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.
     
    John Uhden, Jun 18, 2004
    #14
  15. 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.")

    --
     
    Marc'Antonio Alessi, Jun 18, 2004
    #15
  16. mark

    cesi2d Guest

    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
     
    cesi2d, Jun 18, 2004
    #16
  17. 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)))

    --
     
    Martti Halminen, Jun 21, 2004
    #17
  18. 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
     
    Tony Tanzillo, Jun 22, 2004
    #18
Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.