How to select unique elements in a list?
- To: mathgroup at smc.vnet.net
- Subject: [mg7953] How to select unique elements in a list?
- From: "C. Woll" <carlw at u.washington.edu>
- Date: Fri, 25 Jul 1997 02:40:28 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Hi again,
In a previous message (see below) I wanted to define a function which
selects unique elements from a list. I gave a proposed solution, which was
both slow and incorrect. The function worked for my specific application,
since my lists never had more than 2 identical elements, but for a general
list with an odd number of identical elements it gave an incorrect answer.
Since then, I have come up with a faster (and correct) solution as
follows:
Distinct[a_] := Select[Union[a],Count[a,#]===1&]
For the following test expression
test = Table[i[Random[Integer,1000]],{1000}];
the above version of Distinct produced an answer in 3.13 seconds. This
shoud be compared to the time it takes to evaluate Union[a] which is .05
seconds.
So, this solution is still too slow. Can anyone do better?
Carl Woll
On Wed, 23 Jul 1997, C. Woll wrote:
> Hi all,
>
> First, let me say that Union does not do what I'm looking for! I am
> interested in a function which returns the unique elements from a list.
> Let's call the function Distinct. Then, I want
>
> Distinct[{i1,i2,i3,i2}]
>
> to return
>
> {i1,i3}
>
> Of course, I can write a function to do this, but I am hoping someone can
> do a better job them my feeble attempt. So, my best functional solution so
> far is,
>
> RemoveDuplicates[a___,i_,i_,b___]:=RemoveDuplicates[a,b]
> Distinct[a_List]:=List@@RemoveDuplicates@@Sort[a]
>
> However, this solution is very slow. For example, with
>
> test=Table[i[Random[Integer,1000]],{1000}];
>
> it takes approximately 27 seconds to evaluate Distinct[test] on an SGI
> system. This is slow when compared to .01 seconds to evaluate Union[test]!
>
> It's likely that the way to go is to use a procedural method instead of a
> functional method.
>
> At any rate, can anyone come up with a solution which is competitive in
> speed with Union?
>
> Carl Woll
>
>
>