Flattening large list of lists

Part of my code takes in list of lists of around 200 integers and produce a new list of lists. Following the approach in this post and this post, I created the new list using the linked list approach and Flatten it at the end.

So far the code runs fine, until I hit the mark when my list is of size $10^8$. There, the linked list is still produced (so the 32GB RAM is enough to at least store the list), however, flattening it caused Mathematica to run out of memory and the kernel quits.

Is there a better alternative to deal with this memory overhead? I tried Sow/Reap but they are extremely slow to even reach this progress. I am not sure if dividing the creation of the list into blocks will help (the data is created sequentially from the previous list)

Edit: The theoretical maximum of the list size is about $2∗10^8$, so it will be great if the solution can deal with that size as well.

The list of lists is not a matrix. Each row has different length. Also the whole list has to be sorted (with some custom defined function) so I at least need to keep the whole list in memory?

Edit: Sample data starts like:

{{49},
{49, 50},
{34, 49, 50},
{34, 49, 50, 69},
{34, 49, 50, 53, 69},
{34, 37, 49, 50, 53, 69},
{21, 34, 37, 49, 50, 53, 69},
{5, 21, 34, 37, 49, 50, 53, 69},
{34, 37, 49, 50, 53, 69, 118},
{21, 34, 37, 49, 50, 53, 69, 118},
{5, 21, 34, 37, 49, 50, 53, 69, 118},
{21, 34, 37, 38, 49, 50, 53, 69, 118},
{5, 21, 34, 37, 38, 49, 50, 53, 69, 118},
......
}


and I need to create a list that is roughly the size of the same order of magnitude, with some rows removed and some rows added, sequentially from the rows of the current list, and then sort it at the end.

• The theoretical maximum of the list size is about $2*10^8$, so it will be great if the solution can deal with that size as well. – Ivan Aug 5 '18 at 22:56
• What about AppendTo? – David G. Stork Aug 5 '18 at 22:59
• It is hard to answer without specifics... But since you seem to know the upper limit, can you preallocate a packed array of this lenght, and modify elements of that array? – Marius Ladegård Meyer Aug 5 '18 at 23:00
• Yeah, here some more questions: Is your list of lists a matrix? Does DeveloperPackedArrayQ applied to that list return True? – Henrik Schumacher Aug 5 '18 at 23:01
• This all is a bit abstract without a concrete example data set. But also try Join@@list. This should need less memory for ragged lists. If each of the sublists is an packed array, then also Join@@list should be a packed array. – Henrik Schumacher Aug 6 '18 at 0:00

Here is an approach that might or might not work, but at least the memory impact is small. I'm using InternalBag to store your linked list. With InternalStuffBag you can put your sublists into the bag; one after another. When you have done your computation, use InternalBagPart[bag,all] to extract your ragged list as normal Mathematica list. It seems in this step, no copying is done and the memory footprint is small.

Creating a function for returning random integer lists of different length around 200 and initializing your bag:

rand[] := With[{n = RandomInteger[{150, 250}]},
RandomInteger[1000, n]
];
bag = InternalBag[];


Measuring the current memory-in-use in MB with MemoryInUse[]/2^20. gives about 50MB. Now fill your bag with 10^5 lists

Do[InternalStuffBag[bag, rand[]], {10^5}]


After this, Mathematica has 220MB of memory in use. Getting the bag out as a normal list of lists

list = InternalBagPart[bag, All];


That adds only one MB of memory to the footprint. Without a concrete example, it is hard to give further advice, except that you should use Henrik's advice and ensure that your list of integers are indeed packed.

• I cannot change to a packed array? In[1]:=L=DeveloperToPackedArray[L] Out[1]= {{1},{1,2},{1,2,3}} In[2]:= DeveloperPackedArrayQ[L] Out[2]= False – Ivan Aug 6 '18 at 6:27
• @Ivan Note that I wrote "list of integers"! For your final list that contains lists of integers of different length, packing is not possible. So rather you should check if the sublists that only contain integers are indeed packed. – halirutan Aug 6 '18 at 6:29
• i see... sorry I am not familiar with the PackedArray` structure. Then the sublists are indeed packed. – Ivan Aug 6 '18 at 6:31
• At the end, this method passed through the flattening part. However, Mathematica Kernel still quits while trying to sort the resulting list... – Ivan Aug 7 '18 at 10:12