Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #11360

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

From daniel.lichtblau0@gmail.com
Newsgroups comp.soft-sys.math.mathematica
Subject Re: Find Position of many elements in a large list.
Date 2012-08-15 07:34 +0000
Message-ID <k0fjep$q91$1@smc.vnet.net> (permalink)
References <k0d4bu$m8f$1@smc.vnet.net>
Organization Time-Warner Telecom

Show all headers | View raw


On Tuesday, August 14, 2012 4:05:02 AM UTC-5, ben...@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

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Find Position of many elements in a large list. benp84@gmail.com - 2012-08-14 09:05 +0000
  Re: Find Position of many elements in a large list. Roland Franzius <roland.franzius@uos.de> - 2012-08-15 07:32 +0000
  Re: Find Position of many elements in a large list. Peter Pein <petsie@dordos.net> - 2012-08-15 07:33 +0000
  Re: Find Position of many elements in a large list. daniel.lichtblau0@gmail.com - 2012-08-15 07:34 +0000
  Re: Find Position of many elements in a large list. Peter Pein <petsie@dordos.net> - 2012-08-15 07:39 +0000
  Re: Find Position of many elements in a large list. daniel.lichtblau0@gmail.com - 2012-08-16 05:58 +0000

csiph-web