# What is the best build-in function to pick or select given element in a huge list

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.

• That depends on the concrete setup. Sorry, I did not understand your example. Would you please elaborate? – Henrik Schumacher Dec 3 '18 at 15:41
• 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}} – Ramez Hindi Dec 3 '18 at 15:43
• 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? – Henrik Schumacher Dec 3 '18 at 15:45
• yes the function will return to me the position of it – Ramez Hindi Dec 3 '18 at 15:47
• 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. – user202729 Dec 3 '18 at 15:47

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.

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