Java: 从缓存的Function和缓存的BiFunction实现递归缓存

Question

TLDR：如何实现这个功能？

public static <T, R> Function<T, R> cachedRecursive(final BiFunction<T, Function<T,R>, R> bifunc) {
        
    }

我需要以某种方式从 BiFunction 中提取第二个参数，这样我就可以 return 函数的正确结果。

这个项目是为了学习目的，虽然我坚持完成任务的最后一部分。

任务的第一部分是创建一个从 LinkedHashMap 扩展的缓存 class，这是我的实现：

public class Cache<K,V> extends LinkedHashMap<K, V> {


    private static int MaxSize;
    
    public Cache (int maxSize) {
        super(maxSize,1f,false);
        MaxSize = maxSize;
    }
    
    public Cache () {
        super();
    }
    
    public int getMaximalCacheSize () {
        return MaxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MaxSize;
    }
}

第二部分是创建一个class，添加函数定义：

public class FunctionCache {
    
    private static class Pair<T, U> {
        private T stored_t;
        private U stored_u;
        
        public Pair(T t, U u) {
            stored_t = t;
            stored_u = u;
        }
        
        public boolean equals(Object t) {
            
            if (t == this) {
                return true;
            }
            
            return t == stored_t;
        }
        
        public int hashCode () {
            return stored_t.hashCode();
        }
        
        public T get_first() {
            return stored_t;
        }
        
        public U get_second() {
            return stored_u;
        }
    }
    
    private final static int DEFAULT_CACHE_SIZE = 10000;
    
    public static <T, R> Function<T, R> cached(final Function<T, R> func, int maximalCacheSize) {
        Cache<T, R> cache = new Cache<T,R>(maximalCacheSize);
        return input -> cache.computeIfAbsent(input, func);
    }

    public static <T, R> Function<T, R> cached(final Function<T, R> func) {
        Cache<T, R> cache = new Cache<T,R>(DEFAULT_CACHE_SIZE);
        return input -> cache.computeIfAbsent(input, func);
    }
    
    public static <T, U, R> BiFunction<T, U, R> cached(BiFunction<T, U, R> bifunc, int maximalCacheSize) {
        Cache<T, R> cache = new Cache<T, R>(maximalCacheSize);
        
        return (t, u) -> {
            Pair<T,U> pairKey = new Pair<T,U>(t,u);
            
            Function<Pair<T,U>, R> something = input -> {
                return bifunc.apply(input.get_first(), input.get_second());
            };
            
            if (!cache.containsKey(pairKey.get_first())) {
                R result = something.apply(pairKey);
                cache.put(pairKey.get_first(), result);
                
                return result;
            } else {
                return cache.get(pairKey.get_first());
            }
        };
    }
    
    public static <T, U, R> BiFunction<T, U, R> cached(BiFunction<T, U, R> bifunc) {
        Cache<T, R> cache = new Cache<T, R>(DEFAULT_CACHE_SIZE);
        
        return (t, u) -> {
            Pair<T,U> pairKey = new Pair<T,U>(t,u);
            
            Function<Pair<T,U>, R> something = input -> {
                return bifunc.apply(input.get_first(), input.get_second());
            };
            
            
            if (!cache.containsKey(pairKey.get_first())) {
                R result = something.apply(pairKey);
                cache.put(pairKey.get_first(), result);
                
                return result;
            } else {
                return cache.get(pairKey.get_first());
            }
        };
    }
    
    public static <T, R> Function<T, R> cachedRecursive(final BiFunction<T, Function<T,R>, R> bifunc) {
        
    }
}

这是我的问题：

public static <T, R> Function<T, R> cachedRecursive(final BiFunction<T, Function<T,R>, R> bifunc) {
        
    }

我完全不知道如何实现 cachedRecursive 函数，之前的函数可以完美地使用简单的斐波那契测试，但是此任务的目标是实现 cachedRecursive 函数，该函数采用第一个参数作为 BiFunction输入和第二个参数是一个函数。刚补完代码，这个是我测试的主要class：

