Efficient List of Lists

Question

I'm running some analysis that requires the creation, row by row, of a large list of lists. The big list is called "Nodes" and it will ultimately contain hundreds of thousands of rows. The first few rows will look like this ...

Row 1: {{1,3,5}, {2,4,6}, {7}, {6,7,8,9}}

Row 2: {{7,3,8}, {2,5,4}, {2}, {6,2,8,4}}

Row 3: {{9,7,5}, {5,4,6}, {1}, {6,7,8,9}}

I've tried AppendTo and Join in this way ...

Nodes = AppendTo[Nodes,List[{8,3,2},{1,2,3},{8},{8,3,3,2}]];

Nodes = Join[Nodes,List[{8,3,2},{1,2,3},{8},{8,3,3,2}]];

and they both take quite a long time to run.

I also tried creating a huge Nodes array ahead of time and then replacing each row, something like this ...

Nodes = Range[200000];
For[ji = 1, ji < 200001, ji++, Nodes[[ji]] = List[{}, {}, {}, {}]];

followed by

Nodes[[nodesrownumber]] = List[{8,3,2},{1,2,3},{8},{8,3,3,2}]];

and this seems to take even longer.

Any suggestions for improving the speed of this? Thanks, very much, in advance.

Answer 1

One approach is to construct the rows with a head other than list, say row, then accumulate the rows as a linked list, and finally transform the linked list into a simple list of sublists of the form wanted. Here is an example.

Row constructor.

 newRow[] := 
   With[{rs = RandomSample[Range[11]]},
     row[rs[[;; 3]], rs[[4 ;; 6]], {rs[[7]]}, rs[[8 ;;]]]]

On my system, a not very fast, aging iMac, I get the following timing for making a table of 100000 rows as I described.

timer[n_] :=
  Module[{data = {}},
   AbsoluteTiming[
     Do[data = {data, newRow[]}, {n}];
     List @@@ Flatten@data][[1]]]

timer[100000]

0.866738

That's less than a second for a 100000 rows, so maybe it will be fast enough for you.

And just to show that the process actually produces the structures described, consider

Module[{data = {}},
  Do[data = {data, newRow[]}, {3}];
  Column[{data, List @@@ Flatten@data}]]

Answer 2

Maybe there's something I do not understand because this seems fast to me. I used Do instead of For, since it is faster:

(nodes = ConstantArray[0, {200000}];
  Do[
   nodes[[ji]] = List[{8, 3, 2}, {1, 2, 3}, {8}, {8, 3, 3, 2}],
   {ji, 200000}];) // AbsoluteTiming
(*  {0.13, Null}  *)

But it's not even twice as fast as For:

(nodes = ConstantArray[0, {200000}];
  Block[{ji},
   For[ji = 1, ji < 200001, ji++,
    nodes[[ji]] = List[{8, 3, 2}, {1, 2, 3}, {8}, {8, 3, 3, 2}]
    ]];) // AbsoluteTiming
(*  {0.246, Null}  *)

If the calculation of a row can be done independently, either as a function of some parameters or none, then Table will be faster still:

calcrow[i] := List[{8, 3, 2}, {1, 2, 3}, {8}, {8, 3, 3, 2}];
(nodes = Table[
     calcrow[i],
     {i, 200000}];) // RepeatedTiming
(*  {0.086, Null}  *)

nextrow[] := List[{8, 3, 2}, {1, 2, 3}, {8}, {8, 3, 3, 2}];
(nodes = Table[
     nextrow[],
     {i, 200000}];) // RepeatedTiming
(*  {0.018, Null}  *)

Some baseline comparisons for iteration and memory storage:

(* all 1's *)
(#[1, {200000}] // RepeatedTiming // First) & /@ {Do, Table, ConstantArray}
(*  {0.0031, 0.0034, 0.0000663}  *)

(* rows of 11 elements *)
(#[Evaluate@ Internal`PartitionRagged[Range@11, {3, 3, 1, 4}], {200000}] // 
     RepeatedTiming // First) & /@ {Table, ConstantArray}
(*  {0.0062, 0.0012}  *)

Notes: Do does not produce a table, so it gives some idea of a lower bound on iteration. ConstantArray is a rather specialized & optimized table-generator; timings with Table probably reflects the lower bound in generating a table.