Re: Re: easiest way to sort a list?
- To: mathgroup at smc.vnet.net
- Subject: [mg18408] Re: [mg18322] Re: [mg18308] easiest way to sort a list?
- From: gaylord at ux1.cso.uiuc.edu (richard j. gaylord)
- Date: Wed, 7 Jul 1999 00:11:06 -0400
- Organization: university of illinois
- References: <7lccua$1gg@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
this is the kind of thing that drives me TOTALLY beserk [or at least more
beserk-er]. looking at some timings for two programs taking fundamentally
different approaches.
In[1]:=
dog[lis_] := lis[[Sort[Flatten[Map[Position[lis, #, 1, 1] &, Union[lis]]]]]]
In[2]:=
OrderedUnion[1][li_] :=
Block[{i},
i[n_] := (i[n] = Sequence[]; n);
i /@ li]
In[3]:=
testLis1 = Table[Random[Integer, {1, 999}], {1000}];
In[4]:=
dog[testLis1]; // Timing
Out[4]=
{3.15 Second, Null}
In[5]:=
OrderedUnion[1][testLis1]; // Timing
Out[5]=
{0.366667 Second, Null}
In[6]:=
testLis2 = Table[Random[Integer, {1, 99}], {1000}];
In[7]:=
dog[testLis2]; // Timing
Out[7]=
{0.283333 Second, Null}
In[8]:=
OrderedUnion[1][testLis2]; // Timing
Out[8]=
{0.1 Second, Null}
In[9]:=
testLis3 = Table[Random[Integer, {1, 9}], {1000}];
In[10]:=
dog[testLis3]; // Timing
Out[10]=
{0.0333333 Second, Null}
In[11]:=
OrderedUnion[1][testLis3]; // Timing
Out[11]=
{0.0333333 Second, Null}
In[12]:=
testLis4 = Table[Random[Integer, {1, 9}], {10000}];
In[13]:=
dog[testLis4]; // Timing
Out[13]=
{0.216667 Second, Null}
In[14]:=
OrderedUnion[1][testLis4]; // Timing
Out[14]=
{0.383333 Second, Null}
In[15]:=
testLis5 = Table[Random[Integer, {1, 9}], {100000}];
In[16]:=
dog[testLis5]; // Timing
Out[16]=
{2.1 Second, Null}
In[17]:=
OrderedUnion[1][testLis5]; // Timing
Out[17]=
{3.83333 Second, Null}
the dog function is basically functional style while the orderedunion
function takes advantage of the unique Sequence function.which function
runs faster depends on the ratio of Length[Union[Lis]]/Length[Lis].
it is really frustrating when you can't use one style of programming
throughout but must spend time testing various approaches for calculating
various quantities in a program. it's even worse when the relative speeds
of different approaches reverses based on the numbers of values being used
[this is not very well stated but hopefully you'll get the idea].
i suppose other languages don't have this 'problem' (since most only have
one style of programming so there is no choice to be made) but there seems
to be alot of cases where scaling up from a 'toy' system to a 'real'
system becomes undoable due to unanticipated speed slowdown.
it would be helpful if there were some way to judge in advance what
approach will be best to use for a specific program but when i ask people
about it, i often hear 'well approach x seems like it should be faster
than approach y but it's really not possible to tell without writing the
program in both ways and comparing them'.
excuse this rant but i've been trying to convert some rule-based code to
functional style code and at this point i have no idea how to translate
pattern-matching operations into list manipulation operations.
-richard-
In article <7lccua$1gg at smc.vnet.net>, "Andrzej Kozlowski"
<andrzej at tuins.ac.jp> wrote:
> This is very efficient indeed and beutifully illustrates the usefullnes of
> the amazing Sequence function. The only slight weakness that I can see is
> when dealing with very long lists with a small number of distinct elements.
> Since we know that the final output must have the same number of elements as
> given by the (very fast) built-in Union function, for such lists one may do
> better by a code which stops checking elements of li once it has constructed
> a list of length Length[Union[li]]. Here is a modified code that does this:
>
>
> In[2]:=
> OrderedUnion1[li_]:=Block[{i,counter=0,l0={},m=Length[Union[li]]},
> i[n_]:=(i[n]=Sequence[];counter=counter+1;n);
> Scan[If[counter<m,l0={l0,i[#]},Return[Flatten[l0]]]&,li];Flatten[l0]]
>
> On very long lists with a small number of distinct elements this is somewhat
> faster than OrderedUnion:
>
> In[3]:=
> list1=Table[Random[Integer,{1,9}],{10000}];
>
> In[4]:=
> OrderedUnion[list1];//Timing
> Out[4]=
> {0.166667 Second, Null}
>
> In[5]:=
> OrderedUnion1[list1];//Timing
> Out[5]=
> {0.0833333 Second, Null}
>
> (Mac PowerBook G3 233 Mhz).
>
> However, in the case of lists with very few or no repetitions the balance is
> naturally reversed:
>
> In[6]:=
> list2=Range[1000];
>
> In[7]:=
> OrderedUnion[list2];//Timing
> Out[7]=
> {0.15 Second, Null}
>
> In[8]:=
> OrderedUnion1[list2];//Timing
> Out[8]=
> {0.25 Second, Null}
>
> What's worse, on my Mac if I try to apply OrderedUnion1 to
> list2=Range[10000] I get a crash, caused presumably by the Kernel running
> out of memory while building up a huge nested list.
>
> For those with a taste for weird Mathematica programs here is an unusual
> (and unfortunately inefficient) example:
>
> In[10]:=
> OrderedUnion2[l_]:=Module[{a},Reverse[GroebnerBasis[Map[a,l]]]/.a[k_]->k]
>
> e.g.
>
> In[11]:=
> OrderedUnion2[{3,2,4,5,a,a,3,6,5,2,8}]
> Out[11]=
> {3, 2, 4, 5, a, 6, 8}
>
>
> --
> Andrzej Kozlowski
> Toyama International University
> JAPAN
> http://sigma.tuins.ac.jp
> http://eri2.tuins.ac.jp
>
>
> ----------
> >From: "Carl K.Woll" <carlw at fermi.phys.washington.edu>
To: mathgroup at smc.vnet.net
> >To: mathgroup at smc.vnet.net
> >Subject: [mg18408] [mg18322] Re: [mg18308] easiest way to sort a list?
> >Date: Sun, Jun 27, 1999, 8:08 AM
> >
>
> > Peter,
> >
> > Here is one idea.
> >
> > OrderedUnion[li_]:=Block[{i},
> > i[n_]:=(i[n]=Sequence[];n);
> > i /@ li]
> >
> > The first time the function i hits an integer, it returns that
integer. After
> > that, it returns Sequence[], which disappears. I had another idea, where I
> > adjoined an auxiliary index list, then sorted and unioned using appropriate
> > tests. This idea was slightly faster for short lists. However, for longer
> > lists, it was slower, as the sorting algorithm is O(n log(n)), and the
> function
> > OrderedUnion is O(n).
> >
> > Carl Woll
> > Physics Dept
> > U of Washington
> >
> > Peter T. Wang wrote:
> >
> >> Hi everyone,
> >>
> >> Here's my question: Suppose you have a list of integers, not all distinct,
> >> say
> >> {1, 5, 3, 5, 10, 10, 1},
> >>
> >> and you want to obtain the list
> >>
> >> {1, 5, 3, 10}
> >>
> >> which is the set of distinct elements but with the order preserved; i.e.,
> >> the order in which the elements in the second list appear is the same as
> >> the order in which it first occurs in the first list. What is a simple
> >> way to do this? Evidently Union[] sorts the elements in canonical order,
> >> which is not desirable. My current solution is so messy that I suspect
> >> there must be an easier way.
> >>
> >> -peter
> >
> >
> >
--
"I would say life is pretty pointless, wouldn't you, without the movies?"
Vincent Gallo as Johnny Tempi in The Funeral (1996)