computing total[ragged array] fast

• To: mathgroup at smc.vnet.net
• Subject: [mg74337] computing total[ragged array] fast
• From: "er" <erwann.rogard at gmail.com>
• Date: Mon, 19 Mar 2007 02:01:04 -0500 (EST)

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: Re: Possible bug in NSolve[equation, variable, precission]
• Next by Date: TraditionalForm[HoldForm[...]] query
• Previous by thread: Re: Possible bug in NSolve[equation, variable, precission] 2
• Next by thread: Re: computing total[ragged array] fast