Java 中各种输入函数的记忆

Question

我有一个将各种 double 变量作为输入的昂贵函数：

public double f(double v1, double v2, double v3){
    ...
    return output;
}

所以我尝试使用两种不同的策略来记住它的输出。

嵌套的 HashMaps：

Map<Double,Map<Double,Map<Double,Double>>> map = new HashMap<>();

public double f(double v1, double v2, double v3){
    // This is abbreviated: in my case I made sure to call only once each "get()"
    if(map.containsKey(v1) && map.get(v1).containsKey(v2) && map.get(v1).get(v2).containsKey(v3))
         return map.get(v1).get(v2).get(v3);
    ...
    // calculations
    ...
    // put "output" in the map (and create new intermediate HashMaps when needed)
    ...
    return output;
}

自定义 HashMap 键：

public class DoubleKey {
   public final double[] values;
   public DoubleKey(double[] values){ this.values = values;}

   @Override
   public boolean equals(Object key){
      if(key instanceof DoubleKey)
         return Arrays.equals(values, ((DoubleKey)key).values);
      return false;
   }

   @Override
   public int hashcode(){
      return Arrays.hashcode(values);
   }
}

Map<DoubleKey,Double> map = new HashMap<>();

public double f(double v1, double v2, double v3){
    DoubleKey key = new DoubleKey(new double[]{v1,v2,v3});
    if(map.containsKey(key))
         return map.get(key);
    ...
    // calculations
    ...
    map.put(key, output);
    return output;
}

现在，我希望第二种方法更快，因为它使用单个 Hashmap，并且通常感觉更优雅。但事实证明，与产生巨大速度提升的第一种方法相比，我从第二种方法中获得的收益较少。

你知道为什么第二种方法效率会降低吗？是使用Arrays.equals()and/orArrays.hashcode()的成本吗？

更一般地说，您知道其他更有效的记忆技术吗？

Answer 1

两个解不相等。第一个硬编码仅支持 3 个双参数，而第二个支持任意数量的参数。

如果你只需要支持 3 个参数，我认为保存 3 个实例变量更有效：

编辑： 在评论之后，将使用可变参数 ctor 的原始答案替换为显式的单个参数。可能更有效（不构造数组）。还使实例变量最终化以启用编译器优化

public class DoubleKey
{
    final double arg1, arg2, arg3;
    final int hashCode;

    public DoubleKey(double arg1, double arg2, double arg3)
    {
        this.arg1 = arg1;
        this.arg2 = arg2;
        this.arg3 = arg3;
        hashCode = Objects.hash(arg1, arg2, arg3);
    }

    @Override
    public boolean equals(Object key)
    {
        if (key instanceof DoubleKey) {
            DoubleKey dk = (DoubleKey) key;
            return arg1 == dk.arg1 && arg2 == dk.arg2 && arg3 == dk.arg3;
        }
        return false;
    }

    @Override
    public int hashCode()
    {
        return hashCode;
    }
}

构建 DoubleKey 实例现在更容易

DoubleKey key = new DoubleKey(v1,v2,v3);

Java 中各种输入函数的记忆

Memoization of a function of various inputs in Java

java

arrays

hashmap

memoization

嵌套的 HashMaps：

自定义 HashMap 键：