18
$\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 prefer Join @@ # &. They are equal in output when the inputs are {list1,list2,...listn}, so I wonder if there are difference 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 lengh-time plot at around length~2^13?

$\endgroup$
  • 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$ – Simon Woods Feb 21 '15 at 13:45
12
$\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$
  • 2
    $\begingroup$ Please add Catenate to this answer, or I shall post a separate one. $\endgroup$ – Mr.Wizard Feb 10 '16 at 19:46

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.