🐩

JuliaでQueueを実装する

1 min read 2

下心

JuliaでStackを実装する」という記事で実装したstackは直前に追加した要素を取り出せるデータ構造でした。
しかし、古い要素を取り出すデータ構造も欲しいです。これがqueueと呼ばれる物です。

queueの操作(簡単な説明)

stackと同様、queueの構成要素は以下の3つです。

  1. 要素の初期化
  2. 要素の追加
  3. 要素の削除
  4. 空(カラ)かの確認

しかし、今回は要素の追加は配列の末尾に、要素の取り出しは配列の先頭から行うため、queueには配列と、その末尾の要素の位置情報の他に先頭の情報も必要です。

実装

まずは初期化です。

mutable struct queue{T}
   last :: Int 
   front :: Int 
   length :: Int
   data :: Array{T,1}
   function queue{T}(N::Int) where T
       new(1,1,N+1,Array{T,1}(undef,N+1))  #空か満杯かを区別するために、N+1個の要素を用意
   end 
end

構造体の構成要素はlast, front, length, dataです。ここで以下の2つの工夫があります。

  1. lengthを定義
  2. 配列を1つ大きく確保

2つとも後の実装を見ていただくと理由がわかりますが、端的にはそれぞれ

  1. 要素の追加、削除を繰り返すとindexがどんどん増えるので、それを抑えるため
  2. queueが空か満室かを区別するため

です。

次に、要素の追加です。ほとんどstackと同様ですが、今回はlastに配列の最後の要素の次のindexを記憶しています。
加えて、lastがどんどん大きくなることを防ぐために、last=lengthになったら次のindexを1に戻しています。

function push!(q :: queue, sth)
    q.data[q.last] = sth
    q.last = ifelse(q.last == q.length, 1 , q.last+1)
end

要素の削除もあまり変わりません。frontの要素を削除すると、次の要素の位置はfront+1となります。ここでも同様に、frontが大きくなりすぎないようにlengthで引き戻しています。

function pop!(q :: queue)
    if !isempty(q)
        tmp = q.data[q.front]
        q.front = ifelse(q.front == q.length, 1 , q.front+1)
        return tmp
    else
        error("queue is empty")
    end
end

最後はqueueが空かの確認です。これはlastがfrontと同じ位置かを調べれば良いです。

function isempty(q :: queue)
    q.last==q.front
end

動作確認

動作確認には以下のコードを用意しました。今回の実装の良いところはCharもqueueに追加できることです。

q = queue{Char}(10)

for s in 'A':'J'
    push!(q,s)
end

while !isempty(q)   
    println(pop!(q))
end

for s in 'A':'J'
    push!(q,s)
end

while !isempty(q)   
    println(pop!(q))
end

AtCoderなどで使う際には念のため確認してください。

Discussion

スミマセン素朴な疑問です。AtCoder等の競プロやってない人のシロウト質問です。

Juliaには配列をStackやQueueとして扱うための関数群は既に用意されている(push!/pop!/popfirst!)のですが、それだとパフォーマンス的に問題があって簡単にTLEするからきちんとデータ構造自分で作った方が良い、ということでよろしいでしょうか?

(もちろん私も実際にJuliaでプログラミングする際にパフォーマンス目的や可読性目的でこうしたデータ構造に適切な名前(型)を付けて実装すると言うことは良くやるのでその意味では至極真っ当だしその行為にはむしろ肯定的です!)

ありがとうございます。早くなるだろうという先入観からこの記事を書いていましたが、以下のように簡単に調べたところJuliaの関数のほうが速かったです。(早めに気付けて良かったです。)
加えて、今回の実装ではメモリを1.5倍使っているので悪い実装例です。

今回のQueueでは

@time begin
    q = queue{Int}(100_000_000)
    for i in 1:100_000_000
        push!(q,i)
    end
    for i in 1:100_000_000
        pop!(q)
    end
end

を4回実行すると

19.087762 seconds (300.00 M allocations: 5.215 GiB, 7.92% gc time)
15.513442 seconds (300.00 M allocations: 5.215 GiB, 8.03% gc time)
12.624149 seconds (300.00 M allocations: 5.215 GiB, 9.64% gc time)
14.682942 seconds (300.00 M allocations: 5.215 GiB, 10.40% gc time)

次に、Juliaの関数を使って

@time begin
    v=Vector{Int}(undef,0)
    sizehint!(v,100_000_000)
    for i in 1:100_000_000
        Base.push!(v,i)
    end
    for i in 1:100_000_000
        Base.pop!(v)
    end
end
14.395166 seconds (200.00 M allocations: 3.725 GiB, 6.48% gc time)
14.827620 seconds (200.00 M allocations: 3.725 GiB, 5.77% gc time)
12.918156 seconds (200.00 M allocations: 3.725 GiB, 10.80% gc time)
14.385135 seconds (200.00 M allocations: 3.725 GiB, 7.67% gc time)

従ってJuliaの関数のほうが速い。

ログインするとコメントできます