2
$\begingroup$

I have the following simple code

finalList = {};
For[i = 1, i <= myN - 3, i++,
 For[j = i + 1, j <= myN - 2, j++,
  For[k = j + 1, k <= myN - 1, k++,
   l = RandomInteger[{k + 1, myN}];
   AppendTo[finalList, {i, j, k, l}];
   ]
  ]
 ] // Timing

for some value of myN I obtain the following execution times

30 0.056
40 0.356
50 1.436
60 4.296
70 12.083
80 43.012
90 116.903

that grow much faster than N^3 (it's about N^6 for the first point and it is increasing for the last two points), and I cannot understand why.

Any insight of why this happens?

$\endgroup$
3
  • 2
    $\begingroup$ It is good to add one sentence what you code is eactly doing. People here don't remember anymore what nested Fors are doing :). p.s. Take a look at $3.2 about AppendTo performance. You may also be interested in alternatives to procedural loops. $\endgroup$ – Kuba Mar 28 '14 at 11:40
  • 4
    $\begingroup$ Don't use AppendTo, it is very very slow use Sow and Reap. And yes as @Kuba hinted at don't use For loops. $\endgroup$ – Matariki Mar 28 '14 at 11:45
  • 1
    $\begingroup$ At the end: Tuples, Subsets and friends are quite fast when creating similar lists. $\endgroup$ – Kuba Mar 28 '14 at 11:47
6
$\begingroup$

To demonstrate the time saving using a linked list instead of AppendTo :-

time1[myN_] := First@Timing[
  finalList = {};
  For[i = 1, i <= myN - 3, i++,
   For[j = i + 1, j <= myN - 2, j++,
    For[k = j + 1, k <= myN - 1, k++,
     l = RandomInteger[{k + 1, myN}];
     AppendTo[finalList, {i, j, k, l}]]]]];

time2[myN_] := First@Timing[
   finalList = {};
   For[i = 1, i <= myN - 3, i++,
    For[j = i + 1, j <= myN - 2, j++,
     For[k = j + 1, k <= myN - 1, k++,
      l = RandomInteger[{k + 1, myN}];
      finalList = {finalList, {i, j, k, l}}]]];
   finalList = Partition[Flatten@finalList, 4]];

ListLinePlot[
 {Map[time1, {30, 40, 50, 60, 70, 80, 90}],
  Map[time2, {30, 40, 50, 60, 70, 80, 90}]},
InterpolationOrder -> 2, PlotStyle -> Thick]

enter image description here

$\endgroup$
2
  • $\begingroup$ Thanks, time2 is now much similar to a cubic function in the size myN. It's just that is very strange to make a function just to do one thing, but then it is so slow that is better to not use it! $\endgroup$ – psmith Mar 28 '14 at 13:09
  • 1
    $\begingroup$ Probably ListLogPlot[%, Joined -> True] in order to see both traces? $\endgroup$ – rhermans Mar 28 '14 at 13:49

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.