rubyではbit全探索よりcombination全列挙のほうが早かった

バージョン情報

Ruby 2.3.3

本題

過去にbit全探索の記事を書いていたことを思い出した。
ここにあるRubyの例で、全組み合わせの列挙をcombinationを使う方法を書いているんだけど、この記事によれば遅いって書いてあるんだよね。
でも、combinationすれば無駄なbitアクセスも無くなるし、早くなるのでは！？

また、Qiitaにこんな記事もあった。Rubyでbit全探索
ここでは、repeated_permutationを使った方法が出ているけど、これは全列挙なので遅そう。

というわけで、次の問題で計測してみた。

問題

24個の下記のデータがある。これを1〜24個ずつ選択する場合の組み合わせで、合計が100になる組み合わせの数を選べ

data = [2, 98, 88, 15, 83, 50, 19, 12, 45, 34, 43, 7, 33, 52, 64, 6, 1, 43, 99, 11, 16, 88, 44, 32]

検証コード


data = [2, 98, 88, 15, 83, 50, 19, 12, 45, 34, 43, 7, 33, 52, 64, 6, 1, 43, 99, 11, 16, 88, 44, 32]

Benchmark.bmbm do |x|
  x.report(:combination) do
    ans = 0
    1.upto(data.size) do |i|
      data.combination(i) do |s|
        ans += 1 if s.inject(:+) == 100
      end
    end

    puts ans
  end

  x.report(:repeated_permutation) do
    ans = 0
    [0, 1].repeated_permutation(data.size) do |bits|
      sum = 0
      bits.each_with_index do |bit, i|
        sum += data[i] if bit == 1
      end

      ans += 1 if sum == 100
    end

    puts ans
  end

  x.report(:bit_search) do
    ans = 0
    digits = data.size
    (1 << digits).times do |i|
      sum = 0
      digits.times do |d|
        sum += data[d] if i[d] == 1
      end

      ans += 1 if sum == 100
    end

    puts ans
  end
end

結果

Rehearsal --------------------------------------------------------
combination          233
 14.520000   0.010000  14.530000 ( 14.540594)
repeated_permutation 233
 34.200000   0.080000  34.280000 ( 34.337175)
bit_search           233
 29.050000   0.050000  29.100000 ( 29.199201)
---------------------------------------------- total: 77.910000sec

                           user     system      total        real
combination          233
 15.130000   0.040000  15.170000 ( 15.237124)
repeated_permutation 233
 35.120000   0.120000  35.240000 ( 35.354405)
bit_search           233
 28.760000   0.040000  28.800000 ( 28.847624)

というわｋで、repeated_permutationが一番遅くて、bit全探索が次に遅くて、combinationが一番早くて、って、combinationが一番早いじゃん！！
過去の自分、大嘘つきじゃん！？
過去の記事にはこれから謹んで訂正を入れさせていただきます。

一応、合計が100になるとかの計算話に、純粋にループだけの時間も計測してみた。
その結果、

Rehearsal --------------------------------------------------------
combination          0
  4.040000   0.050000   4.090000 (  4.105794)
repeated_permutation 0
 24.150000   0.050000  24.200000 ( 24.228031)
bit_search           0
 11.840000   0.010000  11.850000 ( 11.855139)
---------------------------------------------- total: 40.140000sec

                           user     system      total        real
combination          0
  4.200000   0.050000   4.250000 (  4.269952)
repeated_permutation 0
 25.610000   0.150000  25.760000 ( 25.910155)
bit_search           0
 12.710000   0.060000  12.770000 ( 12.900679)

うん、combination早いな。

さらに一応Ruby2.7.0でも試してみたけど、combinationバージョンはさらに高速になりましたね。
めでたしめでたし。
bit全探索で頑張るよりは、combinationを使っちゃった方がいいね・・。