CODEWITHSUNDEEP
javarecursionoptimization
Tobiq
Tobiq

Reputation: 2657

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

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...

Upvotes: 0

Views: 162

Answers (1)

sprinter
sprinter

Reputation: 27986

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.

Upvotes: 3

Related Questions