Efficient storage of large non-rectangular arrays

Question

I need to store in memory an array of the form

a=Table[Tuples[{1, 2, 3}, {n}], {n, 1, MaxLength}]

When MaxLength larger than - say - 20, this obviously results in an enormous array. In the ideal application, MaxLength is of the order of 30-40.

Is there a way to store arrays of this type more efficiently? In this example, the values 1,2,3 are the only ones that the array takes. Other arrays in my code would need to store floating-point variables rather than integers, with the same non-rectangular structure.

As a way of focusing the discussion, I am aware of two workarounds that would limit memory usage, but make the code significantly slower: I could generate in memory only the particular tuple n I need every time; or, I might store these elements in files on disk, and load in memory only the elements I need. Both solutions would slow down the code significantly - there are loops over n that access the elements of a.

Thank you.

Answer 1

Special case

Best way would be to not store this thing at all. It has so much structure that a[[i,j]] is cheaply computable on the fly. Integer and double arithmetic in the CPU are orders of magnitude faster than memory access.

Here is how to compute entries on the fly for the given example:

MaxLength = 5;
a = Table[Tuples[{1, 2, 3}, {n}], {n, 1, MaxLength}];
f[i_, j_] := IntegerDigits[j - 1, 3, i] + 1;

i = 5;
j = 26;

a[[i, j]] == f[i, j]

True

For more performance, we certainly want to have a compiled version of f.

cf = Compile[{{i, _Integer}, {j, _Integer}},
   Block[{x, r},
    x = j - 1;
    r = Table[0, {i}];
    Do[
     r[[-k]] = Mod[x, 3] + 1;
     x = Quotient[x, 3];
     , {k, 1, i}];
    r
    ],
   CompilationTarget -> "C",
   RuntimeAttributes -> {Listable},
   Parallelization -> True,
   RuntimeOptions -> "Speed"
   ];

Now this example shows that random indexing is not necessarily slower with the compiled function:

MaxLength = 15;
a = Table[Tuples[{1, 2, 3}, {n}], {n, 1, MaxLength}];
n = 1000000;
ilist = RandomInteger[{1, Length[a]}, n];
jlist = Developer`ToPackedArray@ Table[RandomInteger[{1, Length[a[[i]]]}], {i, ilist}];
idx = Transpose[{ilist, jlist}];

result = Extract[a, idx]; // AbsoluteTiming // First
result2 = cf[ilist, jlist]; // AbsoluteTiming // First
result == result2

0.427946

0.405359

True

General case

Of course, this won't work for less regular data. In general, the best you can do is to ensure that each element of a is a packed array. But maybe the data has some further structure that might be exploited? For example, a[[k]] could be the sampled values from a rather smooth function. In that case, one could employ an interpolation. Or if a[[k]] has mostly the same value (e.g. 0.), then SparseArray could be used. But it is hard to say anything without further details.