Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question

8 Answers 8

up vote 12 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Very clean. :-) –  Mr.Wizard Aug 27 at 10:59
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}} *)
share|improve this answer
    
Since it is Internal I should be able to use in a Compile ? –  lalmei Aug 27 at 10:30
    
@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. –  Pickett Aug 27 at 10:55

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 *)
share|improve this answer

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.

share|improve this answer

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}}
   }
*)
share|improve this answer

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.

share|improve this answer
1  
You were probably thinking about Mr.Wizard's dynP function. –  Pickett Aug 26 at 16:38
    
+1 because this is basically how I would do it. By the way you don't need Partition[#1, #2] &; instead use plain Partition. –  Mr.Wizard Aug 27 at 10:57

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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