Java 记忆化方法

lambda java memoization

2022-09-02 09:28:26

我遇到了一个有趣的问题，想知道是否以及如何在Java中完成此操作：创建一个可以记住任何函数/方法的方法。该方法具有以下参数：方法/函数及其参数。

例如，假设我有这个方法：

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

我用相同的参数调用我的memoization方法两次：例如，addOne和5，第一个调用实际上应该调用addOne方法并返回结果，并存储该给定参数的结果。当我第二次打电话时，应该知道这之前已经叫过，只是查找上一个答案。

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

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

答案 1

在Java 8中，您可以使用ConcurrentHashMap.computeIfAbsent：

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

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

DZone有一个很好的教程，它提供了一个适用于任何方法的解决方案：

该类非常简单：Memoizer

public class Memoizer<T, U> {

  private final Map<T, U> cache = new ConcurrentHashMap<>();

  private Memoizer() {}

  private Function<T, U> doMemoize(final Function<T, U> function) {
    return input -> cache.computeIfAbsent(input, function::apply);
  }

  public static <T, U> Function<T, U> memoize(final Function<T, U> function) {
    return new Memoizer<T, U>().doMemoize(function);
  }
}

使用这个类也非常简单：

Integer longCalculation(Integer x) {
  try {
    Thread.sleep(1_000);
  } catch (InterruptedException ignored) {
  }
  return x * 2;
}
Function<Integer, Integer> f = this::longCalculation;
Function<Integer, Integer> g = Memoizer.memoize(f);

public void automaticMemoizationExample() {
  long startTime = System.currentTimeMillis();
  Integer result1 = g.apply(1);
  long time1 = System.currentTimeMillis() - startTime;
  startTime = System.currentTimeMillis();
  Integer result2 = g.apply(1);
  long time2 = System.currentTimeMillis() - startTime;
  System.out.println(result1);
  System.out.println(result2);
  System.out.println(time1);
  System.out.println(time2);
}

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

答案 2

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

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);
            }
        });
    };
}

工作实例

这创建了一个包含函数的可变 arity lambda，并且在构造 lambda 后几乎与直接调用函数一样快（即，内部不会发生反射），因为我们使用的是代替。call(Object...args)MethodHandle.invoke()Method.invoke()

您仍然可以在没有 lambda（替换为匿名类）和 MethodHandles（替换为 Method.invoke）的情况下执行此操作，但是对于注重性能的代码来说，性能会受到损害，从而降低其吸引力。