crystal の AtCoder における Deque の使用による速度改善

はじめに

AtCoder さん、いつもお世話になっております。

私は、下記のトランスパイラを夢見ている者ですが、Dequeの使用により実行時間の改善が見られましたので、ここに投稿いたします。

003 - Longest Circular Road（★4）

n = read_line.to_i
- ab = Array.new(n + 1){ [] of Int32 }
+ ab = Deque.new(n + 1){ [] of Int32 }
- f = Array.new(n + 1, 0)
+ f = Deque.new(n + 1, 0)
(n - 1).times do
  a, b = read_line.split.map(&.to_i)
  ab[a] << b
  ab[b] << a
end
- que = [] of Int32
+ que = Deque(Int32).new
f[1] = 1
que << 1
while que.empty?.!
  r = que.shift
  ab[r].each do |x|
    if f[x] == 0
      f[x] = f[r] + 1
      que << x
    end
  end
end
que << f.index(f.max).not_nil!
- f = Array.new(n + 1, 0)
+ f = Deque.new(n + 1, 0)
f[que[0]] = 1
while que.empty?.!
  r = que.shift
  ab[r].each do |x|
    if f[x] == 0
      f[x] = f[r] + 1
      que << x
    end
  end
end
puts f.max

ここでは、何も考えずにArrayをDequeに書き換えます。

	Array	Deque	参考(Ruby)
実行時間(ms)	664	84	249

Array版では、トランスパイル前のRuby版より遅かったのですが、それが改善されました。

crystal#Deque

Deque has a subset of Array's API. It performs better than an Array when there are frequent insertions or deletions of items near the beginning or the end.
Dequeには、ArrayのAPIのサブセットがあります。最初または最後の近くでアイテムの挿入または削除が頻繁に行われる場合は、配列よりもパフォーマンスが向上します。

公式の通りpush/pop/shift/unshiftで速くなる様です。
デメリットは、分かる範囲ですが、sortメソッドがないことです。

D - Cylinder

q = read_line.to_i
- a = Array(Array(Int64)).new
+ a = Deque(Array(Int64)).new
q.times do
  que = read_line.split.map(&.to_i64)
  if que[0] == 1
    a << [que[1], que[2]]
  else
    ans = 0i64
    t = que[1]
    while t > 0
      b = a.shift
      if t >= b[1]
        t -= b[1]
        ans += b[0] * b[1]
      else
        ans += t * b[0]
        a.unshift([b[0], b[1] - t])
        t = 0
      end
    end
    puts ans
  end
end

Array版ではTLEになりますが、Deque版は高速です。

	Array	Deque	参考(Ruby)
実行時間(ms)	TLE	119	356

まとめ

crystalのDeque使用により実行時間が改善される場合があることが分かりました。