lambda - java 8 lambda 的懒惰但持久的评估

Question

我目前正致力于在 java 中创建自己的持久数组，它使用二叉搜索树来存储值的集合。

我想添加一个采用 Function 的 map 方法作为生成新数组的参数。除非请求特定值，否则我不想评估函数。这很简单，因为 lambda 是惰性求值的。但是，我也只希望一个函数只被评估一次，即使结果被多次请求。

我可以创建一个节点来存储供应商并在评估时更新结果:

class Node<T> {

    private T value;
    private Supplier<T> supplier;

    public T get() {
        if (null != value)
            return value;
        value = supplier.get();
        return value;
    }
}

...在哪里 supplier源自 Function应用于旧版本的持久化数组中的值。

但是，这不再是一种功能性方法，并且有可能在多线程系统中导致错误*。在供应商返回空值的情况下，它也不会产生优势**。

另一种方法是返回 Node 的实例。在接听电话时:

class Node<T> {

    private final Optional<T> value;
    private final Supplier<T> supplier;

    Node(Supplier<T> supplier, T value) {
        this.supplier = supplier;
        this.value = Optional.ofNullable(value);
    }

    public Tuple<Node<T>, T> get() {
        if (null != value)
            return new Tuple<>(this, value.orElse(null));
        T result = supplier.get();
        Node<T> newNode = new Node<>(null, result);
        return new Tuple<>(newNode, result);
    }
}

我喜欢这种保持功能的方法；但这将需要在树上向上的所有父节点中进行大量开销，以进行 get 调用。并且它需要在使用应用程序的代码中进行繁琐的拆箱。

有没有人可以想到另一种方法来按照我的要求进行这项工作？谢谢。

*这可以使用锁定机制来解决，但会增加一层我希望避免的复杂性。

**我考虑过制作value一个 Optional<T> , 其中 null表示尚未评估，Optional.empty() as 已被评估并返回 null。但是，这可以解决我的问题，而不是解决它。

对于不熟悉持久数组的人来说，它是一种数据结构，每当执行更新时，它都会创建一个自身的新实例。这允许它是纯粹不可变的。使用二叉树(或更常见的 32 位树)方法允许更新减少重复数据，无论是速度还是内存。

编辑:

集合的代码可以在 github 上找到.有关使用说明，您可以查看测试文件夹。

Answer 1

免责声明:此答案不直接回答问题，因为它既不使用 Supplier也不是 Optional直接在Node类(class)。相反，提出了一种可能有助于解决问题的通用函数式编程技术。

如果问题是关于每个输入值只评估一次函数，那么你不应该改变你的树/数组/节点。相反，memoize函数，这是一种纯函数方法:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again

这是一种方法，灵感来自 this excellent article由 Pierre-Yves Saumont 编写(请查看它以获得对记忆化的深入介绍):

public static <T, U> Function<T, U> memoize(Function<T, U> function) {
    Map<T, U> cache = new ConcurrentHashMap<>();
    return input -> cache.computeIfAbsent(input, function::apply);
}

假设您有一个需要很长时间才能执行的方法。然后，您可以使用 memoize这种方法:

// This method takes quite long to execute
Integer longCalculation(Integer x) {
    try {
        Thread.sleep(1_000);
    } catch (InterruptedException ignored) {
    }
    return x * 2;
}

// Our function is a method reference to the method above
Function<Integer, Integer> function = this::longCalculation;

// Now we memoize the function declared above
Function<Integer, Integer> memoized = memoize(function);

现在，如果你打电话:

int result1 = function.apply(1);
int result2 = function.apply(2);
int result3 = function.apply(3);
int result4 = function.apply(2);
int result5 = function.apply(1);

您会注意到五个调用总共需要大约 5 秒(每个调用 1 秒)。

但是，如果您使用 memoized具有相同输入值的函数 1 2 3 2 1 :

int memoizedResult1 = memoized.apply(1);
int memoizedResult2 = memoized.apply(2);
int memoizedResult3 = memoized.apply(3);
int memoizedResult4 = memoized.apply(2); // <-- returned from cache
int memoizedResult5 = memoized.apply(1); // <-- returned from cache

您会注意到现在五个调用总共需要大约 3 秒。这是因为最后两个结果会立即从缓存中返回。

所以，回到你的结构......在你的map里面方法，你可以只记住给定的函数并使用返回的内存函数。在内部，这会将函数的返回值缓存在 ConcurrentHashMap 中。 .

作为 memoize方法使用 ConcurrentHashMap在内部，您无需担心并发性。

注意:这只是开始......我正在考虑两个可能的改进。一种是限制缓存的大小，这样如果给定函数的域太大，它就不会占用整个内存。另一个改进是仅在之前没有被内存的情况下内存给定的函数。但是这些细节留给读者作为练习......;)