Sponsor Link
環境&対象
- macOS Big Sur 11.3
- Xcode 12.5
- iOS 14.5
Ring Buffer
例えば、Array はバッファとして線形に確保され、一方の端から使われ始めます。確保されたバッファに収まらなくなった時には、バッファが自動的に拡張されます。
通常は、Array の持つこのような振る舞いが便利なのですが、特定数まで保持していれば、それ以上は不要というようなケースもあります。
例えば、待ち行列のような バッファの後ろには追加し、バッファの先頭からは削除するというような操作のみを行うケースでは、先頭部分の削除されたエリアを再利用したくなります。
このような時に、RingBuffer が使われます。
Wikipedia の説明は、こちら。
TDD (Test Driven Development) で作ります。
いつもどおり、TDD で作っていきます。
最初から Generics で考えるとややこしいので、まずは Int を対象に Ring Buffer で管理するもの作成し、その後 Generics を導入します。
仕様 = Test Spec
以下のような使い方ができる仕様で作ります。
インスタンス作成
capacity: で容量を指定できるようにします。
// 容量 4 の RingBuffer
var sut = RingBufferInt(capacity: 4)
この数字は、最大保持数を意味します。この例では、最大4つの要素を保持し、それ以上の要素は古いものから破棄していくことになります。
データ追加
write(_:) でデータを追加できるようにします。(最初は Int 限定ですが、Generics によって、タイプを拡張します)
var sut = RingBufferInt(capacity: 4)
// RingBuffer に 0 追加
sut.write(0)
// RingBuffer に 1 追加
sut.write(1)
保持データ数
count で、保持しているデータ数を取得できるようにします。(返却値は、最大で capacity です)
テストとして書くと以下のようになります。
var sut = RingBufferInt(capacity: 4)
sut.write(0)
sut.write(1)
// count で 保持しているデータ数を返却
XCTAssertEqual(sut.count, 2)
データ参照
インデックス経由でデータを参照できるようにします。
最新のデータを latestIndex で参照でき、最古のデータは、oldestIndex で参照します。
テストとして書くと以下のようになります。
var sut = RingBufferInt(capacity: 4)
sut.write(0)
sut.write(1)
sut.write(2)
XCTAssertEqual(sut.count, 3)
// 最も古いデータを参照 (i.e. 0)
XCTAssertEqual(sut[sut.oldestIndex], 0)
// 最も新しいデータを参照 (i.e. 2)
XCTAssertEqual(sut[sut.latestIndex], 2)
エラー処理
# Ring Buffer なので、書き込むことができなくなることはないです。
インデックスでデータを参照するので、インデックスが範囲外の時には、値として nil を返すものとします。
テストとして書くと以下のようになります。
var sut = RingBufferInt(capacity: 4)
sut.write(0)
sut.write(1)
sut.write(2)
// [5] は存在しないので、nil が返される
XCTAssertNil(sut[5])
テストコード
Capacity を超える数を write されるかどうかで2パターン作成しました。
func test_write_writeWithinCapacity_shouldKeepAsIs() throws {
var sut = RingBufferInt(capacity: 4)
sut.write(0)
sut.write(1)
sut.write(2)
XCTAssertEqual(sut.count, 3)
XCTAssertEqual(sut[sut.oldestIndex], 0)
XCTAssertEqual(sut[sut.oldestIndex+1], 1)
XCTAssertEqual(sut[sut.oldestIndex+2], 2)
XCTAssertEqual(sut[sut.latestIndex], 2)
XCTAssertEqual(sut[sut.latestIndex-1], 1)
XCTAssertEqual(sut[sut.latestIndex-2], 0)
XCTAssertNil(sut[5])
}
func test_write_writeMoreThanCapacity_shouldKeepOnlyCapacity() throws {
var sut = RingBufferInt(capacity: 4)
sut.write(0)
sut.write(1)
sut.write(2)
sut.write(3)
sut.write(4)
XCTAssertEqual(sut.count, 4)
XCTAssertEqual(sut[sut.oldestIndex ], 1)
XCTAssertEqual(sut[sut.oldestIndex+1], 2)
XCTAssertEqual(sut[sut.oldestIndex+2], 3)
XCTAssertEqual(sut[sut.oldestIndex+3], 4)
XCTAssertEqual(sut[sut.latestIndex ], 4)
XCTAssertEqual(sut[sut.latestIndex-1], 3)
XCTAssertEqual(sut[sut.latestIndex-2], 2)
XCTAssertEqual(sut[sut.latestIndex-3], 1)
}
実装 : RingBufferInt
いきなり Generics を入れるとわかり難いので、まずは Int で動くものを作成します。
public struct RingBufferInt {
let capacity: Int
private var buffer:[Int?]
private(set) public var latestIndex: Int = -1
private(set) public var oldestIndex: Int = 0
public var count: Int {
return (latestIndex - oldestIndex + 1)
}
public init(capacity: Int) {
self.capacity = capacity
self.buffer = Array(repeating: nil, count: capacity)
}
public mutating func write(_ value: Int) {
latestIndex += 1
buffer[latestIndex % capacity] = value
if capacity count {
oldestIndex += 1
}
}
subscript(index: Int) -> Int? {
get {
guard (oldestIndex <= index && index <= latestIndex) else { return nil }
guard let value = buffer[index % capacity] else { return nil }
return value
}
}
}
上記のコードは、すでに先に記述したテストをパスします。
Ring Buffer の複数タイプ対応
上記の実装は、Int を保持する RingBuffer でした。実装コードを確認するとわかりますが、buffer で保持するデータとして Int を使用しているために、write や subscript の返り値に Int を使っていますが、その他の箇所では RingBuffer の保持する型が Int であることを必要としてはいません。
RingBuffer の仕組みとしては String でも Double でも同様に保持し処理することができます。
しかし、実際に String を保持しようとすると、様々な箇所の Int を String に置き換える必要があります。
対象とするタイプを変更するために、コードの大部分をコピーして、一部書き換えるという作業は、百害あって一利なし です。
そのようなケース向けに Swift が用意している機能が Generics です。
Generics
Buffer の保持するタイプを例に挙げていますが、もう少し簡単なケースから説明してみます。
Generics を使うと解決できる課題
以下のような、受け取った2つの Int を入れ替える関数を考えてみます。
func swapTwoInt(_ valueA: inout Int,_ valueB: inout Int) {
let tempA = valueA
valueA = valueB
valueB = tempA
return
}
使い方は以下のようになります。
var intA = 3
var intB = 5
swapTwoInt(&intA, &intB)
RingBuffer の時と同様に 、変数の中身の交換という処理自体は 対象が Int であることを必要としていません。Double であっても、 String であっても同様の処理を実装することはできます。
ただし、引数が それぞれの型であることが必要であるため、Double を入れ替える関数や String を入れ替える関数は 上記コードをコピーしたものを書き換える必要が発生します。
# なお、valueA と valueB は同じ型であることが必要です。
Generics を使うと このような課題を解決することができます。
Generics を使った関数
先の swapTwoInt(:,🙂 を Generics を使うと以下のように書き換えることができます。
func swapTwoValues<T>(_ valueA: inout T, _ valueB: inout T) {
let tempA = valueA
valueA = valueB
valueB = tempA
}
関数定義中の関数名の直後に<>で T を囲っています。この T は、<>で囲われることで placeholder として定義されています。(ここで定義された T がその後の引数定義に出てきています。必要であれば、関数内部でも使うことができるようになります)
Placeholder で使われる名称は、関連性がわかるような名称をつけることが推奨されています。
このケースでは、置き換える値のタイプという以上の意味はないので、T を使っています。意味を特に持たせたくない時には、T や U,V などの英字1文字がよく使われるようです。
関連性がわかる名称の例としては、Swift Standard Library の Dictionary の定義を参照すると placeholder で Key, Value という意味のある名称が使われていることが確認できます。
なお、関数定義時には、T は定義されている必要はありません。
この関数が使用される時に、T は決定される必要があります。つまり以下のように使用される必要があります。
var intA = 3
var intB = 5
swapTwoValues<Int>(&intA, &intB)
ですが、上記は “Cannot explicitly specialize a generic function” というコンパイルエラーとなります。
エラーの意味は、「generic function を具体的タイプを指定して使うことはできない」と言うものです。
Swift は、強力な型推論する機能をもっているため、型推論できる時には 以下のように省略して書くことが必要のようです。
var intA = 3
var intB = 5
swapTwoValues(&intA, &intB) // <Int> は、Swift が推測してくれる
例えば以下のように書くと、型推論されていることがわかるエラーが表示されます。
var intA = 3
var intB = 5
var intC = 4.0
swapTwoValues(&intA, &intC)
// Error: Cannot convert value of type 'Double' to expected argument type 'Int'
エラーの意味は、「(1つ目の引数が Int であるため、)2つ目の引数も Int に変換しようとしたが、Double は、Int に変換できない」と言うものです。
Swift が文脈から 引数の型情報を取得し適用していることがわかります。
Generics を使った struct
次に、struct に Generics を適用する方法を見てみます。
struct での placeholder 指定は、struct の名称直後に記述します。先の RingBuffer を Generics を使って記述すると以下のようになります。
public struct RingBuffer<T> {
let capacity: Int
private var buffer:[T?]
private(set) public var latestIndex: Int = -1
private(set) public var oldestIndex: Int = 0
public var count: Int {
return (latestIndex - oldestIndex + 1)
}
public init(capacity: Int) {
self.capacity = capacity
self.buffer = Array(repeating: nil, count: capacity)
}
public mutating func write(_ value: T) {
latestIndex += 1
buffer[latestIndex % capacity] = value
if capacity < count {
oldestIndex += 1
}
}
subscript(index: Int) -> T? {
get {
guard (oldestIndex <= index && index <= latestIndex) else { return nil }
guard let value = buffer[index % capacity] else { return nil }
return value
}
}
}
Generics をつかった RingBuffer のテストコード
func test_write_writeWithinCapacity_shouldKeepAsIs() throws {
// (1)
var sut = RingBuffer<Int>(capacity: 4)
sut.write(0)
sut.write(1)
sut.write(2)
XCTAssertEqual(sut.count, 3)
XCTAssertEqual(sut[sut.oldestIndex], 0)
XCTAssertEqual(sut[sut.oldestIndex+1], 1)
XCTAssertEqual(sut[sut.oldestIndex+2], 2)
XCTAssertEqual(sut[sut.latestIndex], 2)
XCTAssertEqual(sut[sut.latestIndex-1], 1)
XCTAssertEqual(sut[sut.latestIndex-2], 0)
XCTAssertNil(sut[5])
}
func test_write_writeMoreThanCapacity_shouldKeepOnlyCapacity() throws {
// (1)
var sut = RingBufferInt<Int>(capacity: 4)
sut.write(0)
sut.write(1)
sut.write(2)
sut.write(3)
sut.write(4)
XCTAssertEqual(sut.count, 4)
XCTAssertEqual(sut[sut.oldestIndex ], 1)
XCTAssertEqual(sut[sut.oldestIndex+1], 2)
XCTAssertEqual(sut[sut.oldestIndex+2], 3)
XCTAssertEqual(sut[sut.oldestIndex+3], 4)
XCTAssertEqual(sut[sut.latestIndex ], 4)
XCTAssertEqual(sut[sut.latestIndex-1], 3)
XCTAssertEqual(sut[sut.latestIndex-2], 2)
XCTAssertEqual(sut[sut.latestIndex-3], 1)
}
- RingBuffer 初期化時には、capacity 指定だけで保持するタイプが推測できないため、明示的に Int を指定する必要があります。
RingBuffer 初期化部分以外は先のテストと同じです。
まとめ:Generic を使って、TDD で RingBuffer を作る
- placeholder 指定を使って、タイプを一般化できる
- placeholder 指定されたタイプは、Swift によって推測される
- よく使われる構造は、Generic を使って様々なタイプに対応させると、タイプごとにコードを書く必要がなくなる
サンプルとして作成した swapValues は 同機能の swap という関数が Swift Standard Library から提供されていますので、上記実装を自分で作成する必要はありません。
説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。
別記事で Generics の型に制限をつけて、機能追加する方法を説明しています。
[Swift] Generics の型に制約をつけて拡張する
Sponsor Link