MathGroup Archive 2012

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Find Position of many elements in a large list.

  • To: mathgroup at
  • Subject: [mg127719] Re: Find Position of many elements in a large list.
  • From: daniel.lichtblau0 at
  • Date: Thu, 16 Aug 2012 01:59:57 -0400 (EDT)
  • Delivered-to:
  • Delivered-to:
  • Delivered-to:
  • Delivered-to:
  • References: <k0d4bu$m8f$>

On Tuesday, August 14, 2012 4:05:02 AM UTC-5, ben... at 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}},
    {res, n1 = Length[l1], n2 = Length[l2], n3 = 0, j = 1, k = 1,
    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;
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

  • 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?