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


Groups > comp.soft-sys.math.mathematica > #11338 > unrolled thread

Find Position of many elements in a large list.

Started bybenp84@gmail.com
First post2012-08-14 09:05 +0000
Last post2012-08-16 05:58 +0000
Articles 6 — 4 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  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

#11338 — Find Position of many elements in a large list.

Frombenp84@gmail.com
Date2012-08-14 09:05 +0000
SubjectFind Position of many elements in a large list.
Message-ID<k0d4bu$m8f$1@smc.vnet.net>
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.

[toc] | [next] | [standalone]


#11345

FromRoland Franzius <roland.franzius@uos.de>
Date2012-08-15 07:32 +0000
Message-ID<k0fj9u$q6m$1@smc.vnet.net>
In reply to#11338
Am 14.08.2012 11:05, schrieb benp84@gmail.com:
> 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 dont need any "code" at all.

Condsider this example executed on an i7 quad core notebook

data = RandomInteger[10000000, 500000];
pattern = RandomInteger[10000000, 10000];

patterninuse = Intersection[data, pattern];

Timing[pointers = Position[data, #] & /@ patterninuse;]
{17.471999999999998`, Null}

Now we Parallize by splitting the target list in two.

Four kernels get launched

{rg1, rg2} = Partition[data, Length[data]/2];
t1 = AbsoluteTime[];
Parallelize[
  pt1 = Position[rg1, #] & /@ patterninuse;
  pt2 = Position[rg2, #] & /@ patterninuse;
  pt = Join[pt1, pt2 + Length[pt1]];
  ]
AbsoluteTime[] - t1

4.7736084`8.130391782549879


Timing[] with Parallelize[] doesnt work.  Splitting a list of 1000000 in 
four partitions (plus a little error r3 instead rg3) sends the machine 
into nowhere.

Since memory reaches the maximum of 8 Gb and after some minutes even 
mouse interrupt is freezing and screen becomes black there may be a 
parallel problem using the graphic processor.

-- 

Roland Franzius

[toc] | [prev] | [next] | [standalone]


#11354

FromPeter Pein <petsie@dordos.net>
Date2012-08-15 07:33 +0000
Message-ID<k0fjcr$q85$1@smc.vnet.net>
In reply to#11338
Am 14.08.2012 11:05, schrieb benp84@gmail.com:
> 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.
>

Well, using the fact that the huge list (x) is sorted, I got a faster one.

binpos[xl_, y0_] :=
   Block[{mid = BitShiftRight[Length[xl]], sel, pos},
    If[mid === 0,
     Boole[xl === {y0}],
     If[xl[[mid]] <= y0, sel = Drop; pos = mid, sel = Take; pos = 0];
     pos + binpos[sel[xl, mid], y0]
     ]];
Reap[Fold[Drop[#1, Sow[binpos[##]]] &, x, Intersection[x, y]]][[2,
    1]] // Accumulate

needs only 20% of the time needed by
  Position[x,Alternatives@@Intersection[x,y]]//Flatten

I'm sure, this can be slightly optimized.
Peter

[toc] | [prev] | [next] | [standalone]


#11360

Fromdaniel.lichtblau0@gmail.com
Date2012-08-15 07:34 +0000
Message-ID<k0fjep$q91$1@smc.vnet.net>
In reply to#11338
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

[toc] | [prev] | [next] | [standalone]


#11363

FromPeter Pein <petsie@dordos.net>
Date2012-08-15 07:39 +0000
Message-ID<k0fjnm$qbc$1@smc.vnet.net>
In reply to#11338
Am 14.08.2012 11:05, schrieb benp84@gmail.com:
> 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.
>

Hi,

  the fastest way I was able to find is about four times faster than the 
naive approach

Flatten[Position[x, Alternatives @@ Intersection[x, y], 1]]

Dropping successively the irrelevant parts of the huge list x, searching 
becomes faster:

Reap[
  Fold[
   Drop[#1, Sow[LengthWhile[#1, Function[x0, x0 <= #2]]]] &,
   x, Intersection[x, y]
  ]
][[2, 1]] // Accumulate

I tried patterns and compilation; to no avail (see [1]).

Cheers,
  Peter

[1] https://dl.dropbox.com/u/3030567/Mathematica/getpositions.nb

[toc] | [prev] | [next] | [standalone]


#11372

Fromdaniel.lichtblau0@gmail.com
Date2012-08-16 05:58 +0000
Message-ID<k0i26i$1aq$1@smc.vnet.net>
In reply to#11338
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.

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

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web