A long time ago, I wrote a note about how to do this with DownValues. Since then, we got Association
, which is a much better data structure for caching. MaTeX uses it for its cache (see the store
function in MaTeX.m
).
Here's a very small example of how we can do this. I tied this cache to a single function, and used a recursive Fibonacci for illustration. A nice implementation could auto-memoize any function. Perhaps someone else will show this in another answer.
You asked to remove only those values from the cache which aren't used often. Instead, I will remove those which were not used recently. To achieve this, I use AppendTo
to add to the association, and do this even if the value was already present. The effect is that the value will be moved to the end of the association. Then we remove elements from the beginning only. Note that AssociateTo
is a faster way to update associations, but it does not change the order of keys.
asc = <|"a" -> 1, "b" -> 2|>
(* <|"a" -> 1, "b" -> 2|> *)
AssociateTo[asc, "a" -> 1]; // RepeatedTiming
(* {7.3*10^-7, Null} *)
AppendTo[asc, "a" -> 1]; // RepeatedTiming
(* {1.235*10^-6, Null} *)
Here's the implementation of a recursive Fibonacci with caching, and a limit on the cache size.
Clear[asc, get, store, fib, limit];
(* cache storage *)
asc = <||>;
(* retrieve value *)
get[n_] :=
store[n]@Lookup[asc, Key[n], fib[n]]
limit = 10; (* max number of entries in cache *)
(* store value; we always do this, even if the value was known, to update the ordering *)
store[n_][val_] := (
AppendTo[asc, n -> val];
If[Length[asc] > limit, asc = Take[asc, -limit]];
val)
fib[0] = fib[1] = 1;
fib[n_] := get[n - 1] + get[n - 2]
Let's test it:
fib[100]
(* 573147844013817084101 *)
asc
(* <|90 -> 4660046610375530309, 91 -> 7540113804746346429,
92 -> 12200160415121876738, 93 -> 19740274219868223167,
94 -> 31940434634990099905, 95 -> 51680708854858323072,
96 -> 83621143489848422977, 97 -> 135301852344706746049,
99 -> 354224848179261915075, 98 -> 218922995834555169026|> *)
Association
, which is better for this purpose. MaTeX uses it. Here's the function tostore
values in the cache. Here's how to retrieve them. MaTeX needs to retrieve multiple values at a time, you'll only need a single. Sorry, no time for a proper answer, but these should give you some ideas. $\endgroup$asc = <|"a" -> 1, "b" -> 2|>
, thenAssociateTo[asc, "a" -> 1]
, which is fast but doesn't reorder keys, andAppendTo[asc, "a" -> 1]
, which is slower, but places the key at the end. With some small performance hit, you can bump values to the top on every hit. Thus when you prune old values, the values that are removed will be the ones that have not been requested recently. $\endgroup$