Java记忆化方法

Question

我遇到了一个有趣的问题，想知道在Java中是否可以以及如何做到这一点:创建一个可以记忆任何函数/方法的方法。该方法有以下参数:方法/函数和它的参数。

例如，假设我有这样的方法：

int addOne(int a) { return a + 1;}

我使用相同的参数调用我的memoization方法两次: addOne和5，例如，第一次调用应该实际调用addOne方法，并返回结果，并存储给定参数的结果。当我第二次调用它时，应该知道它之前已经被调用过了，只需查看上一次的答案。

我的想法是有一个类似于HashMap<Callable,HashMap<List<Objects>,Object>>的东西，你可以在其中存储之前的答案，并在以后查找它们。我认为这可以通过lambda表达式以某种方式完成，但我不太熟悉它们。我不太确定如何编写这个方法，希望能得到一些帮助。

使用这种方法可以做到这一点吗？

Answer 1

在Java8中，您可以使用ConcurrentHashMap.computeIfAbsent

Map<Integer, Integer> cache = new ConcurrentHashMap<>();

Integer addOne(Integer x) {
    return cache.computeIfAbsent(x -> x + 1);
}

DZone有a good tutorial，它提供了一个适用于任何方法的解决方案：

Memoizer类非常简单：

公共类Memoizer {私有最终函数，U>缓存=新ConcurrentHashMap<>()；私有Memoizer() {}私有Function doMemoize(最终函数，Function cache.computeIfAbsent(input，function::apply)；}公共静态 Function memoize(最终Function函数){ return new Memoizer ()(函数)；}}

使用这个类也非常简单：

整数longCalculation(整数x) { try { Thread.sleep(1_000)；} catch (忽略InterruptedException){} return x* 2；} Function f=this：：long longCalculation；Function g= Memoizer.memoize(f)；public void automaticMemoizationExample() { long startTime = System.currentTimeMillis()；整数result1 = g.apply(1)；long time1 = System.currentTimeMillis() - startTime；startTime = System.currentTimeMillis()；整数=(1)；long time2 = System.currentTimeMillis() - startTime；System.out.println(result1)；System.out.println(result2)；System.out.println(time1)；System.out.println(time2)；}

运行automaticMemoizationExample方法将产生以下结果：

%2%2% 1000 % 0

Answer 2

如果你愿意放弃参数的类型安全性，你可以用Java8的MethodHandle和lambda来记住任何函数：

public interface MemoizedFunction<V> {
    V call(Object... args);
}

private static class ArgList {
    public Object[] args;

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof ArgList)) {
            return false;
        }

        ArgList argList = (ArgList) o;

        // Probably incorrect - comparing Object[] arrays with Arrays.equals
        return Arrays.equals(args, argList.args);
    }

    @Override
    public int hashCode() {
        return args != null ? Arrays.hashCode(args) : 0;
    }
}

public static <V> MemoizedFunction<V> memoizeFunction(Class<? super V> returnType, Method method) throws
                                                                                                  IllegalAccessException {
    final Map<ArgList, V> memoizedCalls = new HashMap<>();
    MethodHandles.Lookup lookup = MethodHandles.lookup();
    MethodHandle methodHandle = lookup.unreflect(method)
                                      .asSpreader(Object[].class, method.getParameterCount());
    return args -> {
        ArgList argList = new ArgList();
        argList.args = args;
        return memoizedCalls.computeIfAbsent(argList, argList2 -> {
            try {
                //noinspection unchecked
                return (V) methodHandle.invoke(args);
            } catch (Throwable throwable) {
                throw new RuntimeException(throwable);
            }
        });
    };
}

Working Example

这创建了一个包含函数的可变大小的lambda，它几乎和构造lambda之后直接调用函数一样快(即，在call(Object...args)内部没有发生反射)，因为我们使用的是MethodHandle.invoke()而不是Method.invoke()。

您仍然可以在没有Method.invoke(替换为匿名类)和MethodHandles (替换为lambdas )的情况下做到这一点，但对于注重性能的代码来说，性能损失会降低这一点。