kona0001の日記

Rubyで競プロする人の日記です

本番で使えるRubyの定数倍高速化手法【競技プログラミング | Atcoder】

※本記事の対象はRubyで解く競技プログラミングにある程度慣れた方です。

参考までに、緑(rating:800)くらいの方からを対象にしています。 「ABCのC問題でTLEが取れない…」という方はそもそも解法が間違っている可能性があるので(ABC189-Cを除く)、別の方の記事もしくは公式解説を見る事をオススメします。



はじめに

Ruby競技プログラミングをする際に、TLE(Time Limit Exceeded)に悩まされる事が多々あります。その原因として挙げられるのは以下の4つです。

  1. そもそも解法が間違っている … ①
  2. Whileが抜け出せていない … ②
  3. 実装が悪い … ③
  4. 言語的に通せない … ④

①はそもそも解法が間違っていて、計算量が爆発している一番よくある例ですね。ABC(Atcoder Biginner Contest)でいうところのC問題から意識する必要があります。この場合どのように実装を変えても、なんなら高速な言語に書き換えてもTLEは取れません(例外もありますが)。

解法そのものを変え、計算量の削減をする必要があります(本記事では扱いません)。

②はたま~に起こる、whileなどのループを抜け出せていないパターンです。この場合コードを見直すことで修正できることが多いですが、それに気づけない場合泥沼にハマって抜け出せなくなります。 回避方法として、プログラムの挙動をアルゴリズムとして記述し、具体的なシミュレートをすると気づける事が多いです。紙に書くなどして整理すると、この類のTLEは回避しやすくなるでしょう(この場合バグによるWAも同様に回避しやすくなります)。


ここからが本題で、③と④の場合。

同じ解法であっても、実装によって処理速度が大幅に変わる事があります

特に、計算量(106)を超える辺りからちょっとコードの書き方を変えるだけで100msもの実行時間が短くなったりします。AtcoderCodeforcesでは基本的に実行時間制限が2secと短いので、100msの短縮が計算量の大きな問題でACできるかどうかに深く関ってきます。例えば、二次元グリッド問題(座標平面に沿って操作を行っていう問題)で想定解法なのにTLEが出るのはRuby競プロあるあるだと思います。

本記事では僕が意識して実戦している「定数倍高速化手法」についてまとめていきます。 ④については、記事の最後で触れています。

※定数倍高速化:いわゆる処理速度の高速化。同じアルゴリズムでより早く処理するためのテクニック。

以下、実行環境はAtcoderのコードテストを用いています(厳密な計測はしていませんのであしからず。。)Ruby verionは2.7.1です。


定数倍高速化手法

1.繰り返しではWhileを使う(重要度★★★★★)

繰り返し処理においてforやtimesは遅いので、Whileを使うようにしましょう。これは多重ループの際に本領を発揮します。

#ループ回数を数えるプログラム
n = gets.to_i
cnt = 0
for i in 0..n
    for j in 0..n
        cnt += 1
    end
end
#whileで高速化
n = gets.to_i
cnt = 0
i = 0
while i < n
    j = 0
    while j < n
        cnt += 1
        j += 1
    end
    i += 1
end
n 100 1000 2000 5000
for 61 106 201 1002
while 64 86 150 615

計算量: O(N2), 単位[ms]

別途インデックスを定義する必要がありコードが冗長になりますが、処理速度とのトレードオフと考えましょう。また注意点としてスキップ処理にnextを用いるとインデックスが更新されないので、正しい処理をさせるためにコードが難解になる可能性があります。

#nまでの偶数の和を数えるプログラム
n = gets.to_i
cnt = 0
for i in 1..n
    next if i%2==0
    cnt += i
end
n = gets.to_i
cnt = 0
i = 1
while i < n
    next if i%2==0  # ここでスキップ処理が入ると
    cnt += i
    i += 1  # インデントの更新も処理されなくなる
end


2.二次元配列は一次元配列として参照する(重要度★★★★☆)

動的計画法などで、dp[i][j]という書き方をすることがよくあります。ここで

dpi = dp[i]

のように、一つ目の添え字を参照して用いることで処理速度がグっと早くなります。

#n×nの配列を1回ずつ参照するプログラム
n = gets.to_i
dp = Array.new(n){Array.new(n,1)}
cnt = 0
for i in 0..n-1
    for j in 0..n-1
        cnt += dp[i][j]
    end
end
#一次元配列として参照するプログラム
n = gets.to_i
dp = Array.new(n){Array.new(n,1)}
cnt = 0
for i in 0..n-1
  dpi = dp[i]
  for j in 0..n-1
    cnt += dpi[j]
  end
end
n 100 1000 2000 5000
二次元参照 65 119 295 1481
一次元参照 63 114 275 1374

