# How to efficiently manage lists of arbitrary length?

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.

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

• This could be a problem for linked lists or a proper Reap and Sow algorithm. – march Nov 10 '16 at 22:04
• Sow and Reap with tags. The tag will be the sublist index. – Szabolcs Nov 10 '16 at 22:04
• You can have a look at InternalBag as well. – user31159 Nov 10 '16 at 22:29

## 1 Answer

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;
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;
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.