21
$\begingroup$

Trying to unflatten an array that was part of ragged array of sub matrices.

As input we have flattened array:

  myflatarray={7.7056, 4.20225, 3.02775, 7.60807, 9.77169, 6.18476, 4.80993,
   6.32965, 2.69882, 0.268505, 1.78048, 9.67702, 0.875699, 7.18504, 
   1.62811, 0.0313174, 5.66048, 1.61613, 5.71987, 0.971484, 3.87503, 
   2.8537, 2.68776, 3.47433, 2.81483, 4.0387, 1.74939, 3.12037, 4.18016, 
   2.35264, 0.853583, 1.22412, 0.382633, 3.67874, 8.68059, 8.02419, 
   6.9547, 7.11112};

and the original dimensions of the submatrices in the ragged array.

  mydimensions={{4, 5}, {3, 4}, {2, 3}};

In other words the original object looked like

 original={
  {{7.7056, 4.20225, 3.02775, 7.60807, 9.77169}, 
   {6.18476, 4.80993, 6.32965, 2.69882, 0.268505}, 
   {1.78048, 9.67702, 0.875699, 7.18504, 1.62811}, 
   {0.0313174, 5.66048, 1.61613, 5.71987,  0.971484}}, 
  {{3.87503, 2.8537, 2.68776, 3.47433}, 
   {2.81483, 4.0387,1.74939, 3.12037}, 
   {4.18016, 2.35264, 0.853583, 1.22412}}, 
  {{0.382633, 3.67874, 8.68059}, 
   {8.02419, 6.9547, 7.11112}}
 };

I tried using the undocumented function Internal`Deflatten, and it didn't work, but I was happy that it didn't crash my kernel!

I'm able to do it rather inefficiently this way:

  arraytoweights[myflatarray_,mydimensions_]:=
  MapIndexed[Partition[#1, mydimensions[[Last@#2, 1]]] &, 
  Take[myflatarray, #] & /@ ((# - {0, 1}) & /@ (Partition[
  FoldList[Plus, 1, (Times @@@ mydimensions)], 2, 1]))];

My main problem is that this is part of an optimization function, that needs to be called many times during the optimization, and this is atm the slowest part. It also can't seem to be compiled. I suppose with Compile I have to make sure there are no ragged arrays generated in-between neither. Any suggestions are appreciated!

Edit: So it turns out mine is not as bad as I thought. Though I like the extensions to more structure as @Leonid did. I have no need for it now, but I see how I can use it in the future.

Here is the current tally of the answers and their timing, using a random larger result, the typical size I need. (only with submatrices atm)

    mydimensions = {{30, 4}, {10, 5}, {3, 4}, {2, 1}};
    SeedRandom[1345]
    original = ((RandomReal[{0, 10}, ##] & /@ mydimensions));
    myflatarray = Flatten[original];

For the timing I ran the result from each with $10^3$ runs. For example, here the set for my results.

    lalmeiresults = 
         Table[First@
           Timing[lalmei = arraytoweights[myflatarray, mydimensions];],    {i,Range@1000]}]
     lalmei === original

True

Here is the BoxWhiskerChart, with only the 95% quantile, no outliers. (Not sure if this the best way to do timing, but here it goes )

enter image description here

Couple of notes about the image: the distribution of mine and Leonid's, and seismatica's is about the same. Picket's is only a bit larger 25% only.

Mr.Wizard's, kguler's and WReach's results only shoot up as the size of the sub-matrices gets larger.

With a small examples, Mr. Wizard's is the fastest.

      mydimensions = {{3, 4}, {2, 5}, {3, 4}, {2, 1}};
      SeedRandom[1345]
      original = ((RandomReal[{0, 10}, ##] & /@ mydimensions));

Here the distributions in that case: enter image description here

$\endgroup$
16
$\begingroup$

Here is a version which is quite general, and based on Mr.Wizard's dynP function:

dynP[l_, p_] := 
   MapThread[l[[# ;; #2]] &, {{0}~Join~Most@# + 1, #} &@Accumulate@p]

ClearAll[tdim];
tdim[{dims__Integer}] := Times[dims];
tdim[dims : {__List}] := Total@Map[tdim, dims];

ClearAll[pragged];
pragged[lst_, {}] := lst;
pragged[lst_, dims : {__Integer}] := 
   Fold[Partition, lst, Most@Reverse@dims];
pragged[lst_, dims : {__List}] := 
   MapThread[pragged, {dynP[lst, tdim /@ dims], dims}];

It may look similar to other answers, but the difference is that it can take more general specs. Example:

pragged[Range[20], {{{2, 3}, {2, 4}}, {2, 3}}]

(* 
   {
     {{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9, 10}, {11, 12, 13, 14}}}, 
     {{15,16, 17}, {18, 19, 20}}
   }
*)

In general, the specs to pragged will form a tree.

$\endgroup$
14
$\begingroup$

Here is a semi-imperative way:

result = Module[{i = 1}, Array[myflatarray[[i++]]&, #]& /@ mydimensions];

result === original
(* True *)

It uses Array to build up each of the original submatrices, taking successive elements from the flat array.

$\endgroup$
  • $\begingroup$ Very clean. :-) $\endgroup$ – Mr.Wizard Aug 27 '14 at 10:59
13
$\begingroup$
MapThread[
 Partition,
 {Internal`PartitionRagged[myflatarray, Times @@@ mydimensions], mydimensions[[All, 2]]}
 ]

