Re: Find Position of many elements in a large list.
- To: mathgroup at smc.vnet.net
- Subject: [mg127701] Re: Find Position of many elements in a large list.
- From: daniel.lichtblau0 at gmail.com
- Date: Wed, 15 Aug 2012 03:37:46 -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.
You could directly walk the lists, skipping ahead as needed and marking positions when applicable. This can be made fairly fast since it is amenable to Compile provided the integers are machine numbers.
Here is a method that does not use sorting and is still reasonably fast. We'll make a lookup table for elements in Y and then walk X and mark which elments are in that lookup table.
posns[l1_, l2_] := Module[
{tbl, res},
Do[tbl[l2[[j]]] = True, {j, Length[l2]}];
res = Reap[Do[If[TrueQ[tbl[l1[[j]]]], Sow[j]], {j, Length[l1]}]][[2,
1]];
Clear[tbl];
res
]
Test:
In[373]:= n1 = 6;
n2 = 4;
In[381]:= SeedRandom[1111];
l1 = RandomInteger[10^n1, 10^n1];
l2 = RandomInteger[10^n1, 10^n2];
In[384]:= Timing[pos = posns[l1, l2];]
Out[384]= {1.460000, Null}
In[385]:= Length[pos]
Out[385]= 10009
Daniel Lichtblau
Wolfram Research