how to remove repeat element in a list

Jim,

The downside of this implementation is that it is O(n^2) and whilst the list is in order, it's in the order of the last occurrence rather than first occurrence of a repeated value.

An ordered version which is a bit cleaner than Derek's and avoids a reverse is:

 procedure(CCFuniqueInOrder(lst)
  let(((uniq makeTable('uniq)))
    setof(elem lst
    !boundp(uniq[elem]) && (uniq[elem]=t)
    )
  )
)

This is making the assumption that 'unbound is not in the list (which is probably a reasonable assumption in most scenarios).

For a list with 1000000 random integers with values up to 10000,  this took 0.65s (on my laptop running on battery only), whereas I gave up with yours. Running with a list 10 times shorter took 29s, so I'd reasonably expect the original list to take 100 times longer than that, i.e. ~2900s. My example is roughly O(n).

Regards,

Andrew.

Jim,

The downside of this implementation is that it is O(n^2) and whilst the list is in order, it's in the order of the last occurrence rather than first occurrence of a repeated value.

An ordered version which is a bit cleaner than Derek's and avoids a reverse is:

 procedure(CCFuniqueInOrder(lst)
  let(((uniq makeTable('uniq)))
    setof(elem lst
    !boundp(uniq[elem]) && (uniq[elem]=t)
    )
  )
)

This is making the assumption that 'unbound is not in the list (which is probably a reasonable assumption in most scenarios).

For a list with 1000000 random integers with values up to 10000,  this took 0.65s (on my laptop running on battery only), whereas I gave up with yours. Running with a list 10 times shorter took 29s, so I'd reasonably expect the original list to take 100 times longer than that, i.e. ~2900s. My example is roughly O(n).

Regards,

Andrew.

Hi Andrew,

I managed to cook up a faster implementation using tables, based on a solution elsewhere:

(defun rmDuplicates (lst "l")

  (let ((r (makeTable 'r)))

    (foreach e lst r[e]=t)

    r->?))

Sorting an array of symbols 10000000 times, I see that my function is about 1.4x faster.

Maybe tables are the way to go for efficient skill programs!

Dushyant

Hi Dushyant,

Yes, you'll find that implementation in an older post I made 7 years ago (I'm sure I've posted it elsewhere before that too). The implementation above specifically was to allow the resulting list to be in the same order as in the input list, whereas the approach you've shown and in my other post will list the values in an arbitrary order. If the order doesn't matter, then the ->? approach would be fine. However, the saving is relatively small since they're both O(N) rather than O(N^2) and in most practical implementations the difference would probably be dominated by something else in the overall application where this is used, I'd expect. Both use hash tables to gain performance here - they can be useful for this purpose - although are not always the saviour for efficiency as it depends on what you're doing...

Regards,

Andrew.

Hi Andrew,

Ok -- I got so deep into speeding it up that I did not catch the ordering requirement in the question.

Thanks for these solutions, though. They are really helpful!

On a different note -- do you know if there are the likes of common lisp's functional programming features like reduce or Haskell's foldl, foldr? They are pretty useful for lisp processing, but I was not able to find them in SKILL.

Dushyant

There's a discussion (and example of foldr) in this thread. I haven't seen any formal requests for Common Lisp's reduce function to be implemented in SKILL.

Regards,

Andrew.