Re: Find Position of many elements in a large list.
- To: mathgroup at smc.vnet.net
- Subject: [mg127719] Re: Find Position of many elements in a large list.
- From: daniel.lichtblau0 at gmail.com
- Date: Thu, 16 Aug 2012 01:59:57 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- Delivered-to: l-mathgroup@wolfram.com
- Delivered-to: mathgroup-newout@smc.vnet.net
- Delivered-to: mathgroup-newsend@smc.vnet.net
- References: <k0d4bu$m8f$1@smc.vnet.net>
On Tuesday, August 14, 2012 4:05:02 AM UTC-5, ben... at gmail.com wrote:
> I have a sorted, 1-dimensional list X of 1,000,000 integers, and a sorted, 1-dimensional list Y of 10,000 integers. Most, but not all, of the elements of Y are also elements of X. I'd like to know the positions of the elements in X that are also in Y. What's the fastest way to compute this?
>
>
>
> I have an algorithm in mind but it requires lots of custom code and I'm wondering if there's a clever way to do it with built-in functions. Thanks.
Here is a method around an order of magnitude faster than my previous attempt. Still not the fastest one seen but it handles duplicates in case that's an issue. This time I do assume the inputs are sorted (which can dominate the time of the subsequent work).
posns2 = Compile[{{l1, _Integer, 1}, {l2, _Integer, 1}},
Module[
{res, n1 = Length[l1], n2 = Length[l2], n3 = 0, j = 1, k = 1,
diff},
res = ConstantArray[0, n1];
While[j <= n1 && k <= n2,
diff = l1[[j]] - l2[[k]];
If[diff < 0, j++, If[diff > 0, k++, n3++; res[[n3]] = j; j++]];
];
Take[res, n3]
]];
n1 = 6;
n2 = 4;
SeedRandom[1111];
l1 = Sort@RandomInteger[10^n1, 10^n1];
l2 = Sort@RandomInteger[10^n1, 10^n2];
In[557]:= Timing[pos2 = posns2[l1, l2];]
Out[557]= {0.160000, Null}
Daniel Lichtblau
Wolfram Research