Re: Re: Re: easiest way to sort a list?
- To: mathgroup at smc.vnet.net
- Subject: [mg18512] Re: [mg18408] Re: [mg18322] Re: [mg18308] easiest way to sort a list?
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Thu, 8 Jul 1999 22:32:51 -0400
- Sender: owner-wri-mathgroup at wolfram.com
I have just had a private "dispute" with David Withoff concerning a similar matter. My point was (or at least what I intended to say though maybe I faiiled to make it quite clear) was that a user has essentially no reliable way to "theoretically" estimate the performace of Mathematica programs, even their relative performance. All we can do is just run various examples on our machines and make guesses about what is going on internally. David Withoff's point - as far as I managed to understand it and I do hope I am not misrepesenting him- was that it is possible to make accurate "theoretical estimates" if one takes all the relevant factors into account. However what this seems to amount to is that David Withoff and others at wri can make such estimates, which is a rather different thing. -- Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp http://eri2.tuins.ac.jp ---------- >From: gaylord at ux1.cso.uiuc.edu (richard j. gaylord) To: mathgroup at smc.vnet.net >To: mathgroup at smc.vnet.net >Subject: [mg18512] [mg18408] Re: [mg18322] Re: [mg18308] easiest way to sort a list? >Date: Wed, Jul 7, 1999, 1:11 PM > > 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 >> >To: mathgroup at smc.vnet.net >> >Subject: [mg18512] [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)