Rubyで使える！競技プログラミング、小手先TLE対策 #Ruby

AtCoderでRubyを使って競技プログラミングをしている物好きな人はいますかね。私もです
Rubyで競技プログラミングをしていると、TLEとの戦いになることがあります。
そんなとき、オーダーレベルでのアルゴリズムの改良ができれば最高ですが、そんなひらめきがいつでも降ってくるわけがない。
というわけで今回は小手先のテクニックによって少しでも実行時間を短くする方法を紹介します。

バージョン情報

Ruby 2.3.3

文字列から文字の比較はしない！

str = 'abc'
str[0]
# => "a"

ベンチマークは後で乗せますが、このstr[0]はめっちゃ遅いです・・。おそらく添え字アクセス時に、Stringの新しいインスタンスを作成しているせいでしょう。
なので、.charsメソッドで1文字毎の配列にしてしまいます。

str = 'abc'.chars
# => ["a", "b", "c"]
str[0]
# => "a"

このアクセスであれば、添え字アクセス時に新しいStringのインスタンスは作られないので、ループを回す場合は結構早くなります。

さらに、文字列の比較よりは数値の比較のほうが早いですよね。なので、.codepointsメソッドで数値として持ってしまうのが良いです。

codepoints = 'abc'.codepoints
# => [97, 98, 99]
str[0]
# => 97

では上記3パターンのベンチマークを取ってみます。

require 'benchmark'

str = 'abc' * 100
N = 10000000
A = 'a'

Benchmark.bmbm do |x|
  x.report 'str' do
    N.times do
      str[0] == A
    end
  end

  x.report 'chars' do
    chars = str.chars
    N.times do
      chars[0] == A
    end
  end

  x.report 'codepoints' do
    codepoints = str.codepoints
    N.times do
      codepoints[0] == 97
    end
  end
end

結果はこう。

Rehearsal ----------------------------------------------
str          1.290000   0.000000   1.290000 (  1.299665)
chars        0.500000   0.000000   0.500000 (  0.498776)
codepoints   0.400000   0.000000   0.400000 (  0.402605)
------------------------------------- total: 2.190000sec

                 user     system      total        real
str          1.280000   0.000000   1.280000 (  1.281719)
chars        0.490000   0.000000   0.490000 (  0.498172)
codepoints   0.390000   0.000000   0.390000 (  0.394821)

codepoints早いですね。
なので、大量のループがあり、その中で文字列中の1文字を比較するような時は、文字列で持たずにcodepointsで持っておくとTLEを回避できることがあるかもしれません。

ネストの深い配列を避ける！

こんな二次元配列があるとして、

DATA = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

こんな風にアクセスするのが普通かもしれません。

3.times do |i|
  3.times do |j|
    DATA[i][j]
  end
end

が、ループの中においては、これより若干早くなる可能性がある書き方が存在します！
それが、これ。

3.times do |i|
  data = DATA[i]
  3.times do |j|
    data[j]
  end
end

ほんとに！？
って思うかもしれませんが、ベンチマーク取ってみます。

require 'benchmark'

N = 5000

DATA = N.times.map { N.times.map { rand(100) } }

Benchmark.bmbm do |x|
  x.report 'direct' do
    N.times do |i|
      N.times do |j|
        DATA[i][j]
      end
    end
  end

  x.report 'tmp' do
    N.times do |i|
      data = DATA[i]
      N.times do |j|
        data[j]
      end
    end
  end
end

Rehearsal ------------------------------------------
direct   1.000000   0.000000   1.000000 (  0.999422)
tmp      0.870000   0.000000   0.870000 (  0.875144)
--------------------------------- total: 1.870000sec

             user     system      total        real
direct   1.040000   0.000000   1.040000 (  1.055139)
tmp      0.870000   0.010000   0.880000 (  0.872905)

若干早いですね。
この若干によりTLEを回避できるかもしれません！

終わりに

mapよりmap!を使うだとか、巷でよく言われている小手先のテクニックについてではなく、あまり見ない2つの手法を紹介しました。

早い言語を使っている皆さんは、なんでこんな苦労をしてまでRubyで競技すんの？Mなの？
と思われるかもしれませんが、まぁ、これはこれで楽しんでるんで気にしないでください！