RE: Re: Re: easiest way to sort a list?

• To: mathgroup at smc.vnet.net
• Subject: [mg18525] RE: [mg18428] Re: [mg18344] Re: [mg18308] easiest way to sort a list?
• From: "Ersek, Ted R" <ErsekTR at navair.navy.mil>
• Date: Thu, 8 Jul 1999 22:32:57 -0400
• Sender: owner-wri-mathgroup at wolfram.com

```I have a new approach to add to this long thread.

In[1]:=
OrderedUnion5[h_[args__]]:=
Fold[ If[ FreeQ[#1,#2,1], Join[#1,h[#2]], #1]& ,h[],{args}]

In[2]:=
OrderedUnion5[{5,3,5,3,1,2,2,3,4,5,3}]

Out[2]=
{5,3,1,2,4}

I would like to see how the timings of different methods compare (version
above included).  I would do it, but I am working under Windows 98, and I
understand Microsoft made it impossible for Timing to give accurate results.

Regards,
Ted Ersek

--------------------
Hi Hartmut (and newsgroup),

Thanks for unraveling the linear nature of the Block[{i... function. Nice
explanation!

Since this topic shows no sign of slowing down, I thought I would present a
couple refined versions of my two functions. First, an improvement of the
"linear" solution:

OrderedUnion[li_]:=Block[{i,Sequence},
i[n_]:=(i[n]=Sequence[];n);
i/@li]

By including Sequence in the Block variables, Mathematica doesn't waste time
eliminating Sequences until after the Block is exited. This seems to be a
5-10% or so improvement in speed.

Secondly, an improvement of my O(n log n) solution:

OrderedUnion[3][li_]:=Module[{tmp=Transpose[{li,Range[Length[li]]}]},
tmp=Union[tmp, SameTest->(#1[[1]]===#2[[1]]&)];
Last/@Sort[RotateLeft/@tmp]]

The key idea here is that Sort with the default ordering function is much
faster than Sort with a user supplied ordering function. So, RotateLeft
switches the order of the index and the element to allow Sort to be used
with its default ordering function. For lists with a large number of
distinct elements, this seems to improve the speed by a factor of 3.

Carl Woll
Dept of Physics
U of Washington

Wolf, Hartmut wrote:

> Hello everone,
>
> I just sent a letter to Carl K.Woll, part of which I would like to
> publish to the community:
>
> Hello Carl,
>
> congratulations for your brilliant solution of "easiest way to sort a
> list?" At the first glance, ... I was already struck.
>
> According to my measurements, you proposed not only the fastest
> solution, but also the second fastest, the fastest O[n log n] version.
> ....
>
> The question that concerned me was, is your solution really O[n]? My
> preoccupation before was that O[n log n] could be the best achievable.
> Clearly your solution is O[n] for 'smaller' samples, but the question
> was, is it still O[n] for very large samples?  So I did some
> measurements, which I'd like to show you. They are in the two attached
> notebooks (...not for you, unless you request it from
> mailto:hwolf at debis.com )
>
> What is the interpretation of the graphs? In fact your solution is as
> far as I could calculate seemingly linear overall. There are interesting
> wiggles in it. The algorithm seems to become increasingly worse, when it
> makes up it's mind and "starts anew". Well I think this are the traces
> of Mathematica's Extendible Hashing algorithm for the symbol store. When
> hashing becomes more and more inefficient (due to collisions) then the
> store ist extended. (This conforms to my observation of memory usage
> with Windows NT Task Manager during the calculation, where I say periods
> of rapid increase of used memory and times of slower grow.) So it's this
> extension, which keeps your algorithm linear.
>
> ....
>
> With kind regards, your
>         Hartmut Wolf

```

• Prev by Date: Thickness in 3D parametric plots
• Next by Date: Re: Re: Re: easiest way to sort a list?
• Previous by thread: Re: Re: Re: easiest way to sort a list?
• Next by thread: Re: Re: Re: easiest way to sort a list?