MathGroup Archive 1997

[Date Index] [Thread Index] [Author Index]

Search the Archive

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




  • Prev by Date: How to select unique elements in a list?
  • Next by Date: Waiting for a user to finish with a notebook
  • Previous by thread: How to select unique elements in a list?
  • Next by thread: Re: How to select unique elements in a list?