このRubyパズルソリューションをもっと速くするにはどうすればいいですか？

Question

パズルサイトが嫌いな理由の1つは、失敗したときに教えてくれるが、改善方法を習得できないからです。私は通常、これらの種類の質問を投稿するのが好きではありませんが、なぜこれが失敗するのかを理解しようと多くの時間を無駄にしました。 （あなたの好奇心ならば）

ここ ​​

が問題である：http://pastie.org/3044657

それはほとんどの試験に合格するが、その後による最適化の理由にその後失敗

は、ここに私のコードです。私はこれを最適化する方法を知りたいと思っています。私はどのように最適化するかを「特定し、学習する」ことについてはわからない。

PS。これは、最もエントリーレベルのパズルですので、私はそれが誰かを傷つけていることを非常に疑っています。

Answer 1

アルゴリズムはO（n²）です。コードを最適化するだけでこれについて行うことはあまりありません。

少し与えられたアルゴリズムのパフォーマンスを向上させるためにいくつかのアイデア：

• は、配列に文字列を分割します。
• がstring_a[j] != string_b[j]であることがわかったら、各同等のペアを数えるのではなく、 で、sumを増やしてください。

このコードは、私のテストケースのための私のマシン上での約2倍の速さである：

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