【Swift】リングバッファーのQueueでベンチマークテスト

【Swift】リングバッファーのQueueでベンチマークテスト
【Swift】リングバッファーのQueueでベンチマークテスト

Queue
Queue

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

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

swift
var max:Int!
var data:[Any] = []

init(_ max:Int) {
    self.max = max
}

func enqueue(_ obj:Any) -> Bool {
    if data.count > self.max - 1 {
        return false
    }
    data.append(obj)
    return true
}

func dequeue() -> Any? {
    if data.count > 0 {
        let obj = data[0]
        data.remove(at: 0)
        return obj
    }
    return nil
}

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

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

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

リングバッファ
リングバッファ

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

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

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

swift
var head:Int = 0
var num:Int = 0
var max:Int = 0
var data:[Any]!
var debug = false

init(_ max:Int) {
    self.max = max
    self.data = Array<Any>(repeating: -1, count: max)
}

@discardableResult
func enqueue(_ obj:Any) -> Bool { // キューが一杯だったらfalseを返す
    if num < max {
        self.data[(head + num) % max] = obj
        num = num + 1
        return true
    }
    return false
}

@discardableResult
func dequeue() -> Any? {
    if num > 0 {
        let obj = data[head]
        data[head] = -1
        num = num - 1
        head = (head + 1) % max;
        return obj
    }
    return nil
}

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

swift
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())
    }

}

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

動作確認
動作確認

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

swift
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 maxQueue.swift(seconds)RingQueue.swift(seconds)
109.95411.201
10012.37710.863
100033.23311.789
10000232.33110.712

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

QueueのMax sizeが小さい場合は、どちらのアルゴリズムでも大した差はありません。しかし、Max sizeが大きくなるほどQueue.swiftでは顕著に速度が遅くなってしまいました。これは最初に説明した通り、C言語と同様にSwiftでもArrayをシフト処理をしているからだと思われます。

一方、RingQueue.swiftの方は、Max sizeを変えても速度変化はみられませんでした。それもそのはず、Arrayそのものは増やしたり、減らしたりせず、参照するインデックスを足したり減らしたりしているだけなので、QueueのMax sizeには依存しないのです。

関連記事

最後までご覧いただきありがとうございます!

▼ 記事に関するご質問やお仕事のご相談は以下よりお願いいたします。
お問い合わせフォーム