I am running calculations that will generate a list of lists of integers. Throughout the calculations, the number of lists will increase, and already-existing lists will be added to. What is the most efficient way to implement this for lists of arbitrary length without causing a bunch of slow list copies?

The following toy code illustrates the problem with random integers. Using AppendTo[] causes the lists to be copied over and over again. I will not know the number of lists or their lengths beforehand. The variable n will be set as high as I have enough virtual memory for.

EDIT: Just to be really clear, lists will be added and added-to constantly, after every iteration of my ongoing calculation.

a = {{}};
  j = RandomInteger[{1, Length[a]}];
  AppendTo[a[[j]], RandomInteger[9]];
  If[OddQ[j], AppendTo[a, {}]], {i, 1, n}];
  • 1
    $\begingroup$ This could be a problem for linked lists or a proper Reap and Sow algorithm. $\endgroup$
    – march
    Nov 10, 2016 at 22:04
  • 3
    $\begingroup$ Sow and Reap with tags. The tag will be the sublist index. $\endgroup$
    – Szabolcs
    Nov 10, 2016 at 22:04
  • 1
    $\begingroup$ You can have a look at Internal`Bag as well. $\endgroup$
    – user31159
    Nov 10, 2016 at 22:29

1 Answer 1


Credit goes to the people who suggested using Reap and sow. I just add the worked out example here for completeness sake.

Compared to

n = 100000; SeedRandom[1];
Timing[a = {{}};
 Do[j = RandomInteger[{1, Length[a]}];
  AppendTo[a[[j]], i];
  If[OddQ[j], AppendTo[a, {}]], {i, 1, n}];]    

{7.92485, Null}

n = 100000; SeedRandom[1];
Timing[ len = 1;
 Flatten /@  Part[Reap[Do[j = RandomInteger[{1, len}];
     Sow[i, j];
     If[OddQ[j], len++; Sow[ {}, len]];
     , {i, 1, n}]], 2]; ]    

{0.639604, Null}
is about 10 times faster.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.