Fastest way to merge two lists without duplicates

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 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.