ProjectEuler Problem62で==メソッドを調べてみた

Problem 62 「立方数置換」

立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.
立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

class P62
  def initialize
    @keta_values = keta_values
  end

  def  keta_values
    # ある桁数の最初の立法数を求める。ex. 3桁なら5(=125)、4桁なら10(=1000)、
    (0..20).map do |keta|
      ((10**(keta-1))**(1/3.0)).to_i + 1
    end
  end

  def main
    keta = 5 #5ケタ以上を探す
    loop do
      cubics = cubics( keta )
      cubics.each_with_index do |cubic, idx|
        return cubic[0] if permutations( idx, cubics ).size == 5
      end
      keta += 1
    end
    "Not find"
  end

  def cubics( digit )
    # ex. for return value. 36 ** 3 -> [46656, "45666"]  これは [立法数、立法数の各値をソートして文字列にした]

    (@keta_values[digit]..10000000).inject([]) do |cubics, n| # 10000000 ** 3  is 22digits
      cubic = n * n * n

      if cubic.to_s.size > digit
        return cubics
      elsif cubic.to_s.size == digit
        cubics << [cubic, cubic.to_s.enum_for( :each_char ).sort.inject{|conb,s| conb+s}]
      end

      cubics
    end
  end

  def permutations( idx, cubics )
    drop_cubics = cubics.drop( idx )
    base = drop_cubics[0]
    drop_cubics.select { |cubic| base[1] == cubic[1] }
  end
end

puts P62.new.main

cubics()で立法数を求め、その各桁を文字列変換しソートしたものを配列にし
て返す。permutationsでは、cubics()の結果を他の立法
数と比べ、同じものを配列に入れて返す。mainでは、同じものが5つあれば、
立法数を返す。

cubics()の
cubics << [cubic, cubic.to_s.enum_for( :each_char ).sort.inject{|conb,s| conb+s}]

は当初以下のようなコードだった。これだと答がでるまでに15秒以上かかっていた。

cubics << [cubic, cubic.to_s.enum_for( :each_char ).sort]

同様のことをC++で書くと100msecかからないので、Rubyといえども遅すぎる。
調べてみると処理速度改善に一番効きそうなのはpermutations()の以下のコードだ。

base[1] == cubic[1]

これの左辺値は当初 ["4","5","6","6","6"] のようなArrayだったので、"45666"のようなStringに変えたらどうかと試してみた。すると15秒だったのが4秒に短縮できた。やったー。どうもArray.==は再帰的にエレメントを比較しているのに対し(Array.cを最後まで読み切れてないけど,,,) SrtingだとCのmemcmp()に行きつく。たぶんこれが原因だろう。
これでもまだ遅いのだけど、==が左辺値のメソッドだと知っていることで、簡単に改善すべき箇所に気づける良い例だと思った。