LoginSignup
0

More than 1 year has passed since last update.

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

Last updated at Posted at 2022-04-20

はじめに

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

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

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

まとめ

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0