I am certainly interested in longer lists...
Thank you,
Janos
?BinarySearch
BinarySearch[l, k] searches sorted list l for key k and gives the
position of l containing k, if k is present in l. Otherwise, if k is
absent in l, the function returns (p + 1/2) where k falls between the
elements of l in positions p and p+1. BinarySearch[l, k, f] gives the
position of k in the list obtained from l by applying f to each element
in l.
sincerely, Daniel
Here is a little experiment.
First I create a list of strings.
$Version
5.1 for Microsoft Windows (January 27, 2005)
Needs["Miscellaneous`Dictionary`"]
words = FindWords[__];
Length[words]
92836
Now I search the position of four words with Position:
Timing[
{Position[words,"egg"],Position[words,"book
"],Position[words,"you"],Position[words,"paper"]}]
{0.05 Second, {{{25730}}, {{8885}}, {{92516}}, {{57800}}}}
Now I create a little database:
db = Dispatch[Thread[words -> Range[Length[words]]]];
Timing[{"egg", "book", "you", "paper"} /. db]
{0. Second,{25730,8885,92516,57800}}
It is faster, as wanted.
Janos, maybe you could now determine the search time as a function of
the list size.
Cheers, Vittorio
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" <janostot...@gmail.com>
Subject: 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 <ca...@u.washington.edu> wrote:
> <janostot...@gmail.com> wrote in message
> news:d811k4$cch$1...@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
>
>
>
>
>
good luck
yehuda
0. Now I disclose that I am looking for a word in a dictionary.
1. Thank for the BinarySearch idea. It is much faster than Position.
2. The idea of interpolation in the case of numbers is fantastic.
3. However, I tried BinarySearch[{a,b,c},b] without being evaluated.
Thus, I need further help.
Thank for all of you.
Janos
BinarySearch in the Combinatorica package is written so that it
accepts only numeric input. It is very easy to change this:
BinarySearch[list_, elem_] := Module[{
n0 = 1, n1 = Length[list], m}, While[n0 ≤ n1, m = Floor[(n0 +
n1)/2];
If[list[[m]] == elem,
Return[m]]; If[OrderedQ[{list[[m]], elem}], n0 = m + 1, n1 = m -
1] ];
0 ]
BinarySearch[{a,b,c,},b]
2
BinarySearch[{a,b,c,},e]
0
0 means "not found".
Andrzej Kozlowski
Chiba, Japan
Janos,
Apparently the Combinatorica package BinarySearch function only accepts
numeric keys. We can modify this function to work with any key as follows:
binarysearch[d_, k_, ordf_:Less] :=
Module[{lo = 1, mid, hi = Length[d], c},
While[lo <= hi,
If[(c = d[[mid = Quotient[lo + hi, 2]]]) === k, Return[mid]];
If[ordf[k, c], hi = mid - 1, lo = mid + 1]];
Return[lo - 1/2]
]
Then, for your example, we would use the ordering function OrderedQ[{##}]&:
binarysearch[{a, b, c}, b, OrderedQ[{##}] &]
2
Carl Woll