9
$\begingroup$

Most probably this is going to be a duplicate, sorry. I found too many questions/answers here about tree-like structures, and still could not locate what I want.

It is a followup of my previous question Clever caching of a recursively defined function; I've implemented that according to the very nice answer, but it sort of reached its limit, so now I want something more quick and memory efficient.

I need to compute lots of (integer) values of the form f[n,{a1,...,ak}] which depend on each other in a certain way, so I want to store the intermediate results. Seemingly an optimal way to do it would be a list {F[1],...,F[M]} where each F[n] is a tree-like structure, with F[n][a1] holding the value of f[n,{a1}], together with all F[n][a1][a2] for which f[n,{a1,a2,...}] have been computed, etc. There are several ways to do it that would be very fast at retrieval, but I am not sure how to achieve memory efficiency. I should use some nested Association or Dataset or what?

To be specific, here is what I actually want to compute:

stepreduce[{n_, a_, b_}] :=
 Which[
  b == {} \[Or] n == -1, {n, a, b},
  a == {} \[Or] First[a] < First[b], {n, b, a},
  First[a] == First[b], {If[n == 1, 0, -1], {}, {}},
  True, With[{d = First[a] - First[b], 
    r = Mod[First[b], First[a] - First[b]]},
   {n - First[b], Join[If[r == 0, {d}, {d - r, r}], Rest[a]], Rest[b]}
   ]
  ]

reduce[n_, a_, k_] := Most[FixedPoint[stepreduce, {n, a, {k}}]]

compute[n_, a_] := 
 If[n < 0, 0, 
  If[a == {}, If[n == 0, 1, Sum[compute[n, {k}], {k, n}]], 
   Sum[compute @@ reduce[n, a, k], {k, n}]]]

f[n_] := compute[n, {}]

Thus for example f[3] requires compute[3,{1}], compute[3,{2}] and compute[3,{3}], while compute[3,{1}] and compute[3,{3}] require compute[2,{1,1}], etc.

$\endgroup$
  • $\begingroup$ I'm not positive but suspect a nested Association would be a good way to proceed. Alternatively you might just set down values as you proceed e.g. compute[3,{1}]=intermediate allows you to have later access to compute[3,{1}] without needing to recompute it. $\endgroup$ – Daniel Lichtblau Sep 23 '18 at 15:33
  • $\begingroup$ @DanielLichtblau With the second alternative, there would be lots of redundant stuff in memory - e. g. keeping separately compute[n,{a,b,c,...,k,1}]=x1, compute[n,{a,b,c,...,k,2}]=x2,...,compute[n,{a,b,c,...,k,j}]=xj while I could have them gathered in something like F[[n]][a][b][c]...[k]=<|1->x1,2->x2,...,j->xj|>, this kind of thing... $\endgroup$ – მამუკა ჯიბლაძე Sep 23 '18 at 15:41
  • $\begingroup$ Roughly speaking, I would like to have each F[[n]] a rooted tree-like structure, with directed paths along (root)->a->b->c->...->k for all stored compute[n,{a,b,c,...,k}] ending in leaves holding the values of the latter. Of course this makes sense only if one can build such kind of structure economically memorywise $\endgroup$ – მამუკა ჯიბლაძე Sep 23 '18 at 15:50
  • $\begingroup$ How large are ns that you're interested in, and how much memory you have available? $\endgroup$ – jkuczm Sep 24 '18 at 13:21
  • $\begingroup$ @jkuczm Previously I managed to reach n=107 at a computer with 320 gb ram, but with a very primitive code - just kept in memory everything that was going on. Right now I only have 8 unfortunately but if I manage to optimize it well enough I can ask access there again - hoping to get to n=200. Mostly at this stage I need to study statistics/dynamics of function calls, so I can keep in memory only the part without which computations will go too slow. $\endgroup$ – მამუკა ჯიბლაძე Sep 24 '18 at 16:05
10
$\begingroup$

Simple memoization

There are few places where we can optimize code from OP.

Let's start with already mentioned in OP simplest memoization.

