Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #11338 > unrolled thread
| Started by | benp84@gmail.com |
|---|---|
| First post | 2012-08-14 09:05 +0000 |
| Last post | 2012-08-16 05:58 +0000 |
| Articles | 6 — 4 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
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
| From | benp84@gmail.com |
|---|---|
| Date | 2012-08-14 09:05 +0000 |
| Subject | Find 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]
| From | Roland Franzius <roland.franzius@uos.de> |
|---|---|
| Date | 2012-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]
| From | Peter Pein <petsie@dordos.net> |
|---|---|
| Date | 2012-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]
| From | daniel.lichtblau0@gmail.com |
|---|---|
| Date | 2012-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]
| From | Peter Pein <petsie@dordos.net> |
|---|---|
| Date | 2012-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]
| From | daniel.lichtblau0@gmail.com |
|---|---|
| Date | 2012-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