Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

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



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