2
$\begingroup$

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

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.

$\endgroup$

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.