Help us understand the problem. What is going on with this article?

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

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なの?
と思われるかもしれませんが、まぁ、これはこれで楽しんでるんで気にしないでください!

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした