Recursion optimisation using a "visited" set, for pure functions

Question

Does Java support some form of pure-function annotation resulting in the compiler caching results in order to avoid re-calculation of a result.

The context is essentially traversing a graph. I'm not wanting to re-visit already-visited sections of the graph.

I can do this using a stack / visited set. However, this stack code seems like what's already going on in the call-stack - but more complicated for the code-reader. The only missing component is the visited set implementation.

Is this a thing? Would be cool...

Does this answer your question? [What are the different techniques for memoization in Java?](https://stackoverflow.com/questions/3623754/what-are-the-different-techniques-for-memoization-in-java) — Carcigenicate, Nov 26 '19 at 21:50
Note that other languages seem to have much better support for this than Java. Python has a `lrucache` annotation built-in that does what you want for example. — Carcigenicate, Nov 26 '19 at 21:51

score 3 · Accepted Answer · answered Nov 26 '19 at 21:53

3

No there's nothing built into the language. However caching values in a map is relatively easy as long as the input values are in a hashable object:

private final Map<Input,Output> cache = new HashMap<>();

public Output calculate(Input input) {
    return cache.computeIfAbsent(input, in -> <calc output>);
}

If you want to make it a LRU cache then you use LinkedHashMap and implement removeEldestEntry. Again it's pretty straightforward.

answered Nov 26 '19 at 21:53

sprinter

27,148
6
47
78

Is this "Memoization" - never heard of this? – Tobiq Nov 26 '19 at 21:58
1

@Tobiq "memoization" basically just means caching the results of a function based on the arguments. – Carcigenicate Nov 26 '19 at 22:04

Recursion optimisation using a "visited" set, for pure functions

1 Answers1