public class cachedFunction extends FunctionCache {


public static void main(String[] args) {
        
        @SuppressWarnings({ "rawtypes", "unchecked" })
        BiFunction<BigInteger, BiFunction, BigInteger> fibHelper = cached((n, f) -> {
            if (n.compareTo(BigInteger.TWO) <= 0) return BigInteger.ONE;
            
            return ((BigInteger) (f.apply(n.subtract(BigInteger.ONE), f)))
                    .add((BigInteger)f.apply(n.subtract(BigInteger.TWO), f));
        }, 50000);
        
        Function<BigInteger, BigInteger> fib = cached((n) -> fibHelper.apply(n,fibHelper));
        
        System.out.println(fib.apply(BigInteger.valueOf(1000L)));
    }
}

Answer 1

你的代码有很多缺点和错误：

static 大小变量在不同的缓存实例之间共享（因此打破它）；
代码重复；
不正确的equals/hashCode合同实施；
抑制应该固定而不是抑制的东西；
代码过于臃肿；
和一些次要的（例如 _-包含小写的名称等）。

如果你不介意，我简化一下：

final class Functions {

    private Functions() {
    }

    // memoize a simple "unknown" function -- simply delegates to a private encapsulated method
    static <T, R> Function<T, R> memoize(final Function<? super T, ? extends R> f, final int maxSize) {
        return createCacheFunction(f, maxSize);
    }

    // memoize a recursive function
    // note that the bi-function can be converted to an unary function and vice versa
    static <T, R> Function<T, R> memoize(final BiFunction<? super T, ? super Function<? super T, ? extends R>, ? extends R> f, final int maxSize) {
        final Function<UnaryR<T, Function<T, R>>, R> memoizedF = memoize(unaryR -> f.apply(unaryR.t, unaryR.r), maxSize);
        return new Function<T, R>() {
            @Override
            public R apply(final T t) {
                // this is the "magic"
                return memoizedF.apply(new UnaryR<>(t, this));
            }
        };
    }

    private static <T, R> Function<T, R> createCacheFunction(final Function<? super T, ? extends R> f, final int maxSize) {
        final Map<T, R> cache = new LinkedHashMap<T, R>(maxSize, 1F, false) {
            @Override
            protected boolean removeEldestEntry(final Map.Entry eldest) {
                return size() > maxSize;
            }
        };
        return t -> cache.computeIfAbsent(t, f);
    }

    // these annotations generate proper `equals` and `hashCode`, and a to-string implementation to simplify debugging
    @EqualsAndHashCode
    @ToString
    private static final class UnaryR<T, R> {

        @EqualsAndHashCode.Include
        private final T t;

        @EqualsAndHashCode.Exclude
        private final R r;

        private UnaryR(final T t, final R r) {
            this.t = t;
            this.r = r;
        }

    }

}

以及同时测试结果和记忆契约的测试（“没有重新计算，如果记忆”）：

public final class FunctionsTest {

    @Test
    public void testMemoizeRecursive() {
        final BiFunction<BigInteger, Function<? super BigInteger, ? extends BigInteger>, BigInteger> fib = (n, f) -> n.compareTo(BigInteger.valueOf(2)) <= 0 ? BigInteger.ONE : f.apply(n.subtract(BigInteger.ONE)).add(f.apply(n.subtract(BigInteger.valueOf(2))));
        @SuppressWarnings("unchecked")
        final BiFunction<BigInteger, Function<? super BigInteger, ? extends BigInteger>, BigInteger> mockedFib = Mockito.mock(BiFunction.class, AdditionalAnswers.delegatesTo(fib));
        final Function<BigInteger, BigInteger> memoizedFib = Functions.memoize(mockedFib, 1000);
        final BigInteger memoizedResult = memoizedFib.apply(BigInteger.valueOf(120));
        Mockito.verify(mockedFib, Mockito.times(120))
                .apply(Matchers.any(), Matchers.any());
        Assertions.assertEquals("5358359254990966640871840", memoizedResult.toString());
        Assertions.assertEquals(memoizedResult, memoizedFib.apply(BigInteger.valueOf(120)));
        Mockito.verifyNoMoreInteractions(mockedFib);
    }

}

Java: 从缓存的Function和缓存的BiFunction实现递归缓存

Java: Implement recursive cached from cached Function and cached BiFunction

java

memoization

generic-lambda