Finding unique elements of a list
Tue Dec 7 12:42:05 CET 2004
On Tue, 7 Dec 2004, Luke Gorrie wrote:
> James Hague <> 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))]
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.
Daniel Luna | Top reasons that I have a beard:
| 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.
More information about the erlang-questions