(2014.9.3に追記) 本投稿に書かれているのはbeta 2までの古いSwiftについての情報ですのでご注意下さい 。beta 3以降では、Arrayはletのときに要素が変更できなくなり、すばらしく生まれかわりました。
SwiftのArrayとDictionaryはそれぞれ可変長配列と連想配列を表す基本的なコレクション型です。それらのインスタンスを定数に格納した場合について、その仕様に大きな違いがあります[*1]。それは、↓のように、定数のArrayインスタンスの要素は変更が可能ですが、Dictionaryインスタンスでは変更することができないというものです。
let array = [1, 2, 3] // Arrayインスタンスを定数arrayに格納
array[0] = 999 // これはOK
let dictionary = [
"abc": 123,
"def": 456,
] // Dictionaryインスタンスを定数dictionaryに格納
dictionary["abc"] = 999 // コンパイルエラー
直観的にはわかりづらい挙動です。どうしてこのような仕様になっているのでしょうか。
SwiftのArrayとDictionaryの実装は公開されていませんが、可変長配列と連想配列の一般的な実装から考えて、その理由を考えてみたいと思います。
Swiftの構造体（struct）とlet
SwiftのArrayとDictionaryはクラスではなく構造体です。ArrayとDictionaryの挙動の違いを考えるために、まずはSwiftの構造体の仕様を見てみましょう。
Swiftの構造体のプロパティはvarまたはletで宣言します。varで宣言したプロパティは後から変更することができますが、letで宣言されたプロパティは変更することができません。しかし、たとえvarで宣言されたプロパティであっても、その構造体のインスタンス自体が定数に格納されていると変更することができません。
struct Foo {
var bar: Int = 0
let baz: Int = 0
init() {}
}
var foo1 = Foo()
foo1.bar = 888 // barはvarで宣言されているのでOK
foo1.baz = 999 // bazはletで宣言されているのでコンパイルエラー
let foo2 = Foo()
foo2.bar = 888 // foo2は定数なのでコンパイルエラー
また、Swiftの構造体にはメソッドを実装できますが、デフォルトでは構造体のメソッドはプロパティを変更することができません。構造体のメソッドがプロパティを変更する場合、メソッドの宣言にmutatingというキーワードをつける必要があります。mutatingが指定されていないメソッドの中でプロパティを変更しようとするとコンパイルエラーとなります。
では、letで宣言した定数に対してmutatingなメソッドを呼び出そうとするとどうなるでしょう？先の例の通り、定数に格納された構造体のプロパティは変更することができません。mutatingなメソッドも例外ではなく、定数に格納された構造体に対してmutatingなメソッドを呼び出そうとするとコンパイルエラーになります。
struct Foo {
var bar: Int = 0
init() {}
// barを変更するのでmutatingが必要
mutating func incrementBar() {
bar++ // barの値を変更
}
}
var foo1 = Foo()
foo1.incrementBar() // これはOK
let foo2 = Foo()
foo2.incrementBar() // コンパイルエラー
ArrayとDictionaryのSubscript
array[index] = 123のようなコードを実行すると、SwiftではSubscriptというメソッドの一種がコールされます。Subscriptにはgetterとsetterがあり、要素を取得するときはgetterが、要素を変更するときはsetterが呼ばれます。
let array = [1, 2, 3]
let value = array[0] // getterが呼ばれる
array[0] = 999 // setterが呼ばれる
- []で代入しようとするとSubscriptのsetterが呼ばれる。
- 定数に格納されたArrayインスタンスの要素は変更できる。
- 定数に格納されたDictionaryインスタンスでは変更できない。
- SwiftのArrayとDictionaryは構造体である。
- 構造体のメソッドがプロパティを変更するにはメソッドをmutatingで宣言しなければならない。
- 定数に格納された構造体のmutatingなメソッドを呼び出すとコンパイルエラー。
これらから考えると次のようなことが言えます。
- ArrayのSubscriptのsetterはmutatingでない。
- DictionaryのSubscriptのsetterはmutatingである。
では、DictionaryのSubscriptのsetterはmutating付きで宣言されているのでしょうか？実は、Swiftではsetterはデフォルトでmutatingになります。mutatingでないsetterを宣言するには、逆にnonmutatingを指定する必要があります。
以上をまとめると、ArrayとDictionaryの宣言は、次のようになっていると考えられます。
struct Array<T> {
subscript(index: Int) -> T {
get { ... }
nonmutating set { ... } // mutatingでない
}
...
}
struct Dictionary<K: Hashable, V> {
subscript(key: K) -> V? {
get { ... }
set { ... } // mutating
}
...
}
なぜ、ArrayのSubscriptのsetterはnonmutatingで良いのに、Dictionaryではmutatingでないといけないのでしょうか。言い換えると、ArrayのSubscriptのsetterはプロパティを書き換える必要がないのに、DictionaryのSubscriptのsetterはプロパティを書き換える必要があるということです。その理由は、ArrayとDictionaryの実装をイメージするとわかってきます。
Arrayの実装のイメージ
SwiftのArrayは可変長配列を表す型です。可変長配列のよくある実装は次のようなものです。
- 配列の長さ（Swiftで言うcount）よりも長めにバッファを確保する。
- 配列の長さとバッファの長さが異なるので、配列の長さを別途記憶しておく。
- 末尾に要素を追加するときは、バッファに空きがあれば配列の末尾に相当する位置に値を代入して配列の長さを1増やすだけですむ。
- バッファに空きがなければ、より長いバッファを新たに確保しすべての要素をそこにコピーする。
このような実装であれば要素を追加するたびにバッファを確保しなおす必要がありません[*2]。また、バッファを確保するときに長さを倍々に増やしていけば、N個の要素を追加する際に発生するコピーの回数は高々2N回ですみます。
そのような一般的な動的配列の実装を踏まえた上で、Arrayの実装をイメージしてみましょう。
まず、Arrayの要素を格納するためのバッファと実際の配列の長さ（バッファの長さとは異なる）を保持しなければなりません。すると、次のようにプロパティを持っていると考えられます。なお、説明を簡単にするために固定長のバッファを表すBufferクラスがあるものとします。
struct Array<T> {
var buffer: Buffer<T>
var count: Int
...
}
肝心のSubscriptはどうなるでしょうか？ArrayのSubscriptは簡単で、ただ透過的にbufferの要素を返せばOKです[*3]。
subscript(index: Int) -> T {
get {
return buffer[index]!
}
nonmutating set {
buffer[index] = newValue
}
}
setterはArrayのプロパティを一切変更しないので、nonmutatingで良いことに注意して下さい。
本題とは関係ないですが、appendメソッドの実装は次のようになります。
mutating func append(newElement: T) {
if (count == buffer.count) { // バッファに空きがない場合
let oldBuffer = buffer
buffer = Buffer(max(buffer.count * 2, 1)) // 2倍の長さのバッファを確保
for index in 0..count {
buffer[index] = oldBuffer[index] // 古いバッファから要素をコピー
}
}
buffer[count++] = newElement // 末尾に要素を追加してcountを1増やす
}
Dictionaryの実装のイメージ
連想配列にN個のエントリー（キーと値のペア）が格納されているとき、あるキーを指定して値を取得するにはどうすれば良いでしょうか？最も単純な実装はエントリーを一つずつ取り出してキーを比較し、マッチすればそのエントリーの値を返すという方法です。しかし、そのような方法ではN個のエントリーに対して平均N/2回の比較が必要となり、Nが増えるとその分だけ探索にかかる時間も増えてしまいます。そのため、大抵の言語では、より効率的なデータ構造とアルゴリズムを使って連想配列を実装しています。
連想配列の実装はいくつか考えられますが[*4]、The Swift Programming LanguageにDictionaryのKeyTypeはHashableだと書かれていることから、SwiftのDictionaryはハッシュテーブルで実装されていると考えられます。
ハッシュテーブルは、キーを一つずつ比較して探索する代わりに次のような方法で探索を行います。
- ハッシュテーブルと呼ばれる配列を用意する（ハッシュテーブルの行はバケットと呼ばれる）。
- エントリーを登録するときはキーのハッシュ値をインデックスとしてハッシュテーブルのバケットにアクセスし、得られたバケットに格納する。
- ただしハッシュ値は衝突する可能性があるので、一つのバケットには複数のエントリーを格納する必要がある。
- キーで値を取得するときには、キーにハッシュ値をインデックスとしてバケットを取得し、そこに格納されているエントリーの中からキーが一致するものの値を返す。
このような方法であれば、登録されたエントリーの数に関わらず一定の時間でキーから値を取得することができます。ハッシュテーブルの問題点は、バケット数に対して格納されるエントリーが多すぎると著しくパフォーマンスが低下することです。
たとえば、バケット数が100のハッシュテーブルに100万個のエントリーを登録すると、一つのバケットあたり平均1万個のエントリーが格納されることになります。そうすると、キーから値を取得するには、バケットの中の1万個のエントリーに対して一つずつキーが一致するか確認しなければなりません。ハッシュ値を使って高速にバケットにアクセスできても、バケットの中を平均5000回の比較をして探索しなければならないのでは意味がありません。ハッシュテーブルのパフォーマンスを最大限発揮するためには、エントリー数に対して十分に大きいバケット数のテーブルを確保し、一つのバケットに格納されるエントリーの数が平均して1個以下にする必要があります。
しかし、あらかじめ登録されるエントリーの数がわかっていればいいですが、そうでない場合は事前に適切なバケット数のテーブルを用意するのは困難です。そこで可変長配列と同じような戦略をとります。
- 最初はわずかなバケット数のテーブルを用意する。
- エントリーが登録され、バケット数に占めるエントリー数の割合が一定以上になったらテーブルを作りなおしてバケット数を拡張する。
- 新しいテーブルに古いテーブルのすべてのエントリーを登録しなおす。
バケット数を倍々に拡張していけば、N個のエントリーを登録するのに必要なコピーの回数は高々2N回です。
それでは、Dictionaryの実装をイメージしてみましょう。
Dictionaryはハッシュテーブルのバケットを表すバッファと格納されているエントリーの数を保持しなければなりません。そのため、次のようにプロパティを持っていると考えられます。なお、説明を簡単にするためにArrayのクラス版であるListクラスがあるとします[*5]。
struct Dictionary<K: Hashable, V> {
var buckets: Buffer<List<(K, V)>>
var count: Int
...
}
Arrayと比べると、キーのハッシュ値を使ってバケットを取得しなければならないDictionaryのSubscriptはややこしいです。まずはgetterだけ見てみましょう。
subscript(key: K) -> V? {
get {
// ハッシュ値を使ってバケットを取得する
let bucket = buckets[key.hashValue % buckets.count]
if let entries = bucket {
// バケットの中のエントリーを一つずつ取り出しキーを比較
for entry in entries {
// キーが一致するエントリーがあれば値を返す
if key == entry.0 {
return entry.1
}
}
}
// キーが一致するエントリーがなければnilを返す
return nil
}
...
}
次は本題のsetterです。↑で書いたように、DictionaryのSubscriptのsetterには、ハッシュテーブルのバケットがエントリーでいっぱいになったら（バケット数に占めるエントリー数の割合が一定以上になったら）ハッシュテーブルを作りなおしてバケット数を拡張する必要があります。このときに、新しく作成したハッシュテーブルのバケットをbucketsプロパティに代入しなければなりません。この操作が、DictionaryのSubscriptのsetterがmutatingでなければならない理由です。
簡単に言えば、array[index] = elementとしても新しい要素が追加されることはないけれども、dictionary[key] = valueとした場合にはエントリーが追加される場合がある（そうするとバッファを作りなおさなければならない可能性がある）ことによって、ArrayとDictionaryの挙動の違いが生じていると言えると思います。
少し長いですが、setterのコードは次のようになります。
subscript(key: K) -> V? {
...
set {
// ハッシュテーブルがいっぱいの場合は再確保してバケット数を拡張
if (count >= buckets.count * 3 / 4) {
let oldBuckets = buckets
// 倍のバケット数でテーブルを再確保（このためにmutatingでなければならない）
buckets = Buffer<List<(K, V)>>(buckets.count * 2 + 1)
// 古いテーブルのエントリーを新しいテーブルにコピー
for bucketIndex in 0..oldBuckets.count {
let bucket = oldBuckets[bucketIndex]
if let entries = bucket {
for entry in entries {
self[entry.0] = entry.1
}
}
}
}
// キーで探索してエントリーを格納
let bucketIndex = key.hashValue % buckets.count
let bucket = buckets[bucketIndex]
if let entries = bucket {
for (index, entry) in enumerate(entries) {
if key == entry.0 {
// キーが一致すればエントリーを書き換える
if let nonNilNewValue = newValue {
entries[index] = (key, nonNilNewValue)
return
} else {
// newValueがnilならエントリーを削除
entries.removeAtIndex(index)
count--
return
}
}
}
// キーが一致しなければ新しくエントリーを追加
if let nonNilNewValue = newValue {
entries.append((key, nonNilNewValue))
count++
}
} else {
// バケットが空の場合はリストを生成してエントリーを追加
if let nonNilNewValue = newValue {
buckets[bucketIndex] = List<(K, V)>((key, nonNilNewValue))
count++
}
}
}
}
ArrayとDictionaryの仕様について思うこと
SwiftのArrayとDictionaryの仕様は、実装の都合の影響を大きく受けているように思います。仕様が実装の都合で歪められるのは望ましくないですし、可変長配列と連想配列というプログラム中で多用されるコレクション型が直観に反する仕様になっているデメリットは大きいと思います。
本エントリーで書いたこともSwiftのArrayがヤバイで書いたこともArrayやDictionaryがクラスであれば生じない問題なので、構造体ではなくクラスであれば良かったのにと思います。
ArrayとDictionaryの実装イメージのコード
↑ではコードの一部を抜粋しましたが、完全なコードはこちらをご覧下さい。名前の衝突を避けるために、Array2、Dictionary2としています。また、BufferクラスはArrayを使ってエミュレートしています。ListクラスについてはSwiftのArrayがヤバイの中で紹介したもので、こちらに実装があります。
余談ですが、今回Array2とDictionary2を実装してみて、Swiftはなかなか良いと感じました。特に型推論がいい感じですね。その分、余計にArrayとDictionaryが残念です・・・。
まとめ
- 定数に格納されたArrayインスタンスの要素は変更が可能だが、Dictionaryインスタンスでは変更することができない。
- SwiftのArrayとDictionaryは構造体である。
- 構造体のメソッドがプロパティを変更するにはメソッドをmutatingで宣言しなければならない。
- 定数に格納された構造体のmutatingなメソッドを呼び出すとコンパイルエラー。
- []で代入しようとするとSubscriptのsetterが呼ばれる。
- Subscriptのsetterはデフォルトでmutatingなので、mutatingでなくすためにはnonmutatingを指定しなければならない。
- 以上から、ArrayのSubscriptのsetterはnonmutatingだが、Dictionaryではmutatingだと考えられる。
- 可変長配列の一般的な実装を考えると、ArrayのSubscriptのsetterはプロパティを変更する必要はない。
- 連想配列の一般的な実装を考えると、DictionaryのSubscriptのsetterはプロパティを変更する必要がある。
- このようなArrayとDictionaryの違いは、ArrayのSubscriptのsetterで要素が追加されないのに対して、DictionaryのSubscriptのsetterではエントリーが追加されることによる。
補足（2014.6.25に追加）
Array2とDictionary2の実装には、本物のArrayやDictionaryと大きく仕様が異なっている点があります。それは、SwiftのArrayがヤバイで取り上げた↓が再現できないことです。
var a = [11, 22, 33]
var b = a
a[0] = 777 // b[0]も777になる
a.append(44)
a[0] = 888 // b[0]は888にならない
なぜなら、Array2ではバッファを倍々に拡張するので、バッファの再構築＆コピーがバッファがあふれたときにしか起こりません。Array2のバッファサイズは必ず2のN乗になるように確保されるので、要素数が3から4に増えるときには再構築＆コピーが起こらないのです。要素数が2から3へ増えるときや、4から5に増えるときには↑のような現象を再現できます。
では、実際のArrayはどのような実装になっているのでしょう？appendが呼ばれる度にバッファの再構築＆コピーが実行されるのでしょうか。それだと、一つの要素を追加するための計算量がO(N)、N個の要素を追加するにはO(N^2)になってしまい実用的ではありません。とはいえ、Array2のような実装だとカプセル化して隠蔽された内部状態によってappendしたときの挙動が変わることになりわかりにくすぎます。
僕の推測では、おそらくバッファへの参照カウントが2以上のときのみ再構築＆コピーをしているのではないかと思います。そうすれば大方のケースでは要素の追加をO(1)ですませることができますし、appendしたときに実体が変化したりしなかったりという妙な挙動にもなりません。
バッファを変更しうるその他のメソッド（insertやremoveLastなど）も同様だと思います。Dictionaryも同じでしょう。特に、DictionaryはArrayと違いsubscriptのsetterもCopy-on-writeになるので、内部では参照を持っているけれどもまるでメンバに参照など持たない純粋な値型のように振る舞えます。
ただ、やはり何のメリットがあってそこまでして参照を隠して値型に見せかける必要があったのか疑問です。僕が思い付く限りでは、構造体であることのメリットはデリファレンスが必要なく若干パフォーマンスが良いことくらいに思います。しかし、Arrayのsubscriptはともかく、他のメソッドやDictionaryはデリファレンス以外のオーバーヘッドの方がずっと大きそうです。Arrayについても標準の可変長配列はクラスにして、別途subscriptが高速な固定長の配列型を提供すればよかったのではないかと思います（固定長であればappend等によるバッファ再構築によって実体が変わってしまう問題に悩まされることもありません）。
[*1] 個人的には値型の値のことをインスタンスと呼ぶのは違和感がありますが、The Swift Programming Languageにならってここではそう呼ぶことにします。
[*2] この実装では、配列の末尾への追加・削除は高速（O(1)）ですが、先頭への追加・削除は遅い（O(N)）です。バッファが循環していると考えた実装だと先頭への追加・削除もO(1)で行えます。
[*3] 本当はindexが範囲外だった場合のエラー処理が必要ですが、ここでは本筋の話がわかりづらくなるだけなので省略します。
[*4] ぱっと思い付くのはハッシュテーブル、二分探索木や赤黒木・B木などのツリー、Skip Listなどです。
[*5] ここでArrayではなくListを使うのは値型では実装上問題があるからです。