stepreduce // ClearAll
stepreduce@{n_, a_, b_} := Which[
  b == {} \[Or] n == -1,
    {n, a, b},
  a == {} \[Or] First@a < First@b,
    {n, b, a},
  First@a == First@b,
    {If[n == 1, 0, -1], {}, {}},
  True,
    With[{d = First@a - First@b, r = Mod[First@b, First@a - First@b]},
      {n - First@b, Join[If[r == 0, {d}, {d - r, r}], Rest@a], Rest@b}
    ]
]

reduce // ClearAll
reduce[n_, a_, k_] := Most@FixedPoint[stepreduce, {n, a, {k}}]

compute // ClearAll
compute[-1, {}] = 0;
compute[0, {}] = 1;
compute[n_, {}] := compute[n, {}] = Sum[compute[n, {k}], {k, n}]
compute[n_, a_] := compute[n, a] = Sum[compute @@ reduce[n, a, k], {k, n}]

f // ClearAll
f@n_ := compute[n, {}]

Let's gather time and memory usage of above function for calculating first 40 values.

results = <||>;

AppendTo[results, "DownValues memoization" -> Table[
  Internal`InheritedBlock[{compute}, Module[{res},
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ]],
  {i, 40}
]] // Last
(* {{1, 0.000074, 3984}, {2, 0.000121, 4208}, {6, 0.000284, 5136}, {14, 0.000663, 6680},
    {34, 0.001389, 8592}, {68, 0.003436, 11312}, {150, 0.010413, 15192}, {296, 0.014905, 21256},
    {586, 0.017695, 30344}, {1140, 0.025606, 44104}, {2182, 0.051756, 68168}, {4130, 0.072319, 93312},
    {7678, 0.121303, 136872}, {14368, 0.179369, 208728}, {26068, 0.286492, 297072}, {48248, 0.449439, 418840},
    {86572, 0.731423, 627224}, {158146, 1.17463, 878960}, {281410, 1.77709, 1298176}, {509442, 2.57542, 1811608},
    {901014, 4.01303, 2669760}, {1618544, 6.20318, 3717656}, {2852464, 9.20258, 5471776}, {5089580, 13.7751, 7606608},
    {8948694, 21.0816, 11174504}, {15884762, 31.8216, 15514256}, {27882762, 48.4341, 22760552}, {49291952, 71.3518, 31979744},
    {86435358, 108.607, 46273240}, {152316976, 159.118, 64178184}, {266907560, 229.416, 93926304}, {469232204, 337.286, 130198288},
    {821844316, 505.145, 190618272}, {1442300988, 745.747, 264372384}, {2525295380, 1108., 386819480}, {4426185044, 1607.57, 536494800},
    {7747801190, 2397.82, 784631984}, {13567867834, 3492.71, 1088333528}, {23745303556, 5196.81, 1591114776}, {41557384062, 7588.04, 2210837400}} *)

reduce compilation

Further speed-up can be gained by compiling reduce function.

We can see that, inside stepreduce, whenever a list can increase it's length, b list decreases it's length. Total length of a and b lists can't grow during reduce call. So we can start with single list $\{n, \, a_m, \, a_{m-1}, \, \ldots, \, a_1, \, b_1 = k\}$, keep track of length and positions of first elements of a and b lists, and of "direction" in which possible change in positions of first elements will move. This way we can perform all steps of reduce without memory reallocation.

Since compiled function can't return ragged arrays, we'll move around single list na containing n as first element and reversed a list as rest of elements.

reduce // ClearAll
reduce = Hold@Compile[{{na, _Integer, 1}, {k, _Integer}},
  Module[{n, aPos, aLen, bPos, bLen, posDelta, nab},
    n = na[[1]];
    aPos = Length@na;
    aLen = aPos - 1;
    bLen = 1;
    bPos = aPos + 1;
    posDelta = 1;
    nab = Append[na, k];
    While[True,
      Which[
        bLen < 1 || n === -1,
          Break[],
        aLen < 1  || nab[[aPos]] < nab[[bPos]],
          With[{aLenOld = aLen, aPosOld = aPos},
            aLen = bLen;
            bLen = aLenOld;
            aPos = bPos;
            bPos = aPosOld;
            posDelta = -posDelta;
          ],
        nab[[aPos]] === nab[[bPos]],
          n = If[n === 1, 0, -1];
          aLen = 0;
          Break[],
        True,
          Module[{bFirst, d, r},
            bFirst = nab[[bPos]];
            d = nab[[aPos]] - bFirst;
            r = Mod[bFirst, d];
            n = n - bFirst;
            If[r === 0,
              nab[[aPos]] = d;
            (* else *),
              nab[[aPos]] = r;
              aPos += posDelta;
              nab[[aPos]] = d - r;
              ++aLen;
            ];
            bPos += posDelta;
            --bLen;
          ]
      ];
    ];
    If[posDelta === -1,
      Module[{max, reverseMax},
        max = Length@nab + 2;
        reverseMax = Quotient[max - 1, 2];
        If[aLen + 1 < reverseMax, reverseMax = aLen + 1];
        Do[
          With[{tmp = nab[[i]], j = max - i},
            nab[[i]] = nab[[j]];
            nab[[j]] = tmp;
          ];,
          {i, 2, reverseMax}
        ]
      ]
    ];
    nab[[1]] = n;
    Take[nab, aLen + 1]
  ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
] /.
  Part -> Compile`GetElement //. HoldPattern[Compile`GetElement@x__ = y_] :> (Part@x = y) //.
  HoldPattern[Plus][pre___, x_, HoldPattern[Times][-1, y_], post___] :> Plus[pre, Subtract[x, y], post] //
  ReleaseHold // Last;

compute // ClearAll
compute@{-1} = 0;
compute@{0} = 1;
compute@na_ := compute@na = With[{n = First@na},
  If[Length@na === 1,
    Sum[compute@{n, k}, {k, n}]
  (* else *),
    Sum[compute@Developer`FromPackedArray@reduce[na, k], {k, n}]
  ]
]

f // ClearAll
f@n_ := compute@{n}

Again time and memory usage:

AppendTo[results, "DownValues memoization + compilation" -> Table[
  Internal`InheritedBlock[{compute}, Module[{res},
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ]],
  {i, 40}
]] // Last
(* {{1, 0.000063, 2832}, {2, 0.000078, 4136}, {6, 0.000091, 5424}, {14, 0.00017, 6720},
    {34, 0.000332, 9376}, {68, 0.000605, 11616}, {150, 0.001157, 15024}, {296, 0.001871, 21344},
    {586, 0.003039, 29936}, {1140, 0.005082, 43944}, {2182, 0.007769, 62952}, {4130, 0.011655, 92952},
    {7678, 0.014263, 136368}, {14368, 0.023007, 195168}, {26068, 0.033489, 287104}, {48248, 0.050387, 408872},
    {86572, 0.075441, 598824}, {158146, 0.101385, 850560}, {281410, 0.140992, 1241104}, {509442, 0.211831, 1820328},
    {901014, 0.32101, 2612696}, {1618544, 0.460999, 3660608}, {2852464, 0.680271, 5414824}, {5089580, 1.19728, 7549832},
    {8948694, 1.50457, 11118344}, {15884762, 2.29116, 15459152}, {27882762, 3.47475, 22708256}, {49291952, 4.49639, 31527560},
    {86435358, 6.61805, 46235728}, {152316976, 9.90871, 64156608}, {266907560, 14.3602, 93992544}, {469232204, 19.7709, 130377928},
    {821844316, 29.5902, 190884312}, {1442300988, 42.7437, 264764776}, {2525295380, 62.8208, 387425584}, {4426185044, 92.3726, 537406200},
    {7747801190, 130.204, 786031768}, {13567867834, 183.552, 1090416752}, {23745303556, 267.809, 1594242360}, {41557384062, 391.204, 2211848640}} *)

Caching in a tree

As noted by OP different a lists share many elements, so it might be more memory efficient to store result in a specially constructed tree.

While Associations offer fast appending and random access they're also pretty memory hungry, so might not be the best choice for this memory constrained problem.

Instead I propose to use the fact that "ordinary" compound Mathematica expression is a tree, so we can keep results in an expression such that our na list will be position of either result, or of sub-expression having result as it's head.

Such expression offers fast random access, but appending to a node of $k$ elements is $\mathcal O(k)$ operation. Since nodes won't have more than n elements, this shouldn't have huge performance impact.

integerTreeResizeStep = Function[,
  With[{node = #1},
    Which[
      IntegerQ@node,
        #1 = Array[-1&, #2, 1, node],
      Length@node < #2,
        #1 = Join[node, Array[-1&, #2 - Length@node, 1, Head@node]]
    ];
  ];
  Unevaluated@Unevaluated@#1[[#2]]
  ,
  HoldFirst
];
integerTreeGetOrSetLeaf = Function[{tree, path, value},
  Module[{val},
    val = Quiet@Check[
      Extract[tree, path]
      ,
      Fold[integerTreeResizeStep, Unevaluated@tree, path];
      -1
    ];
    If[Not@IntegerQ@val, val = Head@val];
    If[val < 0,
      val = value;
      If[IntegerQ@Extract[tree, path],
        tree[[Sequence @@ path]] = val
      (* else *),
        tree[[Sequence @@ path, 0]] = val
      ];
    ];
    val
  ],
  HoldAll
];

$cache = {};

compute // ClearAll
compute@{-1} = 0;
compute@{0} = 1;
compute@na_ := integerTreeGetOrSetLeaf[$cache, na,
  With[{n = First@na},
    If[Length@na === 1,
      Sum[compute@{n, k}, {k, n}]
    (* else *),
      Sum[compute@reduce[na, k], {k, n}]
    ]
  ]
]

Time and memory usage:

AppendTo[results, "Tree cache + compilation" -> Table[
  Module[{res},
    $cache = {};
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ],
  {i, 40}
]] // Last
(* {{1, 0.000261, 10176}, {2, 0.000286, 14008}, {6, 0.000478, 17800}, {14, 0.000841, 21712},
    {34, 0.001428, 25624}, {68, 0.002476, 29536}, {150, 0.003977, 33448}, {296, 0.006287, 37360},
    {586, 0.00936, 41272}, {1140, 0.014786, 45184}, {2182, 0.022635, 49096}, {4130, 0.034472, 53016},
    {7678, 0.051892, 56920}, {14368, 0.078604, 60840}, {26068, 0.118647, 64744}, {48248, 0.177518, 68664},
    {86572, 0.25746, 81520}, {158146, 0.381425, 98904}, {281410, 0.558052, 131784}, {509442, 0.816168, 167584},
    {901014, 1.19629, 232680}, {1618544, 1.73458, 305024}, {2852464, 2.53002,  434480}, {5089580, 3.64807, 580352},
    {8948694, 5.27007, 838488}, {15884762, 7.58268, 1130824}, {27882762, 10.9998, 1646504}, {49291952, 15.8523, 2231320},
    {86435358, 23.3352, 3261424}, {152316976, 33.9201, 4431688}, {266907560, 47.8143, 6489776}, {469232204, 69.2132, 8828752},
    {821844316, 99.1624, 12943664}, {1442300988, 143.114, 17620240}, {2525295380, 207.741, 25844920}, {4426185044, 293.7, 35193936},
    {7747801190, 432.95, 51638240}, {13567867834, 618.074, 70324968}, {23745303556, 887.757, 103203720}, {41557384062, 1258.96, 140563328}} *)

Sharing nodes

If we examine our $cache we'll see that there's large percentage of nodes containing only zeros. Especially common are nodes that can be created by prepending flat zero node to itself.

Table[Count[$cache, Nest[Prepend[#, #] &, 0 @@ ConstantArray[0, j], i - 1], Infinity], {i, 20}, {j, 40 - 2 i}] // TableForm
Total[%, 2]
(* 2041389 *)

We can reduce memory usage by making sure that, in our cache tree, same zero nodes are internally stored as pointers to single expressions, not as copies of this expression.

We can do this by keeping zero node expressions cached, e.g. as down values of zeroNode symbol. When zero is added to cache tree, we can test whether containing it node is of our special form, if so we can replace it with cached version.

zeroNode // ClearAll
zeroNode[1, _] = 0;
zeroNode[2, i_] := zeroNode[2, i] = 0 @@ ConstantArray[0, i];
zeroNode[depth_, i_] := zeroNode[depth, i] = Prepend[zeroNode[depth - 1, i], zeroNode[depth - 1, i]]

integerTreeOptimizeZeroNode = Function[{tree, path},
  Module[{newPath = Most@path, node, cached},
    node = Extract[tree, newPath];
    cached = zeroNode[Depth@node, Count[node, 0]];
    While[node === cached,
      tree[[Sequence @@ newPath]] = cached;
      newPath = Most@newPath;
      node = Extract[tree, newPath];
      cached = zeroNode[Depth@node, Count[node, 0]]
    ];
  ]
  ,
  HoldFirst
];
integerTreeGetOrSetLeaf = Function[{tree, path, value},
  Module[{val},
    val = Quiet@Check[
      Extract[tree, path]
      ,
      Fold[integerTreeResizeStep, Unevaluated@tree, path];
      -1
    ];
    If[Not@IntegerQ@val, val = Head@val];
    If[val < 0,
      val = value;
      If[IntegerQ@Extract[tree, path],
        tree[[Sequence @@ path]] = val
      (* else *),
        tree[[Sequence @@ path, 0]] = val
      ];
      If[val === 0, integerTreeOptimizeZeroNode[tree, path]]
    ];
    val
  ],
  HoldAll
];

Time and memory usage:

AppendTo[results, "Tree cache + compilation + shared nodes" -> Table[
  Internal`InheritedBlock[{zeroNode}, Module[{res},
    $cache = {};
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ]],
  {i, 40}
]] // Last
(* {{1, 0.000206, 10736}, {2, 0.000256, 14848}, {6, 0.000448, 18920}, {14, 0.000858, 23112},
    {34, 0.001798, 27304}, {68, 0.003416, 31496}, {150, 0.007841, 35688}, {296, 0.014545, 39880},
    {586, 0.019235, 44072}, {1140, 0.017669, 48264}, {2182, 0.029496, 52456}, {4130, 0.042167, 56656},
    {7678, 0.064716, 60840}, {14368, 0.098059, 65040}, {26068, 0.137533, 69224}, {48248, 0.198948, 73424},
    {86572, 0.297026, 77608}, {158146, 0.440113, 86200}, {281410, 0.645397, 97752}, {509442, 0.945092, 115080},
    {901014, 1.39239, 128512}, {1618544, 2.01232, 159560}, {2852464, 3.04968, 180984}, {5089580, 4.37024, 237376},
    {8948694, 6.2295, 263520}, {15884762, 8.86484, 367256}, {27882762, 12.9779, 413672}, {49291952, 18.4895, 610232},
    {86435358, 27.0952, 674016}, {152316976, 39.3753, 1047472}, {266907560, 57.412, 1176016}, {469232204, 81.8548, 1901088},
    {821844316, 119.4, 2092472}, {1442300988, 170.801, 3499760}, {2525295380, 246.583, 3889176}, {4426185044, 355.022, 6659784},
    {7747801190, 516.578, 7312040}, {13567867834, 731.325, 12764352}, {23745303556, 1059.77, 14108216}, {41557384062, 1592.29, 24914200}} *)

Iterative version

Let's gather data on a lists used after calculating f@n's for subsequent ns from 1 to nMax.

$cache = {};
$cacheHistory = Table[f@n; $cache, {n, 40}];

Set of a lists can be generated from cache element by taking Positions and deleting trailing zeros, for example 4th cache element after calculating f@n's up to 7 contains values calculated for following a lists:

Sort[Internal`DeleteTrailingZeros /@ Position[$cacheHistory[[7, 4]], _Integer]]
(* {{}, {1}, {2}, {3}, {4}, {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {3, 1},
    {1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {1, 1, 1, 1}} *)

In a lists we get from $cacheHistory we can notice that, for given nMax and n, last elements of a lists are all integers from 1 to n, and remaining elements form all compositions of all numbers from 0 to Min[n - last, nMax - n].

Let's check this for all calculated $cacheHistory elements, i.e. up to 40:

And @@ Flatten@Table[
  SameQ[
    Sort[Internal`DeleteTrailingZeros /@ Position[$cacheHistory[[nMax, n]], _Integer]],
    Table[
      Append@last /@ Join @@ Permutations /@ IntegerPartitions@totMost,
      {last, n},
      {totMost, 0, Min[n - last, nMax - n]}
    ] // Flatten[#, 2]& // Prepend@{} // Sort
  ],
  {nMax, 40},
  {n, nMax}
]
(* True *)

Proving whether above observation is true for arbitrary large ns is left as an exercise for the reader.

Assuming that it is true, we can replace our recursive function with explicit iteration in which we can sequentially pre-compute all necessary cache elements for given n.

In recursive version absence of element in cache meant that it was not yet calculated and needs to be calculated when requested. In iterative version we know (given our above assumption) that when cache element is requested it was already calculated, so we can use absence of element in cache as sign that its calculation resulted in some chosen default cache value. This way, by not storing this default value in our cache (except when it's needed to fill space up to last non-default value in a node), we can reduce cache size.

Most common value in cache is zero, so we choose it as our default.

nextNA = Hold@Compile[{{prev, _Integer, 1}},
  Module[{prevLen, nextLen, next},
    prevLen = Length@prev;
    nextLen = prevLen + prev[[prevLen - 1]] - 2;
    next = Table[1, nextLen];
    Do[next[[i]] = prev[[i]];, {i, prevLen - 3}];
    next[[prevLen - 2]] = prev[[prevLen - 2]] + 1;
    If[nextLen >= prevLen, next[[prevLen - 1]] = 1];
    next
  ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
] /.
  Part -> Compile`GetElement //. HoldPattern[Compile`GetElement@x__ = y_] :> (Part@x = y) //.
  HoldPattern[Plus][pre___, x_, HoldPattern[Times][-1, y_], post___] :> Plus[pre, Subtract[x, y], post] //
  ReleaseHold // Last;

$cache = {};

cacheResizeStep = Function[,
  With[{node = #1},
    Which[
      IntegerQ@node,
        #1 = Array[0&, #2, 1, node],
      Length@node < #2,
        #1 = Join[node, Array[0&, #2 - Length@node, 1, Head@node]]
    ];
  ];
  Unevaluated@Unevaluated@#1[[#2]]
  ,
  HoldFirst
];

cacheGet // ClearAll
cacheGet@{-1} = 0;
cacheGet@{0} = 1;
cacheGet@na_ := Quiet@Check[Replace[Extract[$cache, na], node: Except@_Integer :> Head@node], 0]

cacheSet = With[{val = Sum[cacheGet@reduce[#, k], {k, First@#}]},
  If[val =!= 0,
    Fold[cacheResizeStep, Unevaluated@$cache, #];
    $cache[[Sequence @@ #]] = val
  ]
]&;

preCompute = With[{oldN = Length@$cache},
  Do[
    If[nn > oldN, Do[cacheSet@{nn, last}, {last, nn}]];
    Do[
      Module[{na = ConstantArray[1, tot + 2]},
        na[[1]] = nn;
        Do[
          Do[
            na[[-1]] = last;
            cacheSet@na
            ,
            {last, nn - tot}
          ];
          na = nextNA@na;
          ,
          2^(tot - 1)
        ]
      ],
      {tot, Max[oldN - nn + 1, 1], Min[nn, # - nn]}
    ];
    If[nn > oldN, $cache[[nn, 0]] = Sum[cacheGet@{nn, k}, {k, nn}]]
    ,
    {nn, Ceiling[oldN, 2] / 2 + 1, #}
  ]
]&;

f // ClearAll
f@n_ := (preCompute@n; $cache[[n, 0]])

Time and memory usage:

AppendTo[results, "Tree cache + compilation + iterative" -> Table[
  Module[{res},
    $cache = {};
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ],
  {i, 40}
]] // Last
(* {{1, 0.000238, 5152}, {2, 0.000694, 5264}, {6, 0.00071, 6768}, {14, 0.001154, 6888},
    {34, 0.002287, 7136}, {68, 0.003436, 7424}, {150, 0.006044, 7808}, {296, 0.009524, 8304},
    {586, 0.014249, 8896}, {1140, 0.021613, 9792}, {2182, 0.029021, 10848}, {4130, 0.045345, 12544},
    {7678, 0.051793, 14144}, {14368, 0.055507, 17112}, {26068, 0.08087, 20016}, {48248, 0.106901, 25048},
    {86572, 0.146255, 29152}, {158146, 0.216362, 37416}, {281410, 0.320636, 44344}, {509442, 0.479902, 58144},
    {901014, 0.601251, 68120}, {1618544, 0.849296, 91216}, {2852464, 1.21726, 108184}, {5089580, 1.72727, 145896},
    {8948694, 2.46205, 169600}, {15884762, 3.51142, 228200}, {27882762, 5.0261, 267120}, {49291952, 7.33004, 361400},
    {86435358, 10.3712, 416728}, {152316976, 14.6958, 567296}, {266907560, 21.4333, 658512}, {469232204, 32.6764, 890880},
    {821844316, 44.3283, 1017496}, {1442300988, 62.5927, 1376632}, {2525295380, 89.3019, 1578752}, {4426185044, 127.182, 2138352},
    {7747801190, 183.395, 2425000}, {13567867834, 261.899, 3297264}, {23745303556, 378.116, 3757568}, {41557384062, 533.63, 5084384}} *)

Comparisons

Let's check that all methods gave same results

SameQ @@ results[[All, All, 1]]
(* True *)

and compare their time and memory usage

ReplacePart[First@#, 1 -> GraphicsGrid[List /@ #[[All, 1]]]] &@(
  ListLogPlot[results[[All, All, First@#]], AxesLabel -> Last@#] & /@
    {2 -> "Time [s]", 3 -> "Memory [B]"}
)

time and memory usage comparison

We can see that simplest DownValues memoization has highest memory usage, regardless of compilation. DownValues memoization with compilation is fastest as long as we have enough memory. Iterative tree cache has lowest memory usage and, with compiled reduce, is only slightly slower than fastest variant.

Further optimizations might require rewriting in lower level language. But since this algorithm is not using any sophisticated high level Mathematica functionality, it should be doable.

$\endgroup$
  • 2
    $\begingroup$ Very nice work (and I got to be the first to upvote-- hope there are more to follow). $\endgroup$ – Daniel Lichtblau Oct 4 '18 at 14:22
  • 1
    $\begingroup$ Well I am overwhelmed. What can I say? Thank you, thank you! Thank you for sharing so much of your time, effort, and expertise. There were several cases when I received much help from the SE network but this is something truly exceptional. I'll never forget this, and I'll be never able to thank you appropriately. The word that comes to mind is grace... $\endgroup$ – მამუკა ჯიბლაძე Oct 4 '18 at 16:08
  • $\begingroup$ Reached i=46 with the last version in less than 4 hours! One question: why do you clear $cache for each i inside the cycle? Without it, for e. g. i=40 I had {41557384062, 486.9017940141061, 22046688} (you show {41557384062, 1460.39, 48706960}) $\endgroup$ – მამუკა ჯიბლაძე Oct 5 '18 at 3:00
  • $\begingroup$ One more question - your zero nodes confuse me. Say, $cache[[7]]//TreeForm shows lots of zero-only branches. Should they be there? I thought what you do is that since everything below a zero in the (downwards growing) tree consists of zeroes only, you (1) moving down along some path, as soon as you encounter zero you return it without moving any further; (2) you don't keep track of anything below a zero. But you seem to do something different. What is it? And why? $\endgroup$ – მამუკა ჯიბლაძე Oct 5 '18 at 4:06
  • $\begingroup$ Sorry, one more thing. When monitoring, I see that after a while ByteCount[$cache] begins to exceed MemoryInUse[]. How can this be?? $\endgroup$ – მამუკა ჯიბლაძე Oct 5 '18 at 4:43

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.