計算量: O(N2), 単位[ms]

(上のプログラムでは1個だけしか参照していませんが、参照すればするほど速くなります)

三次元の場合にも、二次元の参照を経てから一次元参照とすることで同様に高速になります。速くなる理由としてメモリアクセスがどうのこうのという原理があるわけですが、この記事では省略します。


3.文字列は文字配列として処理する(重要度★★★★★)

文字列は遅いです。Rubyでは

string = "文字列"
string[0] # => "文"

のように文字列に対して添え字を指定することで一文字取り出せますが、この処理は遅いです。対策として文字列に対するメソッドcharsを使いましょう。これは、文字列オブジェクトを文字の配列オブジェクトに変換するとても便利なメソッドです。

string = "文字配列"
string = string.chars # => ["文","字","配","列"]
string[0] # => "文"

こうすることで、一文字ずつ見ていく処理は変換前と同じ処理を同じコードで行うことが出来ます。ただし、複数文字を同時に扱う場合には注意が必要です。 ついでに、分解した後の文字配列オブジェクトはjoinメソッドを用いることで文字列に復元できます。

string = "文字列"
string = string.chars # => ["文","字","列"]
string.join # => "文字列"


4.一行処理+ifは後置if

追記あり
コメントにて「後置ifでも処理速度が変わらない、もしくは逆転することもあった」との報告を受けました。自分としては通常ifを後置ifに変えて処理速度が100msほど早くなった問題があったため(どれかは忘れました…)本記事のリストに入れていましたが、どうも不確実のようです。議論にはなると思うので、項目自体は消さずに残しておきます。条件等検討ついたらまた改めて追記します。

※再度追記
結論から言って後置ifでも実行時間は速くなりませんでした。Atcoderのジャッジシステムの計測値のぶれによるものでした。参考までに、同じコードを2回提出したら片方が2051msでTLEが出て、もう片方が1859msでACできたことを確認しました。そのタイミングで後置ifに変更しACできた経験から、間違った知識がインプットがされていたみたいです。お騒がせして申し訳ないと共に、指摘していただき本当にありがとうございました…!


4.グラフなどで配列を使わない(重要度★★☆☆☆)

グラフや優先度付きキューなどで配列を使わないようにすると処理速度が速くなります。たとえば頂点数2のグラフにおいて、「頂点1から頂点2まで距離5である」というのを

N = 2
graph = Array.new(N+1){Array.new}
graph[1] << [2,5]

と記述するところを、mod(N)空間を用いることで配列を使わずに

N = 2
graph = Array.new(N+1){Array.new}
graph[1] << 2+5*N

と記述できます。これを取り出すためには

graph[1].each do |v|
    to = v%N  # => 行き先
    distance = v/N  # => 距離
end

とすればいいです。頂点数が多い場合や、距離にマイナスが入る場合は変換作業を工夫する必要があります。ですが、基本的に頂点数が(106)以上になることは無いので、変換した値が大きすぎて処理速度が落ちることもそうそう起こりません。Ruby多倍長整数であるというメリットをふんだんに使っていきましょう。(可読性がどうしても下がるのは仕方がないと割り切りましょう。。。)


これを用いたACコード(他にも様々な定数倍高速化を用いています)
Submission #22908498 - ZONe Energy Programming Contest

(ZONeエナジープロコン - E問題(Sneaking))


5.文字の比較を数値で行う(重要度★☆☆☆☆)

最終手段です。これを使わないとACできなかった問題は今のところ1つだけです。とはいえかなり実行時間が早くなったので、最終手段として知っておくといいかも。例えばグリッド問題では、マス目に行き止まりなら「#」、通れるなら「.」のように入力が与えられがちです。これを、文字コードの数値として管理し、数値同士の比較を行います。例えば「#」の文字コードは35で、「.」の文字コードは46です。壁が行き止まりかどうかみるなら

grid[i][j] == 35

通れるかどうかなら

grid[i][j] == 46

のようにすることで、処理速度が速くなります。余談ですが上記のコードは

gridi = grid[i]
gridi[j] == 46

とすることでより速く処理できます(2の二次元配列参照のテクニック)
文字を文字コードに変換するのはord関数やbytes関数でできます。覚えておくといつか使うときが来るかもしれません。


これを用いたACコード(他にも様々な定数倍高速化を用いています)
Submission #19542530 - KEYENCE Programming Contest 2021

(キーエンスプロコン2021 - C問題(Robot on Grid))


6.bit演算を使う(重要度★★☆☆☆)

bit演算に代替できるものはそうした方が早いです。例えば

#2のべき乗
2.pow(n)  #こっちよりも
1<<n  #こっちの方が早い
#偶奇判定
n%2 == 1  #こっちよりも
n&1 == 1  #こっちの方が早い

