Re: Finding Position in an ordered list

*To*: mathgroup at smc.vnet.net*Subject*: [mg57743] Re: Finding Position in an ordered list*From*: "Carl K. Woll" <carl at woll2woll.com>*Date*: Tue, 7 Jun 2005 02:03:45 -0400 (EDT)*References*: <00fd01c56aab$6df39900$6400a8c0@Main> <b9804da6050606093923d55b62@mail.gmail.com>*Sender*: owner-wri-mathgroup at wolfram.com

Janos, If your data is numerical, and you want to find the positions of many numbers at once, then Interpolation is a much quicker method. Again, some numeric data: In[1]:= x = Sort[Table[Random[], {10^6}]]; Load your package: In[2]:= Needs["DiscreteMath`"] Define my function to find the position: In[3]:= f = Interpolation[Transpose[{x, N[Range[Length[x]]]}], InterpolationOrder -> 1]; // Timing Out[3]= {0.844 Second, Null} Compare finding the positions of 5000 elements using BinarySearch and using my Interpolation method: In[7]:= r1 = BinarySearch[x, #] & /@ Take[x, 5000]; // Timing r2 = Round[f[#]] & /@ Take[x, 5000]; // Timing r1 === r2 Out[7]= {2.453 Second, Null} Out[8]= {0.062 Second, Null} Out[9]= True As you can see, the Interpolation method is 40 times faster. Carl Woll ----- Original Message ----- From: "János TÓTH" <janostothmeister at gmail.com> To: mathgroup at smc.vnet.net Subject: [mg57743] Re: Finding Position in an ordered list Dear Carl, Many thanks, your solution also seems to be good, but, as usual :), there exist a built in function, as Daniel told me: BinarySearch in DiscreteMath. Thank you, Janos On 6/6/05, Carl K. Woll <carlw at u.washington.edu> wrote: > <janostothmeister at gmail.com> wrote in message > news:d811k4$cch$1 at smc.vnet.net... > >I wonder if it is possible to use the knowledge > > that a list in which I am looking for the position > > of an element is ordered. I want a quicker solution then e.g. > > lis={ac,dmk,rfg,sty,zxxer} > > Position[lis,sty] > > > > I am certainly interested in longer lists... > > > > Thank you, > > > > Janos > > > > Janos, > > I would think a binary search would be the quickest. I won't bother giving > an implementation, as you can do a search in the archives. For example: > > http://forums.wolfram.com/mathgroup/archive/1998/Jul/msg00022.html > > Could you provide a few more details on your problem? For example, is your > ordered list numeric, or does it contain names as you indicated in your > post. Also, are you interested in finding positions of more than one > element? If the answer to both of the above is yes, then you might find > using the built in binary search in Interpolation useful. For example, > suppose your list contained a million reals: > > x = Sort[Table[Random[], {10^6}]]; > > Create the interpolating function: > > In[2]:= > Timing[f = Interpolation[Transpose[{x, N[Range[Length[x]]]}], > InterpolationOrder -> 1]; ] > Out[2]= > {0.844 Second, Null} > > Find the location of an element: > > In[3]:= > Round[f[x[[100000]]]] // Timing > Out[3]= > {0. Second, 100000} > > Contrast this with using Position: > > In[4]:= > Position[x, x[[100000]]] // Timing > Out[4]= > {2.093 Second, {{100000}}} > > Finally, let's make sure that f returns the correct answers for every > element in your list: > > In[5]:= > (Round[f[x]]===Range[10^6])//Timing > > Out[5]= > {5.344 Second, True} > > Carl Woll > > > > >