为什么这个 DP 算法比蛮力算法慢？

Question

我正在努力实现最长回文子串问题，我遵循了 DP 和额外 O(N^2) 的方法（是的，我知道有一个更有效的算法，但我对此不感兴趣post).
我的实现基本上使用了循环：

P(i, j) = P(i + 1, j - 1) ^ s[i] == s[j]

构建相关的 table 但运行时间比预期的要慢得多。
如果我运行它在我的 IDE 几秒后（15+）它确实给出了正确的输出但是它被任何在线法官拒绝因为太慢了。我不确定问题出在哪里，因为我正在使用 memorization。所以没有重新计算相同的情况。
开始显示该算法存在性能问题的字符串长度超过 900 个字符。

更新
我正在更新问题以添加完整的源代码和测试用例

动态编程方法 O(N^2) 时间和 O(N^2) space（不接受且太慢）

public static String longestPalindromeDP(String s) {
        Map<List<Integer>, Boolean> cache = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < s.length(); j++) {
                populateTable(s, i, j, cache);
            }
        }
        int start = 0;
        int end = 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < s.length(); j++) {
                if(cache.get(Arrays.asList(i, j))) {
                    if(Math.abs(start - end) < Math.abs(i - j)) {
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }

private static boolean populateTable(String s, int i, int j, Map<List<Integer>, Boolean> cache) {
        if(i == j) {
            cache.put(Arrays.asList(i, j), true);
            return true;
        }
        if(Math.abs(i - j) == 1) {
            cache.put(Arrays.asList(i, j), s.charAt(i) == s.charAt(j));
            return s.charAt(i) == s.charAt(j);
        }

        if(cache.containsKey(Arrays.asList(i, j))) {
            return cache.get(Arrays.asList(i, j));
        }

        boolean res = populateTable(s, i + 1, j - 1, cache) && s.charAt(i) == s.charAt(j);
        cache.put(Arrays.asList(i, j), res);
        cache.put(Arrays.asList(j, i), res);
        return res;
    }

这在 populateTable 中非常慢，但一旦完成，结果是正确的。

蛮力 O(N^3) 时间和 O(1) space：更快并被接受

public static String longestPalindromeBruteForce(String s) {
        if(s.length() == 1) {
            return s;
        }
        String result = "";
        for(int i = 0; i < s.length(); i++) {
            for(int j = i + 1; j <= s.length(); j++) {
                String tmp = s.substring(i, j);
                if(isPalindrome(tmp)) {
                    if(tmp.length() > result.length()) {
                        result = tmp;
                        if(result.length() == s.length()) {
                            return result;
                        }
                    }
                }
            }
        }

        return result;
    }

    private static boolean isPalindrome(String s) {
        for(int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

测试和输入：

public static void main(String[] args) {
        final String string1 = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
        //final String string2 = "ibvjkmpyzsifuxcabqqpahjdeuzaybqsrsmbfplxycsafogotliyvhxjtkrbzqxlyfwujzhkdafhebvsdhkkdbhlhmaoxmbkqiwiusngkbdhlvxdyvnjrzvxmukvdfobzlmvnbnilnsyrgoygfdzjlymhprcpxsnxpcafctikxxybcusgjwmfklkffehbvlhvxfiddznwumxosomfbgxoruoqrhezgsgidgcfzbtdftjxeahriirqgxbhicoxavquhbkaomrroghdnfkknyigsluqebaqrtcwgmlnvmxoagisdmsokeznjsnwpxygjjptvyjjkbmkxvlivinmpnpxgmmorkasebngirckqcawgevljplkkgextudqaodwqmfljljhrujoerycoojwwgtklypicgkyaboqjfivbeqdlonxeidgxsyzugkntoevwfuxovazcyayvwbcqswzhytlmtmrtwpikgacnpkbwgfmpavzyjoxughwhvlsxsgttbcyrlkaarngeoaldsdtjncivhcfsaohmdhgbwkuemcembmlwbwquxfaiukoqvzmgoeppieztdacvwngbkcxknbytvztodbfnjhbtwpjlzuajnlzfmmujhcggpdcwdquutdiubgcvnxvgspmfumeqrofewynizvynavjzkbpkuxxvkjujectdyfwygnfsukvzflcuxxzvxzravzznpxttduajhbsyiywpqunnarabcroljwcbdydagachbobkcvudkoddldaucwruobfylfhyvjuynjrosxczgjwudpxaqwnboxgxybnngxxhibesiaxkicinikzzmonftqkcudlzfzutplbycejmkpxcygsafzkgudy";

        long startTime = System.nanoTime();

        String palindromic = longestPalindromeDP(string1);
        long elapsed = TimeUnit.SECONDS.convert(System.nanoTime() - startTime, TimeUnit.NANOSECONDS);

        System.out.println(elapsed);
        System.out.println(palindromic);

    }

BruteForce 在 0 秒内完成。
DynamicProgramming 最多可在 9 秒内完成（取决于机器）

这里有什么问题？
我知道可以进行一些优化来提高性能，但是 O(N^3) 怎么可能优于 O(N^2) 因为我使用了记忆？

更新
根据@CahidEnesKeleş

的回答更新

我用自定义对象替换了 List<Integer> 作为键：

class IdxPair {  
   int i;
   int j;  
   IdxPair(int i, int j) {
     this.i = i;
     this.j = j;  
   }  

   @Override  
   public boolean equals(Object o) {  
      if(o == null || !(o instanceof IdxPair)) return false;  
      if(this == o ) return true;  
      IdxPair other = (IdxPair) o;  
      return this.i == other.i && this.j == other.j;  
   }  

   @Override 
   public int hashCode() {  
     int h = 31;  
     h = 31 * i + 37;  
     h = (37 * h) + j;    
     return h;  
   }  
}

虽然之前有几个测试用例失败了，现在通过了，但总体还是太慢了，被在线评委拒绝了。

Answer 1

我尝试使用类似 C 的数组而不是 HashMap，代码如下：

public static String longestPalindromeDP(String s) {
    int[][] cache = new int[s.length()][s.length()];
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < s.length(); j++) {
            cache[i][j] = -1;
        }
    }
    for(int i = 0; i < s.length(); i++) {
        for(int j = 0; j < s.length(); j++) {
            populateTable(s, i, j, cache);
        }
    }
    int start = 0;
    int end = 0;
    for(int i = 0; i < s.length(); i++) {
        for(int j = 0; j < s.length(); j++) {
            if(cache[i][j] == 1) {
                if(Math.abs(start - end) < Math.abs(i - j)) {
                    start = i;
                    end = j;
                }
            }
        }
    }
    return s.substring(start, end + 1);
}

private static boolean populateTable(String s, int i, int j, int[][] cache) {
    if(i == j) {
        cache[i][j] = 1;
        return true;
    }
    if(Math.abs(i - j) == 1) {
        cache[i][j] = s.charAt(i) == s.charAt(j) ? 1 : 0;
        return s.charAt(i) == s.charAt(j);
    }

    if (cache[i][j] != -1) {
        return cache[i][j] == 1;
    }

    boolean res = populateTable(s, i + 1, j - 1, cache) && s.charAt(i) == s.charAt(j);
    cache[i][j] = res ? 1 : 0;
    cache[j][i] = res ? 1 : 0;
    return res;
}

此代码比蛮力方法运行得更快。在我的电脑中，旧的 dp 完成时间约为 5000 毫秒，新的 dp 完成时间约为 30 毫秒，bruteforce 完成时间约为 100 毫秒。

既然我们知道了缓慢的原因，我进行了进一步的实验并测量了以下代码的运行时间。

for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        cache.put(Arrays.asList(i, j), true);
    }
}

此代码在 2000 毫秒内完成。我进一步划分了表达式以准确找到缓慢的根源。

for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        Arrays.asList(i, j);
    }
}

此代码在 37 毫秒内完成。

Map<Integer, Boolean> cache = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        cache.put(i*1000 + j, true);
    }
}

此代码在 97 毫秒内完成。

不Arrays.asList Map.put 都不慢。也许列表的哈希函数很慢

for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        Arrays.asList(i, j).hashCode();
    }
}

此代码在 101 毫秒内完成。

没有。这也很快。所以也许哈希值在大多数时候会发生冲突。为了对此进行测试，我将所有哈希码放入一个集合中并检查其大小。

Set<Integer> hashSet = new HashSet<>();
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        hashSet.add(Arrays.asList(i, j).hashCode());
    }
}
System.out.println(hashSet.size());

它给出了 31969。1000000 中的 31969 大约是 %3,2。我认为这是缓慢的根源。 1m 项对于 HashMap 来说太多了。随着越来越多的碰撞发生，它开始远离 O(1)。

为什么这个 DP 算法比蛮力算法慢？

Why is this DP algo slower than the brute forcea algo?

java

algorithm

recursion

hashmap

dynamic-programming