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