java - 如何在 Java 的 GCD 函数中应用 memoization？

Question

我必须计算多对数字的 gcd，所以为了优化我打算将 memoization 应用于我的函数。

对类：

class Pair{
     private long a;
     private long b;
    
    Pair(long a,long b){
        this.a = a;
        this.b = b;
    }
}

我的哈希图（这是一个静态变量）

public static Map<Pair, Long> hashmap = new HashMap<>();

我的 gcd 功能：

public static long gcd(long a,long b) {
        
        if(hashmap.containsKey(new Pair(a,b))) {
            return hashmap.get(new Pair(a,b));
        }
        
        if(hashmap.containsKey(new Pair(b,a))) {
            return hashmap.get(new Pair(b,a));
        }
        
        if(a == 0) {
            return b;
        }
        
        long GCD = gcd(b%a,a);
        
        if(hashmap.containsKey(new Pair(a,b)) || hashmap.containsKey(new Pair(b,a))) {
            return GCD;
        }
        
        hashmap.put(new Pair(a,b),GCD);
        return GCD;
        
    }

但是，当我打印哈希图的键和值时，它包含重复项。这意味着我的函数无法应用 memoization，而是将 pair 放入 hashmap 中。

标签： javaalgorithmdynamic-programmingmemoization

Answer 1

我可以看到您的代码中需要进行一些更正。

• 您没有hashCode为您的Pair班级定义。您可以使用此处描述的方法为一对 long 实现 hashCode。

• 你没有equals方法。你可以写成this.a == other.a && this.b == other.b相等的条件。并且other是 的一个实例Pair。

• 这个说法 ：

  if(hashmap.containsKey(new Pair(a,b)) || hashmap.containsKey(new Pair(b,a))) { return GCD; }

  不需要。在调用递归 gcd 之前你已经检查过了

• 实际上，键是 Pair(a,b) 还是 Pair(b,a) 都无关紧要，equals 和 hashCode 应该返回相同，因此您不需要检查

if(hashmap.containsKey(new Pair(b,a))) { return hashmap.get(new Pair(b,a)); }