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]];
>         sum
>         ]&;
> sumRaggedArray[3]=
>
> (*
>   (*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[
>                 Timing[sumRaggedArray[i]/@#;][[1]]/(n1 Second)&/@rar}],
> {i,1,
>                 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];

```

• Prev by Date: Re: NDSolve doesn't stop
• Next by Date: Re: Membrane
• Previous by thread: computing total[ragged array] fast
• Next by thread: Help to use colors with graphics in Mathematica