Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Map Question

• To: mathgroup at smc.vnet.net
• Subject: [mg45048] Re: [mg45025] Map Question
• From: "Ben Bongiorno" <bbongiorno at bdo.com>
• Date: Sun, 14 Dec 2003 06:22:47 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

Mr. Lichtblau

Thank you for your promp response.

Does your Module change if the elements being compared (===) are
strings?



Benedetto Bongiorno CPA, CRE
BDO Seidman, LLP
700 North Pearl Street
Suite 2000
Dallas, TX 75201
214-665-0717
bbongiorno at bdo.com

>>> Daniel Lichtblau <danl at wolfram.com> 12/13/03 01:35PM >>>
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


NOTICE:
The contents of this email and any attachments to it may contain privileged and confidential information from BDO Seidman, LLP.  This information is only for the viewing or use of the intended recipient.  If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution or use of, or the taking of any action in reliance upon, the information contained in this e-mail, or any of the attachments to this e-mail, is strictly prohibited and that this e-mail and all of the attachments to this e-mail, if any, must be immediately returned to BDO Seidman, LLP or destroyed and, in either case, this e-mail and all attachments to this e-mail must be immediately deleted from your computer without making any copies thereof.  If you have received this e-mail in error, please notify BDO Seidman, LLP by e-mail immediately.

• Follow-Ups:
  • Re: Re: Map Question
    • From: Daniel Lichtblau <danl@wolfram.com>