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.

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?

share|improve this question
2  
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. –  Kuba Mar 28 at 11:40
4  
Don't use AppendTo, it is very very slow use Sow and Reap. And yes as @Kuba hinted at don't use For loops. –  Matariki Mar 28 at 11:45
1  
At the end: Tuples, Subsets and friends are quite fast when creating similar lists. –  Kuba Mar 28 at 11:47

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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! –  Fabrizio Mar 28 at 13:09
1  
Probably ListLogPlot[%, Joined -> True] in order to see both traces? –  rhermans Mar 28 at 13:49

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.