こんにちは!

今回は前回のLT発表の内容をご紹介いたします。

olivaでは毎月の帰社日で全員集まった際に、LT発表として技術系の発表を行なっています。

前回私の発表した内容をお伝えいたします。

概要

  • 競技プログラミングの問題を題材に、RubyとGoの簡単な速度比較
  • RubyのコードにGoを組み込んで処理速度アップを図ってみる

 

Rubyは本当に遅いのか?

今回の題材はこちらの問題↓

AtCoder Regular Contest 104 B – DNA Sequence

ポイントは、競技プログラミング界においては、「10の7乗はおそらく間に合う」レベルの計算量となります。

 

書いたコード1

まず以下のように解いてみました。(実際にAtCoder参加中に急いで書いたものなので、コードについてはご愛敬で)

(奇数個では相補鎖は作れないので、偶数個だけ判定)

  1. 2個の分割から全てまでの部分列を取得
  2. Aの個数==Tの個数, Cの個数==Gの個数 をカウント

 

間に合いませんでした・・・。

カウント部分で、再度全部チェックしているため、そこが遅いと考えて修正しました。

 

書いたコード2

(奇数個では相補鎖は作れないので、偶数個だけ判定)

  1. 2個の分割から全てまでの部分列を取得
  2. A個数==Tの個数, Cの個数==Gの個数 をカウント

カウントのループを1回でできるように改善

ジャッジ改善せず・・・

ここで、計算量は、nの2乗(今回はn=5000)のため、2.5×10の7乗です。

処理内容は1文字のStringを比較して、カウントし、最後にIntegerの比較をしているだけなので、ギリギリ間に合いそうなのに・・・

 

書いたコード3

こんな形で書いて、ジャッジが通りました。

カウントのループを1回で済ませる

  1. n番目のA, T, C, Gをチェック

(2次元配列に保存)

  1. n番目までのA, T, C, Gの個数を足し合わせる。
  2. 部分列の右と左の差を求めることで部分列の中の個数を計算する。

累積和という考え方で、毎回足すのではなく、いったん足し合わせた結果を用いて、部分列の和を求める手法です。

(計算の流れはスライド参照)

 

想定解

https://atcoder.jp/contests/arc104/editorial/157

ほぼ、解2と同じでは・・・?

結論:やっぱり・・・Rubyは若干遅い

 

Goだとどうなるのか

書いたコード2と同じように書いてみました。

普通にジャッジが通って、それも、Rubyで累積和を使ったコード3よりも6倍速いという結果に・・・

 

Rubyの一部をGoに置き換えられないか?

もっと何かしてみようということで、RubyでGoのコードを使う方法を調べて使ってみました。

RubyでGoを使うための手順

 

TLEになってしまったRubyのコードの一部をGoに置き換える

Go(loop.go)

Ruby

スライドでは1000文字程度でしかやっていないので、若干早いかな程度でした。

 

n=40_000にして、時間を測ってみた

結果が以下です。(20倍くらい速い?)

 

後日談

当然Go純粋の方が圧倒的に速く、「書いたコード2」も書き方次第で通りました。

ちなみに、n=40000の時は、Go単体の場合は以下の速度が出ました。

(RubyにGoを組み込んだものと比較しても圧倒的に速い)

 

おしまい