MathGroup Archive 2007

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

Search the Archive

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];



  • 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