Rubyで変数の割り当ては本当に高価ですか、それとも連鎖文字列メソッドを最適化しますか?

performance ruby string
Rubyで変数の割り当ては本当に高価ですか、それとも連鎖文字列メソッドを最適化しますか?

Project Euler-Problem 36のために書いた次のメソッドがあります。 それが行うのは、ベース10とベース2の両方でパリンドロームである1,000,000未満のすべての数値を合計することです。

def problem_36
  (1...1_000_000).select do |n|
    n.to_s == n.to_s.reverse && n.to_s(2) == n.to_s(2).reverse
  end
end

現在、これは機能し、1秒強で正しい結果が得られます。 1秒未満にしたかったので、数値を文字列に変換する回数を減らすことにしました。 そこで、次の変更を加えました。

def problem_36
  (1...1_000_000).select do |n|
    base10 = n.to_s
    base2  = n.to_s(2)
    base10 == base10.reverse && base2 == base2.reverse
  end
end

問題は、このバージョンは実際には元のバージョンよりも約50%遅いということです。 質問はこれです:これら2つの変数を割り当てるのは本当に遅いですか? または、Rubyはチェーンメソッド呼び出しを最適化していますか?

  7  1


ベストアンサー

この行で

n.to_s == n.to_s.reverse && n.to_s(2) == n.to_s(2).reverse

最初の部分が「false」の場合、2番目の部分は実行されません(Rubyの「&&」演算子の短絡、https://stackoverflow.com/questions/487067/how-to-avoid-short-circuit-evaluation-on/ 487257#487257 [対応する `&`とは異なります)。 これにより、 `to_s(2)`の呼び出しが大幅に節約されます。

7


面白い。

通常のRubyパフォーマンスルールは、プログラムが組み込みの操作を使用する場合、高速になるということです。 そうでない場合は、遅くなります。

2番目のバージョンは、変換が少ない場合とそうでない場合がありますが、1対3のRuby行を実行します。

私はかつて大きなログファイルを読みました。 最初のバージョンでは、Rubyコードを使用して効率的な行のリンクリストを保持していました。

  • 1. *時間の複雑さ:O(1)。

次に、「<<」を使用するように変更し、新しいノードをそれぞれ配列の最後に追加します。

  • 2. *時間の複雑さ:O(N ^ 2 ^)、または少なくともO(N ^ 1 +ε^)

2番目のバージョン(1)はより高速でした。

” ” ‘

^1. 明らかに、実装はチャンク単位で配列を拡張していたため、完全に2次ではありませんでしたが、リンクリストよりもはるかに多くの作業がありました。

0


タイトルとURLをコピーしました