20
$\begingroup$

Err.. Often I met the situation to join lists at the first level and I used to just Flatten[#, 1] & @ them. However, I found (when glance over the mathematica.stackexchange.com) someone else prefers Join @@ # &. They are equal in output when the inputs are {list1, list2, ...listn}, so I wonder if there are any differences in efficiency. Define:

f := Flatten[#, 1] &; g = Join @@ # &;

and the test lists:

lists = Table[ConstantArray[{1, 2}, 2^n], {n, 1, 22}];

test:

ftime = AbsoluteTiming[f@#;] & /@ lists;
gtime = AbsoluteTiming[g@#;] & /@ lists;

with output:

{{0., Null}, {0., Null}, {0., Null}, {0., Null}, {0., Null}, {0., 
Null}, {0., Null}, {0., Null}, {0., Null}, {0., Null}, {0., 
Null}, {0.001000, Null}, {0.007000, Null}, {0.004000, 
Null}, {0.007000, Null}, {0.015001, Null}, {0.030002, 
Null}, {0.062004, Null}, {0.138008, Null}, {0.266015, 
Null}, {0.529030, Null}, {1.053060, Null}}(*ftime*)

{{0., Null}, {0., Null}, {0., Null}, {0., Null}, {0., Null}, {0., 
Null}, {0., Null}, {0., Null}, {0., Null}, {0., Null}, {0.001000, 
Null}, {0., Null}, {0.004000, Null}, {0.003000, Null}, {0.006000, 
Null}, {0.013001, Null}, {0.026002, Null}, {0.052003, 
Null}, {0.102006, Null}, {0.204012, Null}, {0.428024, 
Null}, {0.845048, Null}}(*gtime*)

plot:

ListLinePlot[{Log10 /@ ftime[[All, 1]], Log10 /@ gtime[[All, 1]]}, 
Frame -> True, 
FrameTicks -> {Table[{2 n, 2^(2 n)}, {n, 0, 27}], 
Table[{n, NumberForm[10^n, 3]}, {n, -10, 27, 0.4}]}, ImageSize -> 600, 
PlotLegends -> {f, g}]

enter image description here

seems Join @@ # & approach is slightly faster...

Then my questions are:

  1. is Join @@ # & approach always faster?

  2. why there is a peak in length-time plot at around length ~ $ 2^{13} $?

$\endgroup$
1
  • 1
    $\begingroup$ You might like also to consider the case of packed arrays (use Range[2] in place of {1,2} in your lists) $\endgroup$ Feb 21, 2015 at 13:45

1 Answer 1

13
$\begingroup$

Here's a V10 comparison.

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

With packed arrays, also suggested by Simon Woods:

BenchmarkPlot[{f, g}, ConstantArray[Range[2], #] &, 
 PowerRange[10, 1*^7, 2], "IncludeFits" -> True]

Mathematica graphics

With the OP's original arrays.

BenchmarkPlot[{f, g}, ConstantArray[{1, 2}, #] &, 
 PowerRange[10, 1*^7, 2], "IncludeFits" -> True]

Mathematica graphics

The main advantage of Flatten with packed arrays is that Apply unpacks the first level, which accounts for much of the difference in time. On unpacked arrays Apply performs better on arrays of length of about 100 or greater. The little jump in the timing of Flatten is consistently around 8000 - 10000 as observed by the OP. If the base array is lengthened by a factor of ten, we see that the jump is around 800, so perhaps it is memory related. (If so, then the jump might vary by system. I'm on a MacBook Pro, i7 2.7GHz.) It will probably take knowledge of the internal workings of Flatten to answer the question.

BenchmarkPlot[{f, g}, 
 ConstantArray[
  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, #] &,
 PowerRange[10, 2*^6, 2], 
 "IncludeFits" -> True]

Mathematica graphics

$\endgroup$
3
  • 3
    $\begingroup$ Please add Catenate to this answer, or I shall post a separate one. $\endgroup$
    – Mr.Wizard
    Feb 10, 2016 at 19:46
  • $\begingroup$ Looks like I forgot about this (comment above), but still I think it should be done. $\endgroup$
    – Mr.Wizard
    Nov 11, 2019 at 14:08
  • 1
    $\begingroup$ @Mr.Wizard Me, too. I think BenchmarkPlot was broken at the time, or at least I recall having trouble with it. Works now in V12, with different labels than above. I've run it with Catenate. Not sure when I'll have time to post. i.stack.imgur.com/sZhvp.png $\endgroup$
    – Michael E2
    Nov 11, 2019 at 14:29

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.