基于比较的算法性能

Question

我有一个用 Java 编写的算法，我需要确保在已经执行函数调用的情况下不会重复该函数调用。让我解释一下逻辑:

1. 有一组函数可用:函数 1、函数 2、...、函数 n 及其参数，

2. 函数 1 调用以一组值作为参数并产生结果，

3. 函数 1 调用，作为参数传递的值，产生的结果存储在内存中，

4. 当进行函数 2 调用时，函数 2 调用，其值作为参数传递，结果存储在内存中，

5. 当再次调用函数 1 时，使用不同的值作为参数，新的调用(即它的值和结果)存储在内存中，

6. 现在，当再次进行函数 1 调用时，参数值与上面 2 中的相同，因为之前已经进行了完全相同的调用，我们不想再次执行函数调用，但是我们需要检索存储在上面 2 中的结果。

我们目前的策略是将函数调用、它们的值和结果存储在一个映射中。对于每个新的函数调用，我们首先在映射中查看该函数是否已被调用。如果是这样，我们将函数调用中传递的值与存储在内存中的先前函数调用的值一一比较。

随着函数调用数量的增加，我们遇到了一些性能问题。对于每个新调用，我们将每个值与内存中存储的值进行比较。因此，当我们每次使用不同的值调用函数 1 100,000 次并且我使用以前从未使用过的值 A、B、C 再次调用函数 1 时，我需要将 100,000 次 A、B 和 C 与存储的值进行比较之前的 100,000 次函数调用。然后又是一个电话，我又比较了100001次。

性能变差到非常非常慢的程度。关于如何改进该算法，您能提供一些提示吗？

Answer 1

您不应只将函数类型存储为映射的键，而应将整个调用与所有参数一起存储。因此，有必要编写一个 FunctionCall 类作为 Key。它可能看起来像这样:

enum Funtions{Funktion1, Funktion2, Funktion3};

class FunctionKey(){
    public Functions function;
    public int value1
    public int value2

    public int hashCode(){
        int result = 1 + function.ordinal();
        result = result * 31 + value1;
        result = result * 17 + value2;
        return result;
    }

    public boolean equals(Object obj){
        if (!(obj instanceof FunctionKey))
              return false;
        FunctionKey that = (FunctionKey) obj;
        return function == that.function && value1 == that.value1 && value2 == that.value2;
    }
}

如果你用这样的键构建一个 HashMap，并将函数的结果作为值，你将能够在常数时间内检索旧值。如果映射中没有值，只需将这样的键与新值一起存储。

Function1 现在可能看起来像这样:

Map<FunctionKey, Integer> cache = new HashMap<>();

int function1(int value1, int value2){
    FunctionKey key = new FunctionKey(Functions.Function1, value1, value2);
    Integer result = cache.get(key);
    if (result==null){
        result = oldFunction1(value1, value2);
        cache.put(key, result);
    }
    return result;
}

如果函数返回不同的数据类型，它会变得有点笨拙(也许每个函数一个映射就可以了)。

这个概念叫做缓存。