Метод Java memoization

Question

Я столкнулся с интересной проблемой и задавался вопросом, как и как это можно сделать в Java: Создайте метод, который может memoize любой функции/метода. Метод имеет следующие аргументы: метод/функция и аргумент (ы) для него.

Для примера скажу, у меня есть этот метод:

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

и я называю свой метод запоминания два раза с теми же аргументами: AddOne и 5, например, первый вызов должен фактически вызвать метод AddOne и возврат результат, а также сохраните этот результат для данного аргумента. Второй раз, когда я вызываю это, должен знать, что это было вызвано раньше и просто просмотрел предыдущий ответ.

Моя идея состояла бы в том, чтобы иметь что-то вроде HashMap<Callable,HashMap<List<Objects>,Object>>, где вы сохраните предыдущие ответы и посмотрите их позже. Я думаю, что это может быть как-то сделано с лямбда-выражениями, но я не знаком с ними. m не совсем уверен, как написать этот метод и будет признателен за некоторую помощь.

Можно ли это сделать с помощью этого подхода?

Answer 1

В Java 8 вы можете сделать это так:

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

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

This is a good tutorial. There it is made for any method.

Из учебника:

Класс 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(1000); 
    } 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); 
} 

Выход:

2 
2 
1000 
0 

Answer 2

Вы можете memoize любую функцию с Java 8 в 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); 
      } 
     }); 
    }; 
} 

Working Example

Это создает лямбда переменной arity, которая включает функцию и почти как fa как вызов функции непосредственно (т. е. не происходит отражения внутри call(Object...args)) после того, как лямбда построена, поскольку мы используем MethodHandle.invoke() вместо Method.invoke().

Вы все еще можете сделать это без лямбда (замените на анонимные классы) и MethodHandles (замените на Method.invoke), но будут штрафы за производительность, которые делают это менее привлекательным для служебного кода.