Re: Map Question
- To: mathgroup at smc.vnet.net
- Subject: [mg45046] Re: [mg45025] Map Question
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sun, 14 Dec 2003 06:22:43 -0500 (EST)
- References: <200312131106.GAA11055@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Ben Bongiorno wrote:
>
> Happy Holidays,
>
> a = matrix variable of 22353 x 23 size
> b = list variable of 21963 size
> c = matrix variable of 21963 x 1 size
>
> My Do routine
>
> x=0;
> Do[x=x+1;
> c[[x]]=Select[a,#[[3]]===b[[x]]&],
> {Length[b]}]
>
> How can I utilize Map to speed up this routine?
>
> Benedetto Bongiorno CPA, CRE
> BDO Seidman, LLP
> 700 North Pearl Street
> Suite 2000
> Dallas, TX 75201
> 214-665-0717
> bbongiorno at bdo.com
> [...]
Actually your result is (in general) not a matrix at all. It may be
described as a list of subsets of rows of the original matrix.
A pedestrian approach to do what you have in mind might be as follows.
cc = Table[
Select[aa,#[[3]]===bb[[j]]&],
{j,Length[bb]}]
This will be very slow because the complexity is
O(length(aa)*length(bb)). Indeed, it is not even faster than your code,
just slightly cleaner insofar as it does not require a list
initialization. Here is an example around 200 times smaller than yours.
In[51]:= aa = Table[Random[Integer, 10], {1100}, {23}];
In[52]:= bb = Table[Random[Integer, 10], {2100}];
In[53]:= Timing[cc = Table[
Select[aa,#[[3]]===bb[[j]]&],
{j,Length[bb]}];]
Out[53]= {16.55 Second, Null}
If your elements are, say, real numbers then you can use ordering to get
a much faster code. First sort the matrix based on values of third
elements in each row. Next sort the vector by values, keeping track of
their original positions.
Now you simply walk over both sorted objects, increasing the matrix
index when third element of a row is less than b vector element,
increasing the vector index when the inequality is reversed, and
stuffing a set of rows into the appropriate slots of the result while
the two values are equal. Code to do this is below.
f[a_,b_] := Module[
{aaa, bbb, res, lena=Length[a], lenb=Length[bb], j=1, k=1, oldj},
aaa = aa[[Ordering[aa[[All,3]]]]];
bbb = Sort[Transpose[{bb,Range[lenb]}]];
res = Table[{}, {lenb}];
While [j<=lena && k<=lenb,
aj = aaa[[j]];
bk = bbb[[k]];
If [aj[[3]] < bk[[1]], j++; Continue[]
, (* else *)
If [aj[[3]]>bk[[1]], k++; Continue[]]
];
oldj = j;
While [j<=lena && aaa[[j,3]]==bk[[1]], j++];
res[[bk[[2]]]] = aaa[[Range[oldj,j-1]]];
While [k<lenb && bbb[[k+1,1]]==bk[[1]],
k++; bk = bbb[[k]]; res[[bk[[2]]]] = aaa[[Range[oldj,j-1]]];
];
];
res
]
Here is an example of the size you have in mind.
In[48]:= aa = Table[Random[Integer, 1000], {22353}, {23}];
In[49]:= bb = Table[Random[Integer, 1000], {21963}];
In[50]:= Timing[result = f[aa,bb];]
Out[50]= {1.24 Second, Null}
Extrapolating from the first example, I would expect the pedestrian code
to take about an hour on the full size example. It's still running.
Daniel Lichtblau
Wolfram Research
- References:
- Map Question
- From: "Ben Bongiorno" <bbongiorno@bdo.com>
- Map Question