如何更快地制作这个Ruby拼图解决方案？

我讨厌拼图网站的一个原因是因为他们告诉你什么时候失败，但你无法学习如何改进。我通常不喜欢发布这些类型的问题，但是我浪费了很多时间来弄清楚为什么会失败，我必须知道答案！如何更快地制作这个Ruby拼图解决方案？

这里是我的代码：

这里的问题（如果你好奇）：http://pastie.org/3044657

它通过最测试，但后来则由于失败原因的优化。我很想知道如何优化这个。我不知道如何去“识别和学习”如何优化。

PS。这是最入门级的难题，所以我非常怀疑这是通过走这个步骤伤害任何人。

来源

2011-12-20 darkone

http://pastie.org/3044657不起作用。你确定链接是正确的吗？ – 2011-12-20 08:44:06

我们能否看到测试答案失败？如果通过优化你的意思是执行速度，你是否尝试分析代码？ – arcresu 2011-12-20 10:06:37

你的算法是O（n²）。通过优化代码，你可以做的事情不多。

一些想法，以稍微改善对于给定的算法的性能：

分割字符串到一个数组。
一旦找到j与string_a[j] != string_b[j]，则增加sum那个j 而不是计算每个相等的对。

此代码是关于快两倍，你是我的机器上我的测试用例：

ary = line.strip.chars.to_a 
n = ary.count 
sum = (1...n).inject(n) do | sum, i | 
    sum + (n-i).times { | j | break j if ary[j] != ary[j + i] } 
end

来源

2011-12-20 16:37:32

虽然这基本上仍然是O（n^2）。我想我必须弄清楚如何让它比这更快。 Ether O（n）or O log n – darkone 2011-12-20 20:51:45

@darkone：是的，当然是O（n²） - 它是相同的算法。 – 2011-12-20 22:00:19

是的。令人惊讶的是，你的解决方案也太慢了。让我怀疑我是否忽略了一些明显的东西。 – darkone 2011-12-21 05:37:03

如何更快地制作这个Ruby拼图解决方案？

回答

相关问题