19
$\begingroup$

For example, if we have

assoc = 
  AssociationThread[{1, 2, 3} -> RandomReal[1., {3, 10}]];

and

Developer`PackedArrayQ/@ assoc

gives

<|1 -> True, 2 -> True, 3 -> True|>

so each Value is packed array.

Now, I want to Merge several Assocation like this. Then I checked packedness,

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Flatten]

it gives

<|1 -> False, 2 -> False, 3 -> False|>

It unpacks, even though Flatten should not unpack list.

So is it possible to avoid this unpacking in Merge?

$\endgroup$
21
$\begingroup$

One can use TracePrint to see how Flatten is being used by Merge:

TracePrint[
    Merge[{assoc,assoc}, Flatten],
    _Flatten,
    TraceAction->Print@*Developer`PackedArrayForm
];

Flatten[{PackedArray[Real,<10>],PackedArray[Real,<10>]}]

Flatten[{PackedArray[Real,<10>],PackedArray[Real,<10>]}]

Flatten[{PackedArray[Real,<10>],PackedArray[Real,<10>]}]

Notice how Merge builds a list of two packed arrays, and then flattens them. This is why the the arrays become unpacked. To workaround this, you can either convert the list of two packed arrays into a packed array first:

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Flatten @* Developer`ToPackedArray]

<|1 -> True, 2 -> True, 3 -> True|>

Or you can use Join with Apply (as in Henrik's answer, but using slot free syntax):

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Apply[Join]]

<|1 -> True, 2 -> True, 3 -> True|>

$\endgroup$
  • $\begingroup$ Hi, Carl Woll, I posted a summary answer, and there are some issue I don't understand. Would you to have a look? $\endgroup$ – matheorem Mar 12 at 5:00
10
$\begingroup$

Instead of using Merge, you can also use AssociationTranspose which is often much faster than Merge and doesn't unpack:

m1 = Merge[{assoc, assoc}, Flatten];
m2 = Flatten /@ GeneralUtilities`AssociationTranspose[{assoc, assoc}];
m1 === m2
Developer`PackedArrayQ /@ m1
Developer`PackedArrayQ /@ m2

True

<|1 -> False, 2 -> False, 3 -> False|>

<|1 -> True, 2 -> True, 3 -> True|>

Frankly, AssociationTranspose + Map is pretty much just superior to Merge like 99% of the time.

$\endgroup$
9
$\begingroup$

Join tries to pack whenever it is possible:

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Join @@ # &]

<|1 -> True, 2 -> True, 3 -> True|>

One might expect that Catenate should also work, but it does not.

$\endgroup$
3
$\begingroup$

Here goes a self answer.

To be honest, I almost decide to delete my post right after I posted. Because I naively thought unpacking may be unavoidable. Luckily, I keep this post, and this problem becomes more interesting. Thank you so much to @Carl Woll, @Sjoerd Smit and @Henrik Schumacher for providing great answers. Learned a lot.

Now, I summarize and add some benchmarks to other answers.

First, two related post on flatten or join pure list(not association)

https://mathematica.stackexchange.com/a/75592/4742 https://mathematica.stackexchange.com/a/184578/4742

these two post suggest us, we need to differentiate three cases:

  1. completely packed array
  2. completely unpacked array
  3. sublist packed array(unpacked at first level)

Briefly,

  1. for completely packed array, Flatten is much faster to Apply[Join], because Apply unpacked first level.
  2. for completely unpacked array, 'Apply[Join]` is faster, but timing is much closer than completely packed.
  3. for sublist packed array, Apply[Join] is much faster to Flatten

Before benchmark, we need routines to generated three kind of array

ClearAll[genCompletelyPacked];
genCompletelyPacked[sublistLen_, totalLen_] := ConstantArray[Range[sublistLen], totalLen];
ClearAll[genCompletelyUnpacked];
genCompletelyUnpacked[sublistLen_, totalLen_] := 
  Developer`FromPackedArray@genCompletelyPacked[sublistLen, totalLen];
ClearAll[genSublistPacked];
genSublistPacked[sublistLen_, totalLen_] := 
  Developer`ToPackedArray /@ genCompletelyUnpacked[sublistLen, totalLen];

and define below function (I add Catenate suggested by Mr.Wizard in other post)

f = Flatten[#, 1] &;
g = Join @@ # &;
h = Catenate[#] &;
Needs["GeneralUtilities`"];

Below for every case, I give two benchmark: one for small sublist, the other for long sublist.

complete packed array

BenchmarkPlot[{f, g, h}, genCompletelyPacked[10, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

enter image description here

BenchmarkPlot[{f, g, h}, genCompletelyPacked[1000, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

enter image description here

The jumping maybe due to memory issue as suggested by Michael E2.

completely unpacked array

BenchmarkPlot[{f, g, h}, genCompletelyUnpacked[10, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

enter image description here

BenchmarkPlot[{f, g, h}, genCompletelyUnpacked[1000, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

enter image description here

sublist packed array

BenchmarkPlot[{f, g, h}, genSublistPacked[10, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

enter image description here

BenchmarkPlot[{f, g, h}, genSublistPacked[1000, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

enter image description here

Now, we return to Association case:

As point out by Carl Woll, Merge simply put list together, and resulting sublist packed case that is unpacked at the first level(In this sense, unpacking is unavoidable in Merge, because first level is unpacked). So we can envisage, Apply[Join] will be much faster, however, we will see things getting a little different.

Sjoerd Smit suggested quite novel GeneralUtilitiesAssociationTransposewhich is even better, because it doesn't unpack at all, and we can give much hopeGeneralUtilitiesAssociationTranspose will be much faster. However, we will see this is not always the case.

First, we define routines to generate list of Association with values are packed list.

ClearAll[genAssoc];
genAssoc[len_, n_] := 
  Table[AssociationThread[{1, 2, 3} -> RandomReal[1., {3, len}]], n];

and several functions

f1 = Merge[#, Flatten] &;
f2 = Merge[#, Apply[Join]] &;
f3 = Merge[#, Catenate] &;
f4 = Flatten /@ GeneralUtilities`AssociationTranspose[#] &;

BenchmarkPlot[{f1, f2, f3, f4}, genAssoc[10, #] &, 
 PowerRange[10, 10^4, 2], "IncludeFits" -> True]

enter image description here

BenchmarkPlot[{f1, f2, f3, f4}, genAssoc[1000, #] &, 
 PowerRange[10, 10^4, 2], "IncludeFits" -> True]

enter image description here

you can clearly see some peculiarity as I pointed out previous. For example,

  1. AssociationTranspose is only good for small sublist.
  2. For small sublist, Flatten becomes comparable to Apply[Join] when number of association becomes large.

I have no answer, waiting other to explain.

$\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.