I described how to do memoization recursion using a lambda expression.
class Lambdas{
static <T,R> Function<T,R> memorizeRec(BiFunction<Function<T,R>, T, R> biFunc){
return memorizeRec(new HashMap<>(), biFunc);
}
static <T,R> Function<T,R> memorizeRec(Map<T,R> memo, BiFunction<Function<T,R>, T, R> biFunc){
return t -> {
if(!memo.containsKey(t)) memo.put(t, biFunc.apply(memorizeRec(memo, biFunc), t));
return memo.get(t);
};
}
}
Function<Integer,Long> fib = Lambdas.memorizeRec( (self,x) -> (x <= 2) ? 1 : self.apply(x-1) + self.apply(x-2) );
fib.apply(50);
// argument: 50 => result: 12586269025
that's all. The text is from the following.
It's been more than six years since the release of Java 8 (March 2014), and reading and writing pre-Java 7 code has almost disappeared. Compared to the old coding environment (before Java 7), I feel that the biggest difference is still the change due to the introduction of lambda expressions (and Functional interface). Lambda expressions make it easier to describe behavior, which makes it possible to concisely realize design patterns that have been realized using inheritance and interfaces with less description, while modern Java and lambda expressions. It has also become a barrier for coders who are unfamiliar with Java. In order to write better code, I think it is important to get along with lambda expressions and utilize them.
Lambda expression example.java
Function<Integer, Integer> increment = x -> x + 1;
increment.apply(1);
// argument: 1 => result: 2
This time, I will introduce helper methods that realize (1) memoization, (2) recursion, and (3) memoization recursion in order to increase what you can do with lambda expressions.
Memoization (of a function) is to memorize the input and output of a calculated function and return the memorized output when the same input is given so that the same calculation can be performed at once. It's a technique. I think it's easiest to implement using HashMap.
Memoization.java
class Lambdas{
static <T,R> Function<T,R> memorize(Function<T,R> func){
Map<T,R> memo = new HashMap<>();
return t -> memo.computeIfAbsent(t, tt -> func.apply(tt));
}
}
Function<Integer, Integer> memo = Lambdas.memorize(x -> x+1);
// argument: 1 => result: 2
Not only is memoization shortening the calculation time, but the same instance is returned, which is expected to improve memory usage. (Similarly, since the same instance is referenced, please note whether the return value etc. is an immutable object)
The topic has changed, it's about recursive functions. In fact, you cannot write a recursive function as it is with a lambda expression (anonymous function). For example, when calculating factorial, a named method can be described as int fact (n) {return (n> 0)? N * fact (n-1): 1;}. , When I try to make it a lambda expression, it becomes Function <Integer, Integer> fact = n-> (n> 0)? N * ??? (n-1): 1;, and in the ??? part You can see that there is no name that can be entered. (Fact is not yet defined and cannot be referenced)
As it is not possible to recursively call it as it is, let's assume that the function you want to create is finally given from the outside (I think it is not necessary to create a function if you can make such an assumption). This is because Function <Integer, Integer> will be added to the argument.
BiFunction<Function<Integer, Integer>, Integer, Integer> fact =
(self, n) -> (n > 0) ? n * self.apply(n-1) : 1;
However, as it is, the first argument given to fact does not exist and cannot be called. The function I want to create is also Function <Integer, Integer>, so I want to convert the previous BiFunction <Function <T, R>, T, R> to Function <T, R> ( In the factorial example, both T and R are Integer).
Therefore, if you perform the following conversion, you can convert it well.
class Lambdas{
static <T,R> Function<T,R> rec(BiFunction<Function<T,R>, T, R> biFunc){
return t -> biFunc.apply(rec(biFunc), t);
}
}
Function<Integer, Integer> fact = Lambdas.rec((self, n) -> (n > 0) ? n * self.apply(n-1) : 1);
// argument: 5 => result: 120
It's complicated like a puzzle, but I think it's a good idea to actually enter values step by step and follow them. (It has a shape similar to a fixed point combinator. If you are interested, please check it out. Although rec is recursive as it is, it is not a fixed point combinator.)
Memoization recursion is a technique for efficiently performing calculations by memoizing a recursive function. For example, when finding a specific term in a sequence that can be expressed by a (higher order) recurrence formula, the formula can be expressed by using recursion, but if it is calculated as it is, the calculation of the same term will occur repeatedly and the amount of calculation will increase. It may be. By performing memoization recursion, it is possible to calculate the same term only once. One thing that can be easily mistaken is that memoizing a recursive function does not result in memoized recursive. In that case, the call to a particular argument is faster, but the recursive calculation itself remains slow. Correctly, you need to make a recursive call to the memoized function. Therefore, prepare a map for memoization in advance and refer to the memo every time it is called recursively.
class Lambdas{
static <T,R> Function<T,R> memorizeRec(BiFunction<Function<T,R>, T, R> biFunc){
return memorizeRec(new HashMap<>(), biFunc);
}
static <T,R> Function<T,R> memorizeRec(Map<T,R> memo, BiFunction<Function<T,R>, T, R> biFunc){
return t -> {
if(!memo.containsKey(t)) memo.put(t, biFunc.apply(memorizeRec(memo, biFunc), t));
return memo.get(t);
};
}
}
Function<Integer,Long> fib = Lambdas.memorizeRec( (self,x) -> (x <= 2) ? 1 : self.apply(x-1) + self.apply(x-2) );
fib.apply(50);
// argument: 50 => result: 12586269025
Regarding the implementation part of memorizeRec (Map <T, R>, BiFunction <T, R>, T, R>), the meaning (= what you want to do) is equivalent to computeIfAbsent, but computeIfAbsent ConcurrentModificationException will occur because recursion will occur in and the value will be rewritten. Therefore, it is implemented by containsKey and put without using computeIfAbsent.
Recommended Posts