0
$\begingroup$

im looking for a best and efficient function works like a search engine it takes for example m=5+6I ,then it goes searching in the list V={1,1+I,2+3I,...} until catch it . My Dr said to use "Select[]", but im not sure if its efficient if the size of V is more than 200 element.

$\endgroup$
  • $\begingroup$ That depends on the concrete setup. Sorry, I did not understand your example. Would you please elaborate? $\endgroup$ – Henrik Schumacher Dec 3 '18 at 15:41
  • $\begingroup$ If i have m=1+5*I as Gaussian integer i want to use a function to search for it in the complete residue system of guassian integers Zn[i]={a+ib/a,b are in Z_{n}} $\endgroup$ – Ramez Hindi Dec 3 '18 at 15:43
  • $\begingroup$ And when you found it? What's next? If you Pick or Select it, the selected values is still equal to m. Maybe you want to know the position of m within a given list of Gaussian integers? $\endgroup$ – Henrik Schumacher Dec 3 '18 at 15:45
  • $\begingroup$ yes the function will return to me the position of it $\endgroup$ – Ramez Hindi Dec 3 '18 at 15:47
  • $\begingroup$ How is your list represented? If it's just a normal list then searching in it takes the time at least the time required to read it. $\endgroup$ – user202729 Dec 3 '18 at 15:47
1
$\begingroup$

Here a basis example how to use Nearest to perform the search in $\log(n)$ time where $n$ is the length of the list $V$.

k = 1000;
V = Flatten[Outer[Plus, Range[k], I Range[k]], 1];
NV = N[V];
nf = Nearest[NV -> Automatic]; // AbsoluteTiming // First
mlist = RandomInteger[{1, k}, {1000, 2}].{1, I};
positions = nf[N[mlist], {1, 0.}]; // AbsoluteTiming // First
Extract[V, positions] == mlist

0.060709

0.001179

True

Notice that applying the search to each of the elements 100000 in mlist is dominant; the total runtime of the call to nf is the same for k = 100, k = 1000, and k = 10000 (i.e., $n = 10000$, $n = 1000000$, and $n = 100000000$).

The trick is that Nearest uses a $k$d-tree data structure to organize the data points for fast lookup.

For comparison, here is a straight-forward implementation with Position; each lookup has complexity $O(n)$:

positions2 = Position[V, #] & /@ mlist; // AbsoluteTiming // First
positions == Join @@ positions2

32.9766

True

That takes about 28000 times longer.

$\endgroup$
  • $\begingroup$ This assumes OP has multiple nearest/contains query. If they have only one then the obvious algorithm is still (asymptotically) optimal. $\endgroup$ – user202729 Dec 3 '18 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.