为什么这个DP阿尔戈比蛮力阿尔戈慢？

Question

我正致力于实现最长回文子串问题，我采用了DP和额外的O(n^2)（是的，我知道有一个更有效的算法，但我在这篇文章中对此不感兴趣）的方法。
我的实现基本上使用了递归：

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

生成相关的表，但运行时间比预期的慢得多。
如果我在IDE中运行它几秒钟后(15+)它确实会给出正确的输出，但任何在线判断都认为它太慢。我不知道问题出在哪里，因为我用的是记忆。因此不会对相同的情况进行重新计算。
开始显示算法存在性能问题的字符串长度超过900个字符。

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

O(n^2)时间和O(n^2)空间的动态规划方法（不被接受且太慢）

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)空间的蛮力：快得多，被接受得多

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 = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthathtml" target="_blank">governmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
        //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秒内完成（取决于计算机）

这里的问题是什么？
我知道可以进行一些优化来提高性能，但是由于我使用了memoization，O(n^3)的性能怎么可能超过O(n^2)呢？

更新
基于@cahideneskele的答案更新

我用自定义对象替换了列表 作为键：

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)。