この2つは結構使います。偶奇判定の方は可読性と引き換えに処理がとても速くなります。

演算回数 107
pow 1260[ms]
シフト演算 1061[ms]
演算回数 107
n%2 555[ms]
n&1 464[ms]


7.配列の複製は最小限にする(重要度★★☆☆☆)

配列やハッシュを複製し、元の配列を参照しないように値の更新をしたいときはdupというメソッドが使えます。

arr = [2,3,5,7]
tmp = arr.dup
tmp[0] = 1
p tmp[0]  # => 1  コピー先の値は変わるが
p arr[0]  # => 2 コピー元の値は変わらない

これはとても便利なメソッドである反面、計算量が配列の大きさ分かかります。厳密には「配列を参照し、値の更新が行われるときに初めて配列の複製をO(N)かけて行う」らしいです。

※ユニさん。Rubyの言語仕様まわりでいつもお世話になっています……!

ということでむやみにdupを多用するのはやめましょう。定数倍高速化とは若干異なりますが、先日のABC(ABC203-E - White Pawn)で引っかかったポイントとなったので紹介しました。改めて考えるとコピーサイズ分の計算量かかるの当たり前なんだよな……。


またこの話とは別に、二次元配列に対して雑にdupを使うと痛い目に合うので丁寧に1行ずつdupしていきましょう(1敗)。

※雑に解説すると二次元配列に対するdupは参照が残り複製ではなくなる。


まとめ

以上、Rubyにおける定数倍高速化手法についてでした。あらためて見返すとRubyならではの高速化手法はそんなに無かったかも。

まとめとしては、1と2と3さえ意識できていればだいたいの問題は通せると思います。特にWhileは書きづらいですが、シンプルに処理が速くなるので慣れるためにも積極的に使うといいでしょう。(可読性は大きく落ちるので競プロ以外での仕様は微妙かも。)

ここに紹介したもの以外にも「枝刈り全探索」や「賢いダイクストラ」など、アルゴリズムレベルでの定数倍高速化手法もあるので調べてみるといいです。言語関係なく実践できるので記事も充実しておりオススメです。学びも多いです。


最後に

僕は定数倍高速化を学んでから、通せるようになった問題の幅が広がったという実感があります。それまで(4*106)くらいの計算量が限界だと思っていたのが、だいたい(107)までの計算量の問題が通せるようになりました。大きな成長です。大嫌いだった二次元グリッド問題も苦手意識がかなり無くなりました。

ですが、どうしても言語的な限度はあります。

例えばABC187-FABC189-Cは、想定解法ではどうしてもRubyでACできません

例えば典型テクニックである半分全列挙は、少し工夫して実装しないとTLEになります。

例えば巡回セールスマン問題は、頂点数18でも上手く実装しないと実行時間ギリギリになります。

こういうのは「仕方ない」と割り切る必要があります。

今のところ水色difficulty以下の問題は全て解きましたが、RubyでACできなかった問題はありませんでした。これからを埋めていくところですが、RubyでのAC者が一人もいない計算量厳しめの問題が出始めます。不安ですが、どこまでRubyでいけるのか挑戦してみようと思います。

スクリプト言語である以上、速度はどうしても早い言語に負けてしまいます。それ以上に、スクリプト言語であることのメリットを有効活用できればいいと思います。

例えば間違えなく早解きでは有利です。

例えばRuby以上に書いてて楽しい言語は無いです(これは個人差あり)

同じスクリプト言語であるPythonのメリットは「教材の多さである」と言う人がいます。その通りですが、これはRubyでも十分達成可能だと思っているので、負けじと質の良い記事をたくさん発信していきたいです。

いろいろな高速化を紹介しましたが、それでもRubyで解けない時、残念ですがそのときは別言語を使わざるを得ないでしょう。移行先としてはC++Rustあたりかな?Pythonへの移行はあまりオススメしません(Python自体はRubyより遅いです。PyPyは早いらしいですが、それでもTLEに悩まされている報告を見ます)。

また、ほぼほぼRubyのコードのまま実行できるコンパイル言語Crystalがあり、これはとてもオススメです。配列の型宣言が厳密になったくらいで、コードが基本そのままで速度が10倍とかになります。僕は、どうしても困ったときにはCrystalを使っています。ただし、ユーザーの少なさ・教材の少なさがデメリットになります。



この記事で一人でもTLEに苦しむ人が減ればいいなぁ。 あともっとRuby広まれ



- 参考にした記事 : Ruby競プロTips(基本・罠・高速化108 2.7x2.7)
Rubyに関するTipsがすべて詰まっています。文量は多いですが、具体的な計測値も出しつつ定数倍高速化手法やその他Tipsについてまとまっています。Ruby使いは必見です。