为什么这个动态编程答案很慢?

Question

为什么这个解决方案很慢？我猜这是因为子问题没有在应该解决的正确时间解决。我做错了什么？

def longest_palindrome(s)
len = s.length
longest_start = 0
longest_end = 0
mem = Array.new(len) { Array.new(len, -1) }

(0..(len - 1)).each do |i|
(i..(len - 1)).each do |j|
if util(i, j, s, mem) && j - i > longest_end - longest_start
longest_start = i
longest_end = j
end
end
end
s[longest_start..longest_end]
end
def util(i, j, s, mem)
return mem[i][j] if mem[i][j] != -1
judge = s[i] == s[j]           
mem[i][j] = j - i >= 2 ? util(i+1, j-1, s, mem) && judge : judge  
end

Answer 1

我不会说你的解决方案很慢，尽管这当然是一个完全武断的描述。

也就是说，我想我可能会测试一下user1934428的期望，看看你的代码对于非常短的回文是否确实更快，同时进一步测试你的代码与一个更简单的解决方案，这个解决方案只是循环#each_cons并使用#reverse来检查回文。

这是我想出的方法：

def longest_palindrome2(str)
longest = str.size
loop do
str.chars.each_cons(longest) do |substr|
return substr.join if substr == substr.reverse || longest == 1
end
longest -= 1
end
end

我用两个相当长的字符串测试了你和我的解决方案，一个有一个非常短的回文(x有一个最长的回文三个字符(，另一个有一个很长的回文(y，其中最长的回文是整个 125 个字符的字符串(：

x = 'alkneowinlsoirneleibesemssooeineiiqkwjviowrsitheixwlelajsdk awjlk;ja ;kja ;lk jasdkj a;lskdja pwoeiarjpowiecjpnaowiejcnpaosijcrnpoeirjn'
t = Time.now()
10.times { longest_palindrome(x) }
p Time.now() - t
t = Time.now()
10.times { longest_palindrome2(x) }
p Time.now() - t
y = 'satorarepotenetoperarotassatorarepotenetoperarotassatorarepotenetoperarotassatorarepotenetoperarotassatorarepotenetoperarotas'
t = Time.now()
10.times { longest_palindrome(y) }
p Time.now() - t
t = Time.now()
10.times { longest_palindrome2(y) }
p Time.now() - t

我得到了这些结果：

0.109101
0.266618
0.094408
0.000618

事实证明，你的回文用长回文快一点，而我的快得多。此外，你的短回文比我的快得多，而我的回文比你的长回文快得多。

因此，我的回文会根据回文的长度而变化很大(这是有道理的，因为随着最长回文的大小减小，它必须进行的迭代次数会迅速增加(。你的表现比我的要一致得多，因为结果的大小各不相同。

换句话说，我是否会称您的解决方案为慢取决于最长回文相对于输入字符串大小的长度。