Re: computing total[ragged array] fast
- To: mathgroup at smc.vnet.net
- Subject: [mg74357] Re: computing total[ragged array] fast
- From: "Ray Koopman" <koopman at sfu.ca>
- Date: Mon, 19 Mar 2007 05:52:12 -0500 (EST)
- References: <etlcp7$nup$1@smc.vnet.net>
sumRaggedArray = Total[PadRight[#,{Length@#,Max[Length/@#]}]]&
er wrote:
> hi,
>
> here's a 3x3 example of a ragged array
> ra={{a[1]},{a[2],b[2],c[2]},{a[3],b[3]}}
> and i'd like to define total s/t total[ra] returns
> {a[1]+a[2]+a[3],b[2]+b[3],c[2]}
> where each element is a numeric value (or at least the elements within
> a particular column are summable)
>
> below are 3 tentative functions and their timing performance vs size.
> Total (applied to a regular array) serves as benchmark: 1 outperforms
> 2&3 for large max-row-length but for small ones 3 is best, yet the
> speed gap relative to Total is big.
>
> any suggestion to narrow the gap for small (1-10) max-row-length?
>
> thanks,
>
> e.
>
> (*---code---*)
> Needs["Graphics`MultipleListPlot`"]
> Needs["Graphics`Legend`"]
>
> sumUnEqualLength=Module[{len1,len2,min,max},
> len1=Length[#1];len2=Length[#2]; min=Min[len1,len2];
> max=Max[len1,len2];
> Join[Take[#1,min]+Take[#2,min],
> Take[ If[len1<len2,#2,#1],{min+1,max}]]
> ]&;
>
> ClearAll[sumRaggedArray]
> sumRaggedArray[1]=Fold[sumUnEqualLength,{0},#]&;
> sumRaggedArray[2]=Module[{lens=Length/@#1,sum},
> sum=Array[0&,Max[lens]];
> Scan[sum[[Range[#[[2]]]]]+=#[[1]]&,Thread[{#1,lens}]];
> sum
> ]&;
> sumRaggedArray[3]=
> Module[{max=Max[Length/@#1]},Total[(PadRight[#1,max]&)/@#1]]&;
>
> (*
> (*too slow*)
> sumRaggedArray[4][ar_]:=Module[{lens=Length/@ar},
> Total/@
> Flatten[Reap[Scan[Module[{i=0},Scan[Sow[#,++i]&,#]]&,ar,2],
> Range[Max[lens]]][[2]],1]
> ];
> *)
>
> doPlot[n1_,n2_,n3List_,eqLen:True|False]:=Module[{ar,rar},
> ar=With[{n3=#},Array[Array[Random[]&,{n3}]&,{n1,n2}]]&/@n3List;
> If[
> eqLen,
> rar=ar,
> rar=
> With[{n3=#},
> Array[Array[Random[]&,{Random[Integer,{1,n3}]}]&,
> {n1,n2}]]&/@
> n3List;
> ];
> timings=
> Join[Table[
> Thread[{n3List,
> Timing[sumRaggedArray[i]/@#;][[1]]/(n1 Second)&/@rar}],
> {i,1,
> 3}],{Thread[{n3List,
> Timing[Total/@#;][[1]]/(n1 Second)&/@ar}]}];
> MultipleListPlot[##,PlotLabel\[Rule]"n2="<>ToString[n2],
> PlotJoined\[Rule]True,PlotLegend\[Rule]{1,2,3,"Total"},
> ImageSize\[Rule]72*10]&@@timings
> ];
>
> (*---experiments---*)
> (*timing vs max row-length of ragged array*)
> doPlot[50,5,Table[2^12-2^i,{i,0,11}],False];
> doPlot[500,5,Table[i,{i,1,10}],False];
>
> (*timing vs row-length of regular array*)
> doPlot[50,5,Table[2^12-2^i,{i,0,11}],True];
> doPlot[500,5,Table[i,{i,1,10}],True];