       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;
l1 = Sort@RandomInteger[10^n1, 10^n1];
l2 = Sort@RandomInteger[10^n1, 10^n2];

In:= Timing[pos2 = posns2[l1, l2];]

Out= {0.160000, Null}

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: Re: working with nested lists
• Next by Date: Re: Simplify
• Previous by thread: Re: Find Position of many elements in a large list.
• Next by thread: How to use Pick[]; Is this a bug?