RingBuffer(待ち行列)のQueueを作って100万回の処理【Swift】



突然ですが、プログラミングでQueueを処理するにはどうしますか?



SwiftでQueueを作ってみました。
次のような単純なプログラムでサクッと作れます。



しかしこのようなアルゴリズムは、問題があります。
特にC言語の場合では致命的な問題になる場合があります。

このプログラムでは配列の先頭を削除していますが、内部では同時に配列全体を前方にシフトする処理を行っているので、配列が大きくなればなるほど速度が遅くなってしまうのです。




何か良い方法があるのではと思いQueueのプログラムを調べていくと、リングバッファーというアルゴリズムが見つかりました。




サイズの決まった配列を作り、輪のように見立てて考えます。0番から順番にデータを入れていきます。一周回ったら、また0番に戻ってデータを入れていきます。こうすることで、配列をシフトする処理の必要が無くなります。カウントの管理はheadとnumの値で管理します。enqueueしたらnumカウントを1プラスするようにし、dequeueしたら、headカウンタを1プラスします。enqueueすべきインデックスはhead+num番となります。dequeueすべきインデックスはhead番となります。


リングバッファーの説明およびプログラミングは、こちらのサイトが大変参考になりました。
» 待ち行列


さて、このリングバッファーのQueueを、Swiftでもやってみたいと思いプログラミングしてみました。


動作確認を行うために、XCTestで次のプログラムを組んで確認してみます。

let max = 5
let loop = 3
var num = 0
func sequenceNo() -> Int {
    num = num + 1
    return num
}

func testRingQueue() {
    let q = RingQueue(max)
    
    for _ in 0..<loop {
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.dequeue()
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.enqueue(sequenceNo())
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
    }

}


動作確認の結果です。一つ一つ丁寧に追っていくと、ちゃんとキューイングできていることがわかります。





さらに、最初に作ったQueue.swiftと、先ほどのRingQueue.swiftで速度比較実験を行ってみました。
次のようなXCTestCaseを書いて、速度を比較してみます。

let max = 1000
let loop = 100*100*100

var num = 0
func sequenceNo() -> String {
    num = num + 1
    return "hogehogehogehoge\(num)"
}

func testQueue() {
    print("[Queue.swift]\n\n\n")
    let q = Queue(max)


    for _ in 0..<loop {
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.dequeue()
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.enqueue(sequenceNo())
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
    }

}


func testRingQueue() {
    print("[RingQueue.swift]\n\n\n")
    let q = RingQueue(max)
    
    for _ in 0..<loop {
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.dequeue()
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.enqueue(sequenceNo())
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
        q.dequeue()
        q.dequeue()
        q.enqueue(sequenceNo())
        q.enqueue(sequenceNo())
    }

}


QueueのMax sizeを変えて実験してみました。100万回のループ処理における速度結果を次に示します。

Queue max Queue.swift(seconds) RingQueue.swift(seconds)
10 9.954 11.201
100 12.377 10.863
1000 33.233 11.789
10000 232.331 10.712

上記データをグラフにしてみました。縦軸はQueueのMax size、横軸は100万回処理にかかった秒数を表します。




QueueのMax sizeが小さい場合は、どちらのアルゴリズムでも大した差はありません。しかし、Max sizeが大きくなるほどQueue.swiftでは顕著に速度が遅くなってしまいました。これは最初に説明した通り、C言語と同様にSwiftでもArrayをシフト処理をしているからだと思われます。
一方、RingQueue.swiftの方は、Max sizeを変えても速度変化はみられませんでした。それもそのはず、Arrayそのものは増やしたり、減らしたりせず、参照するインデックスを足したり減らしたりしているだけなので、QueueのMax sizeには依存しないのです。


Swift実践入門 ── 直感的な文法と安全性を兼ね備えた言語 WEB+DB PRESS plus

本書は、Swiftの言語仕様と実践的な利用方法を解説した入門書です。Swiftは簡潔な言語ですが、その言語仕様を理解し、正しく使うことはけっして容易ではありません。Appleの公式ドキュメントをはじめとして、どんな言語仕様があり、それらをどのように使うかに関しては豊富な情報源があります。しかし、それらがなぜ存在し、いつ使うべきかについてまとまった情報があるとは言えません。本書は、読者のみなさんの「なぜ」や「いつ」を解消することにも主眼を置いています。今回の改訂で、新バージョンのSwift 5に対応しました。

KindleAmazon

あなたにおすすめ