Services & ResourcesWolfram ForumsMathGroup Archive

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

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