Swift

Q? 突然ですが、プログラミングでQueueを処理するにはどうしますか？ SwiftでQueueを作ってみました。次の単純なプログラムでサクッと作れました。 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番となります。 リングバッファーの説明およびプログラミングは、こちらのサイトが大変参考になりました。 http://www.cc.kyoto-su.ac.jp/~yamada/ap/queue.html SwiftでQueue さて、このリングバッファーのQueueを、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で次のプログラムを組んで確認してみます。 ...