Fastest way to merge two lists without duplicates

procedure(CCFmergedLists(@rest lists)
  let(((uniq makeTable('uniq)))
    foreach(mapcan lst lists
        setof(elem lst
          !boundp(uniq[elem]) && (uniq[elem]=t)
        )
    )
  )
)

I think that should be pretty fast, It's based on an older post I made to uniquify a list. This makes some attempt to preserve the order. I've also made it accept any number of lists.

Regards,

Andrew.

Don't do it this way:

> artUnique(append('(a b c) '(a d c)))
(a b c d)

artUnique is private.

If order doesn't matter, you can probably do it even faster than Andrew's:

> list1 = '(a b c)
(a b c)
> list2 = '(a d c)
(a d c)
> myTable = makeTable("temp" nil)
table:temp
> foreach(element (append list1 list2) myTable[element] = t)
(a b c a d
    c
)
> myTable->?
(b c a d)

Here is a solution that uses the public function ciUniqueMembers:

> mapcar('car
         ciUniqueMembers(foreach(mapcan list (list list1 list2)
                             mapcar('ncons list))))
(a b c d)

Andrew Beckett said:

I think that should be pretty fast

Would it be a tiny bit faster to do makeTable('unique t) and then make the test (uniq[elem] && uniq[elem]=nil)?  It would save you a call to "null" and "boundp" in the setof....  Also, I wonder which is faster:

and(p q)

if(p q)

when(p q)

cond((p q))

Here's a solution optimized for small positive integers:

procedure(merge_small_positive_integer_lists(@rest lists)
    let(
        (
            (vector makeVector(1024 nil))
            result
        )
        foreach(list lists
            foreach(element list
                vector[element] = t
            )
        )
        for(i 0 sub1(length(vector))
            when(vector[i]
                push(i result)
            )
        )
        result
    )
)

> merge_small_positive_integer_lists('(3 34 63 532 234 23 43) '(3 1 4 1 5 9 2 6 7 3))
(532 234 63 43 34
    23 9 7 6 5
    4 3 2 1
)

You could do a similar thing with characters, storing them in a sparse vector of their ASCII codes.

I did some profiling with a list of 1 million integers (passed twice to the function). Here's the findings (on my laptop, so not the absolutely fastest machine around):

1. My CCFmergedLists implementation: 1.85s
2. artUnique solution: gave up after 170s (so very slow)
3. ciUniqueMembers solution - only works with strings and has to do some list creation to get into the right format. With a list of a million strings passed twice via append, took 9.6s (uses sortcar inside)
4. Tom's unordered approach which uses a table: 0.84s
5. An improvement upon this which uses a foreach loop rather than using append:
   procedure(CCFmergedLists3(@rest lists)
   let((myTable)
       myTable = makeTable("temp" nil)
       foreach(lst lists
       foreach(element lst myTable[element] = t)
       )
       myTable->?
   ))
   This took 0.66s
6. The optimized for small integers (I increased the array size to over 1million to profile it with reasonable data): 0.95s
7. Tom's refinement of my ordered solution which uses a table which returns t by default (won't work directly as using uniq[elem]=nil as the second arg to && will always return nil. So I used prog1 instead:
     procedure(CCFmergedLists4(@rest lists)
     let(((uniq makeTable('uniq t)))
       foreach(mapcan lst lists
           setof(elem lst
             prog1(uniq[elem] uniq[elem]=nil)
           )
       )
     )
   )
   This took 1.45s

So the winners are:

Ordered: 7 in the above list (CCFmergedLists4) - 1.45s
Unordered: 5 in the above list (CCFmergedLists3) - 0.66s

For two million entry lists, which is probably far bigger than you'd ever use this for, these should be good enough (as was my original solution - the others are not massively faster). Maybe small optimizations here and there could be made, Also your mileage may vary with different input data for profiling...

Regards,

Andrew.

I know it's an old thread, but I wanted to say "Thank you!" Andrew for taking the time to profile all these.  The results are quite interesting!

when and and constructs seem to be the fastest, beating others by about 10%:

measureTime (for i 0 100000000 (if 1 2))
(2.041689 0.0 2.070708 0)
measureTime (for i 0 100000000 (if nil 2))
(1.885713 0.0 1.885655 0)
measureTime (for i 0 100000000 (when 1 2))
(1.838721 0.0 1.838768 0)
measureTime (for i 0 100000000 (when nil 2))
(1.666747 0.0 1.666091 0)
measureTime (for i 0 100000000 (and 1 2))
(1.84172 0.0 1.8418 0)
measureTime (for i 0 100000000 (and nil 2))
(1.670746 0.0 1.671489 0)
measureTime (for i 0 100000000 (cond (1 2)))
(2.03869 0.0 2.036863 0)
measureTime (for i 0 100000000 (cond (nil 2)))
(1.928706 0.0 1.92704 0)

Dushyant