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