Internal`PartitionRagged is undocumented. An example of how it works is:

Internal`PartitionRagged[{1,2,3,4,5},{3,2}]
(* Out: {{1,2,3},{4,5}} *)
$\endgroup$
  • $\begingroup$ Since it is Internal I should be able to use in a Compile ? $\endgroup$ – lalmei Aug 27 '14 at 10:30
  • $\begingroup$ @lalmei I'm afraid not; to test it we can try something like Compile[{}, Internal`PartitionRagged[Range[10], {5, 5}]][] and it turns out PartitionRagged that is not compilable. $\endgroup$ – C. E. Aug 27 '14 at 10:55
  • $\begingroup$ @lalmei The WVM (Wolfram Virtual Machine), which runs the compiled code, can handle only regular arrays. A function that returns a ragged array will cause a runtime error. Usually such functions are called via MainEvaluate, which performs an (uncompiled) evaluation in the "main" (i.e. regular) kernel, but it will still cause an error if the result is ragged array. $\endgroup$ – Michael E2 Mar 7 '15 at 14:42
10
$\begingroup$

Here is my contribution: a performance improvement upon WReach's method.
Extracting entire rows at a time can be considerably faster with hopefully a minimum of obfuscation.

fn[source_, dims_] :=
  Module[{i = 0},
    source ~Take~ {i + 1, i += #2} ~Table~ {#} & @@@ dims
  ]

Test:

fn[Range@19, {{2, 3}, {4, 1}, {3, 3}}] // Column
{{1,2,3},{4,5,6}}
{{7},{8},{9},{10}}
{{11,12,13},{14,15,16},{17,18,19}}

Performance compared to WReach's code:

WR[source_, dims_] :=
 Module[{i = 1}, Array[source[[i++]] &, #] & /@ dims]

d = RandomInteger[{1, 300}, {350, 2}];
s = Range @ Tr[Times @@@ d];

fn[s, d] // Timing // First
WR[s, d] // Timing // First
0.062400

7.051245

So my modification yields more than two orders of magnitude improvement for subarrays with an average dimension of 150.5.

$\endgroup$
7
$\begingroup$

Modifying halirutan's unflatten and Ray Koopman's copyPartition that appeared in this Q/A

unflatten2[a_, dims_] := Module[{i = 1, b = Map[ConstantArray[0, #] &, dims, {-2}]},
                                Function[Null, a[[i++]], {Listable}][b]];
copyPartition2[a_, dims_] := Module[{i = 0, b = Map[ConstantArray[0, #] &, dims, {-2}]}, 
                                    Map[a[[++i]] &, b, {-1}]]

mydimensions = {{4, 5}, {3, 4}, {2, 3}};

unflatten2[myflatarray, mydimensions] == original
(* True *)

copyPartition2[myflatarray, mydimensions] == original
(* True *)

Both give the same results as Leonid's function pragged for general dimension specs:

dims = {{{2, 3}, {2, 4}}, {2, 3}}; 
unflatten2[Range[20], dims] == copyPartition2[Range[20], dims] == pragged[Range[20], dims] 
(* True *)
$\endgroup$
4
$\begingroup$

Not sure if this is faster but here it goes:

Module[{accumulateLength, subMatrices},
 accumulateLength = Accumulate[Times @@@ mydimensions];
 subMatrices = MapThread[myflatarray[[#1 ;; #2]] &, {Prepend[Most[accumulateLength] + 1, 1],
     accumulateLength}];
 MapThread[Partition[#1, #2] &, {subMatrices, Last /@ mydimensions}]]

The step to generate the submatrices have been done before here, but I can't seem to find it, though I remember @Mr.Wizard had a more elegant syntax using Thread. It's basically just extracting sublists of (given) variable lengths from a larger list i.e. PartitionRagged in @Pickett's answer.

$\endgroup$
  • 1
    $\begingroup$ You were probably thinking about Mr.Wizard's dynP function. $\endgroup$ – C. E. Aug 26 '14 at 16:38
  • 1
    $\begingroup$ +1 because this is basically how I would do it. By the way you don't need Partition[#1, #2] &; instead use plain Partition. $\endgroup$ – Mr.Wizard Aug 27 '14 at 10:57
4
$\begingroup$

Another version which will take more general specs, though performance is not great:

ragged[l_, dims_] := Module[{x = l},
  dims /. {n__Integer} :> ArrayReshape[x, x = Drop[x, 1 n]; {n}]]

e.g.

ragged[Range[20], {{{2, 3}, {2, 4}}, {2, 3}}]

(* 
   {
     {{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9, 10}, {11, 12, 13, 14}}}, 
     {{15,16, 17}, {18, 19, 20}}
   }
*)
$\endgroup$
4
$\begingroup$

You say that speed is important, and that you will be converting back and forth to a ragged output many times. Assuming that the dimensions of the ragged output aren't changing, then I think the fastest method would be to create a ragged template function once, and then to use the template function on your data. Here is what I mean. The following creates the ragged template function for a set of dimensions:

raggedTemplate[dim_]:=Module[{i=1},
    Function[Evaluate @ Activate @ Map[Inactive[Slot][i++]&, ConstantArray[0,#]& /@ dim, {-1}]]
]

Now, we create a template function for the desired dimensions:

mydimensions = {{30,4},{10,5},{3,4},{2,1}};
tf = raggedTemplate[mydimensions]; //RepeatedTiming

{0.00017, Null}

This is a little slow, but it only needs to be done once. Finally, we apply the template function to the data:

SeedRandom[1345]
original = ((RandomReal[{0,10},##]& /@ mydimensions));
myflatarray = Flatten[original];

r1 = tf @@ myflatarray; //RepeatedTiming

{9.0*10^-6, Null}

Compare this to LeonidShifrin's answer:

r2 = pragged[myflatarray, mydimensions]; //RepeatedTiming

{0.000039, Null}

They give the same result:

r1 === r2

True

$\endgroup$
2
$\begingroup$

Maybe this is faster:

par[arr_, dim_] :=
 Module[{x = Last /@ dim, y = First /@ dim, l1 = Length @ arr, l2, a},
  {
   a = Take[Partition[arr, y[[1]]], x[[1]]],
   a = Take[Partition[Take[arr, (l2 = Length @ Flatten @ a) - l1], y[[2]]], x[[2]]],
   Partition[Take[arr, l2 + Length @ Flatten@a - l1], y[[3]]]
   }];

par[myflatarray, {{4, 5}, {3, 4}, {2, 3}}] == result

True

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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