Finding unique elements of a list

[Daniel Luna]

On Tue, 7 Dec 2004, Luke Gorrie wrote:
> James Hague <jamesh@REDACTED> writes:
>> Is there a standard Erlang library function or idiom for removing duplicate
>> items from an unsorted list?  Ideally the elements in the final list should
>> be in the order they were passed in, except without duplicates:
>
> To be faster I think Vance-style with a dictionary or set to get O(N)
> or O(N log N) is the way, and I think this is reasonably nice:
>
>  remove_dups_linear(L) -> remove_dups_linear(L, gb_sets:new()).
>
>  remove_dups_linear([], _) -> [];
>  remove_dups_linear([H|T], S) ->
>      case gb_sets:is_member(H, S) of
>          true  -> remove_dups_linear(T, S);
>          false -> [H|remove_dups_linear(T, gb_sets:insert(H, S))]
>      end.

But this one isn't linear.

I assume that gb_sets:is_member is O(log(n)) as for most balanced trees.

Then the complexity is O(Nlog(N)) for all of it.

/Luna
-- 
Daniel Luna                           | Top reasons that I have a beard:
luna@REDACTED                     |  a) Laziness.
http://www.update.uu.se/~luna/        |  b) I can.
Don't look at my homepage (it stinks).|  c) I can get away with it.