13
$\begingroup$

Cross post here


I have a compile function cf to calculate the mean for a ragged list:

groups = N[{{40, 23, 213, 79, 18, 152, 105, 191, 119, 243}, {86, 3, 152, 89, 
     52, 36, 132, 196, 159, 108, 200}, {253, 223, 167, 197, 147, 112, 
     225, 98, 159, 163, 245, 240, 267}, {89, 164, 156, 124, 15, 253, 
     41, 171, 209, 132}}];

cf = FunctionCompile[
  Function[Typed[groups, "ListVector"::["ListVector"::["Real64"]]], 
   Mean[Cast[Catenate[groups], "PackedArray"::["Real64", 1]]]]]

cf[groups]

141.955

It works indeed. But I have to use the highly in-efficient "ListVector"::["ListVector"::[*]] for the following Catenate. Then I have to use a very time-consuming Cast for the following Mean in the code. This leads to a disastrous efficiency:

lis = DeleteCases[Table[ResourceFunction["RandomSplit"][RandomReal[255, 1000], 10],100000], {}, {2}];

Timing[Mean@*Catenate /@ lis;]
Timing[cf /@ lis;]

{2.70313, Null}

{9.92188, Null}

This is obviously a bit unbearably slow. I note the documentation of "ListVector": enter image description here So I think there must be a more efficient way to replace Cast, but the documentation is not perfect at the moment and I can't find any relevant examples to do this

$\endgroup$
2
  • 1
    $\begingroup$ I'd suggest not to concatenate the lists in order to compute the mean, but to sum their totals (Total[lis,2] should do) and then divide by Total[Length/@list]. $\endgroup$ Jul 20, 2022 at 14:02
  • $\begingroup$ @HenrikSchumacher Thanks. :) I'm obviously not interested in knowing the average about the ragged List in this post, but how to use and convert the "ListVector" $\endgroup$
    – yode
    Jul 20, 2022 at 14:13

1 Answer 1

16
$\begingroup$

Edit

Regarding the direct question in OP, i.e. how to flatten a "ragged" array inside FunctionCompile, I have to say there might be ready-to-use method but I'm not aware of any, so I'd propose to just roll your own, something like this:

flatten = FunctionCompile@
 Function[
   Typed[groups, "ListVector"::["PackedArray"["Real64", 1]]]
   , Module[{lensVec, totalLen, buffer, i}
         , lensVec = Length /@ groups // Developer`ToPackedArray
         ; totalLen = Total[lensVec]
         ; buffer = ConstantArray[Typed[0, TypeOf[groups[[1]][[1]]]], totalLen]
         ; i = 1;
         ; Do[Do[
                  buffer[[i]] = groups[[gidx]][[j]]; i++;
               , {j, lensVec[[gidx]]}]
            , {gidx, Length@groups}]
         ; buffer
     ]
  ]

TakeList[RandomReal[1, 20], {8, 10, 2}] // Echo[#, "in", Grid] & // flatten
(*
>> in  0.836502 0.14191   0.799241 0.851397 0.0942267 0.124684 0.589021 0.444985    
       0.239656 0.0272972 0.88519  0.860003 0.592972  0.663511 0.133296 0.927317 0.240553 0.469914
       0.217146 0.233076                      

Out[]= {0.836502, 0.14191, 0.799241, 0.851397, 0.0942267, 0.124684, \
0.589021, 0.444985, 0.239656, 0.0272972, 0.88519, 0.860003, 0.592972, \
0.663511, 0.133296, 0.927317, 0.240553, 0.469914, 0.217146, 0.233076}
*)

From my personal experience, "ListVector", as a general purpose expression container, is inefficient for such kind of computing -- much like in normal Wolfram language code where Sin[ a (* <- non-packed array *) ] is relatively inefficient than Sin[ a (* <- packed array *) ]. As I understand, in OP's case "ListVector" is needed to contain a "ragged array", but the usage should be limited to absolute needed. For example, here we can use "ListVector"::["PackedArray"["Real64", 1]] instead to achieve a better performance:

$Version
(* 13.1.0 for Microsoft Windows (64-bit) (June 16, 2022) *)

cf2 = FunctionCompile@Function[
      Typed[groups, "ListVector"::["PackedArray"["Real64", 1]]]
      , Module[{len = Length@groups, total, lenFull, mean}
            , lenFull = Length /@ groups // Developer`ToPackedArray // Total
            ; total = Total /@ groups // Developer`ToPackedArray // Total
            ; mean = Divide[total, lenFull]
       ]
   ]

It's much faster than cf described in OP:

AbsoluteTiming[Mean@*Catenate /@ lis;]
(* {5.26528,Null} *)

AbsoluteTiming[cf /@ lis;]
(* {22.5891,Null} *)

AbsoluteTiming[cf2 /@ lis;]
(* {0.508823,Null} *)

The code can be further optimized. In cf2 I used Developer`ToPackedArray to cast a "ListVector"[*] (e.g. from Length /@ groups) to "PackedArray"[*, 1], because Total is not defined on "ListVector"[*] type. But that casting introduces data copy, a familiar reason to slow down the compiled code just like similar case when using the good old Compile. On the other hand, by guessing, I found Sum is able to iterate along the "ListVector" directly, so here is a slightly faster one:

cf3 = FunctionCompile@Function[
      Typed[groups, "ListVector"::["PackedArray"["Real64", 1]]]
      , Module[{len = Length@groups, lenFull, total, mean}
            , lenFull = Sum[Length[groups[[i]]], {i, len}]
            ; total = Sum[Total[groups[[i]]], {i, len}]
            ; mean = Divide[total, lenFull]
       ]
   ]

AbsoluteTiming[cf3/@lis;]
(* {0.285133,Null} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.