第81回

今回も引き続き、標準ライブラリーで定義されている Collection について眺めていきます。前回に Collection の基本な概念について見ていったので、今回はさらにそこから特定の特徴を際立たせた感じの BidirectionalCollection と RandomAccessCollection の基本概念について確認していってみますね。どうぞよろしくお願いします。

—————————————————————————————————— 熊谷さんのやさしい Swift 勉強会 #81

00:00 開始 00:27 コレクションについて見ていく中で感じること 02:22 Collection の特徴をおさらい 02:51 非破壊 04:06 コンパイラーで適合を検出できない制約 04:36 インデックスによるマルチパスアクセス 05:35 past the end 06:08 スライスの話は今回は省略 06:23 コレクションは範囲が有限 09:29 BidirectionalCorrection 10:16 BidirectionalCollection の特徴 10:49 後方探索 13:15 計算量 14:41 インデックスの前方後方移動について 16:46 シーケンス性を考慮したコレクション 20:19 プロトコルを独自定義する上での考え方 21:33 Equatable と Hashable の関係 25:40 ハッシュでは一致性までは判らないからこそ準拠している？ 28:05 前方検索までは規定しないプロトコルは存在し得る？ 31:02 どこで順次アクセスを可能とするか 32:32 プロトコル定義の匙加減 33:37 Codable に窺える特徴 37:03 Identifiable 38:59 ハッシュテーブルと衝突の管理 44:21 複数のプロトコルに準拠させる方式について 46:47 考え方の転換も必要かもしれない 47:52 後方からの効率的なアクセス 48:33 BidirectionalCollection への準拠 48:53 前方移動と後方移動は同じ量ずつ 49:32 次回の展望 ——————————————————————————————————

Transcription & Summarize : 熊谷さんのやさしい Swift 勉強会 #81

では、改めて始めていこうかと思います。今日はコレクションの話です。ランゲージガイドを見ているんでしたっけね。ちょっとコレクションの話が面白いということで、脱線している回になりますけれども、コレクションって結構簡単で基礎的なもので、なんとなく普通に使っていると思いますが、調べてみるとそれなりに有意義だなと感じながら話していますが、どうなんですかね。みんなとしては少なくとも自分は、ここまで細かくルールが決まっているんだと感じながら話しています。

何気なく使えるとはいえ、知っておくと今後のコードを書く上での自分の動きが変わってきそうです。いろんな発見があって面白いなと感じながら話をしたり、スライドを用意したりしています。

前回お話ししましたが、このコレクションという考え方は Swift 標準ライブラリーのあらゆるところに顔を出すプロトコルなので、それを知っておくと Swift 標準ライブラリー全体を知ることにも繋がっていきそうなテーマです。そんな感じで見ていますが、前回コレクションの話は終わって、コレクションプロトコルの話が終わり、バイディレクショナルコレクションに移っていきます。

ちょっとだけざっくりとコレクションをおさらいしてみますかね。というのも、この先の資料を準備していたときに、知り始めたからなのか、混乱するところが少し出てきたので、自分の情報整理という意味合いでも、ざっくりと復習したいと思います。

コレクションプロトコルとしては、大事なところは要素を非破壊で複数回巡回できる、要は何回でもアクセスできるということが約束されたプロトコルです。コレクションプロトコルはシーケンスプロトコルから継承していますが、シーケンスとコレクションの大きな違いは、シーケンスは非破壊ということが保証されていないということです。

したがって、シーケンスを実装するときには、中を破壊しながらトラバーサルしていってもいい、そういった作り方も許されます。しかし、コレクションになると、中身を破壊しながらトラバーサルすることはやってはいけない、というのがコレクションプロトコルで規定されています。あくまでもコメントレベルの話ですが、コンパイラーは検出できませんが、コメントには非破壊でなければならないと書かれていますので、破壊する実装はNGです。

とりあえず、大事なところは非破壊というところです。この非破壊が担保されることによって、コレクションはインデックスアクセスが可能になる、ここが重要です。非破壊だからインデックスアクセスによるマルチパスアクセスが可能になるということがコレクションのおさらいとして重要なポイントです。

エンドインデックスはどの要素にも対応しない、いわゆるpast the endを表現しています。スタートインデックスからエンドインデックスを含まない手前までということで、手前1個前ではないですが、手前までという考え方になっています。

あとはスライスについては前回や前々回に丁寧に話したのでここでは省略しますが、コレクションはインデックス範囲が有限だという規定があります。コメントレベルで必ず終わるということが約束されています。実際に無限に続くコレクションを作成した場合、プロトコルの規定に反することになるので、それはコレクションとは言えません。

計算量も大事な要素の一つです。計算量についても振り返っておきましょう。 コレクションプロトコルに準拠する場合は、スタートインデックスとエンドインデックス、ストレージアクセスについて計算量オーダー1でアクセスできることが期待されます。ここが重要なポイントです。あくまでも期待するものの、必ずしもオーダー1である必要はありません。これはコレクションプロトコルの特徴であり、その性能を保証できない場合には文書に必ず記載する必要があります。例えば、スタートインデックスのオーダーがオーダーnである場合など、独自に定義した際にはオーダーが1でなければ記載する必要があります。

いずれにせよ、計算量についてはコレクションプロトコルでは期待まではするけれど、求めてはいません。求めるという言葉の重みは取り方次第ですが、前のスライドにも特に記載されていません。これで大体のコレクションプロトコルが理解できたかと思いますので、次にバイディレクショナルコレクションに移ります。

バイディレクショナルコレクションプロトコルの特徴について振り返ってみましょう。このスライドに記載している内容は、標準ライブラリのコメントを元にしています。オリジナルの内容ではなく、Swiftの標準ライブラリが主張するバイディレクショナルコレクションの公式な説明です。

まず、バイディレクショナルコレクションはコレクションプロトコルを継承しています。そのため、これまで話したコレクションプロトコルの性質をそのまま引き継ぎ、さらに表示されている特性が追加されます。そして、バイディレクショナルコレクションは後方探索もサポートします。シンプルなコレクションプロトコルは前方検索のみをサポートしていました。昔のSwift2くらいの頃はフォワードインデックスしかサポートしていませんでした。バイディレクショナルコレクションは後方からの探索もサポートし、さらにindex(before:)というメソッドの実装が求められます。これによって前方と後方の両方からの探索が可能になります。

ちなみに、後方からも探索できるのは、そのコレクションが有限だからです。シーケンスの場合は有限とは限りませんので、後方からの探索を提供することはできませんが、なぜかdropLastのようなメソッドがシーケンスに用意されているため、不思議なところもあります。それでも、コレクションは有限であるため後方からたどることも実現が容易です。さらに、有限であることから効率的に後ろからアクセスすることも可能です。

あくまでインデックスアクセスはオーダー1を期待するものの、これは約束されているわけではありません。バイディレクショナルコレクションにおいてもインデックスアクセスが効率的であることが期待されていますが、それが保証されているわけではない点に注意が必要です。 とりあえず、約束されていないみたいなんですよね。読んでいる限りでは、先頭からでも後方からでも、中間からでも効率よくアクセスできるというのが実現できるポテンシャルを持っているだけ、という状況ですかね。

少なくとも、バイディレクショナルコレクションはそうです。普通のコレクションもそうなのか。ここまで話してきて、自分は混乱してきたんですけれど、普通のコレクションも有限範囲が決まっていて、最後の要素を取得できますよね。インデックスアクセスが可能で、どこでもインデックスさえ指定すれば取得できる。当たり前のことなのですが、バイディレクショナルコレクションも同じではないですか？

ここで、普通のコレクションはindex(after:)だけしか備えませんが、後方探索もサポートするこのコレクションで分ける必要があるのですかね。インデックスという有効範囲があって、その中でどうか。

バイディレクショナルコレクションも別にStrideableであるべきとか決まっていないんですが、要するに、インデックスアクセスは自由ですが、そのインデックスが指す次の要素を検索できるとは限らない。しかし通常のコレクションはできる。バイディレクショナルコレクションの特徴は戻ることができることです。

そうか、インデックスアクセスと連携についてですが、混乱してきました。分からないまましゃべっているので、みんなに伝わっていない気がしますが、例えばArrayとか使うとインデックスはInt型で、要するにランダムアクセスコレクションでもあります。要は文字列などでなくてもこれでインデックスを指定して要素を取り出せるという構造です。

構造体を作って、何かしらのインデックス型があったとして、それでサブスクリプトを使ってインデックス指定で要素を取得することができれば良いのですが、このインデックスが次に進めなくても良いのか、その点ではないかもしれないと感じます。

とりあえず、コレクションがシーケンスに準拠していない限り、index(after:)を持つ必要はないのですが、シーケンスに準拠しているので、インデックスを次に進める必要が出てきます。インデックスがなければ、次のポジションを取れないからです。

この点について整理すると、コレクションの規定の中には、インデックスの標準的な扱いがあり、それでループが回ってイテレーションできるようにするために、index(after:)が必要なのです。そのため、あるインデックスの次のインデックスを取れるようにしておかないといけない。

このあたりの設計には注意が必要です。プロトコルを設計する上で、こういった点が難しいかもしれません。それを考えると昔存在したフォワードインデックスプロトコルなどと同じ話になるかもしれません。

今回は、毎回のように思い出しているトピックですが、この勉強会でも何度か紹介しましたが、EquatableとHashableについても少し触れましょう。元々、Hashableは値の一致性自体は保証しないはずですが、SwiftのHashableはEquatableから準拠している点が面白いところなんですよね。 「理屈で考えると、ハッシュ値が一緒だからといって同じ値とは限らないんです。例えば、Int型ではハッシュ値の衝突は起こらないように設計されていますけど、アルゴリズムによっては衝突が発生する可能性もあります。しかし、普通は衝突しないと考えていいでしょう。ハッシュバリューが同じであっても同値とは限らないということですね。

実際には多くのケースでデフォルトの実装がしっかりしているはずです。例えば、Int型についての例では、デフォルト実装がある程度信頼できるものとなっていると思います。試しに具体的な検証を行うとしたら、Int型のHashableプロトコルに注目する必要があります。

また、Hashableプロトコルについては、同値性の判定までカバーしているわけではありません。ただし、Equatableに準拠している場合、一致判定のインターフェースも備えています。そして、Appleのドキュメントによれば、Hashableは一致性までは備えないものの、効率的な実装が求められるためにEquatableに準拠しているということが述べられています。

さらに理解を深めると、ハッシュ値を基にプロトコルを組みたてると、必ずしもEquatableに準拠するわけではなくなります。しかし、プログラミングの観点から見ると、HashableはEquatableに準拠している方が実際的です。具体的に言うと、HashableがEquatableに準拠していないと、値が一致しているかどうかの判定が難しくなり、ハッシュ値だけで値の一致を判断できない場面が出てくるでしょう。

実際にHashableがEquatableに準拠していることで、値が一致しているかどうかをしっかりと判断するための確かな情報が得られるのです。このように考えると、HashableがEquatableに準拠しているのは自然な設計だと言えます。

一方で、コレクションについても考え方が変わってきました。例えば、本来コレクションはインデックスアクセスが可能であることを規定すべきですが、そうしなかったのは、それがあまり価値がないと考えたからかもしれません。ただし、設計上はプロトコルとしてコレクションを持ち、インデックスアクセスを規定することも可能です。具体的には、サブスクリプトとしてポジションインデックスを規定し、エレメントを返すような形です。そのとき、アソシエイティブタイプもエレメントとして定義します。その上で、必ずスタートインデックスとエンドインデックスを規定しなければなりません。」 まずは、コレクションプロトコルとしての要求はこれだけという価値観もありですよね。本来、サブスクリプトも get が必要です。それで、プロトコルとしてフォワードインデックス、インデックスじゃないですよね、フォワードコレクションとしてコレクションに準拠させて、ここでファンクションとして index(after:) でインデックスを返すという、こういうメソッドを要求します。そしてさらに、プロトコルとして BidirectionalCollection、これがフォワードコレクション。このような設計もありましたよね。

安直に設計していくと、こういう設計にしたくなるような気がします。ただ、結局のところ考え方の違いだと思いますが、コレクションだとインデックスアクセスが可能になります。しかし、今表示中の独自定義のコレクションだとインデックスアクセス可能までしか表現されていないため、インデックスを次に進めることができません。シーケンスに準拠させる場合には少し支障が出てきます。それを解決するためには makeIterator を実装してあげる必要があります。

これ自体は難しくないですが、実装が求められるものです。でもこれでいいと思います。それで、フォワードコレクションの中で makeIterator を規定の実装として何かしらのイテレーターを返してあげればいい。このような作り方もありですよね。

面白いのは実際の実装を見ると、いわゆるこの12行目のフォワードコレクションから、ここからの価値観で作っているということですね。だから、これをまとめるとこんな感じです。こういうふうな作りになっているのが面白いですね。このさじ加減はどうやったら身についていくのでしょうか。どっちがいいかは分かりませんが、今自分が書いた独自コレクションか、標準ライブラリーのコレクションかね、どちらも難しいです。

もう1つ思い出したのですが、コーダブルも面白い定義の仕方をされています。Encodable と Decodable のプロトコルの両方を組み合わせたものが Codable です。この発想は異なりますね。プロトコル継承するパターンですが、これは独立して存在してほしいのでこれしかないと思います。全部を疎結合にしているわけではなく、いい感じにプロトコル継承して振る舞いを最小限にとどめている点が面白いと思いますね。

ハッシャブルも似たような感じで、例えば Hashable を厳密に比較性までは求めないとし、Equatable と Hashable をまとめるという価値観もあります。これをしない理由はわからないですが、ハッシュの計算が Equatable と密結合したほうが都合がいいのかもしれません。ハッシュテーブルを規定する際に、キーが Equatable かつ Hashable であれば、何の不足もなくできるし、そのほうが適しているように思えます。

このような考え方もありますので、どちらが良いかは一概には言えませんが、プロトコルの設計は難しいですね。 そうですよね。パッと見た感じ、いつも思い出せないのが「合成」じゃなくて「シンセサイズ」のコンフォーマンスです。あれを考えると、Hashableは便利ですが、型の扱いは結構難しいですよね。この&でEquatableとかHashableみたいなのが合成に影響しますかね。なんか特殊ですよね。パフォーマンスにも影響するし、Hashableだけで一意性が担保できないから、内部的にEquatableを使わなきゃいけないのかな、とかなんですかね。考え方としてはそうだと思います。ただ、一意性がいらないHashableのときもありますよね。あんまりないとは思いますけど、近いのはIdentifiable IDとして使う場合です。

あれとかは、この3つ（Hashable、Identifiable、Equatable）とHashとIDの関係ってどういう感じなんでしょうか。HashってあくまでもIDとして使わない方が良いみたいなイメージがあります。だから別途Identifiableというプロトコルが追加されたのかなと思って。ちょっとUIの話かと思ったのですが、標準にあるんですね。なるほど、Swift 5.1から追加されたみたいですね。これが本当のIDですね。シェルのIDとか、Hashとは違う観点での一意性です。そうですね、Hashはあくまでも一意性のものではないので、これは別々で、そこまで関連するものではないと思います。

話に出してくることはあまりないですが、直行していて次元が違う感じです。ちょっと話がさらに広がりますが、Hashableの一意性について、以前案件のメンバーと話していたのですが、セットの一意性判定にHashableとEquatableが両方使われるんですよ。あれのハッシュテーブルのメモリ空間はうまく設計されていて、配列数がセットに配列を入れて初期化することがよくありますよね。そのときのハッシュテーブルのサイズは配列のサイズに依存する実装になっています。なので、配列が3個の場合と100個または1万個の場合で、ハッシュの衝突率が変わるんです。

セットのハッシュテーブルでは、配列が例えば3個の場合にどれくらい取るのが適切なのかを判定しています。3個だと小さいですが、意外と衝突するんですよ。ハッシュ値で衝突した場合はEquatableが使われる感じになっているので、小さい配列を元にセットを作成した場合には、衝突することが多いですが、メモリ消費量は少ないです。ただ、Equatableで同値判定をすることになっても、配列自体が小さいのでキャパシティも小さいため、問題にはならないでしょう。逆に大きい配列の場合はハッシュテーブルが大きくなるので、ハッシュ値の衝突はあまり起こりません。

そう考えると、HashableがEquatableにプロトコル継承しなくてもいいのかなと思ってしまいます。要は、セット側がハッシュ衝突したときの振る舞いを持っているので、Hashableが必ずしもEquatableである必要はないということですね。ハッシュ衝突したときにどう振る舞うかはセットやその設定次第です。

ただし、セットが持っている値がハッシュが衝突したときにどの値なのかを判定するためには、必ず同値判定が必要です。例えば、containsメソッドが良い例ですね。このとき、ある値を渡して持っているかどうかを見るためには、その値のハッシュ値が求められ、そのハッシュ値が複数ある場合、最終的にどちらの値が正しいかを判定するためにEquatableが必要になります。たとえば、Int型の場合は直感的ですが、独自のインスタンスの場合、Hashableだけでは同値判定が分からないので、Equatableで教えてあげる必要があります。ですので、セット自身が扱う値に対してEquatableが求められ、その際にHashableにEquatableが含まれているとシンプルですね。 そうなんですよね、そこを Equatable と Hashable に分離していた場合ですね、適切な情報を求められているなって分かるんですけど、ちょっと面倒くさい部分もありつつ、プロトコルの吸収をしなきゃいけない理由っていうのを、自明性以外で納得できるようなものがないなっていう。でも、& って別にそんなにね、追加で1個書くだけでしょ。書いたことがないので、なんでこのバランスでこの設計にしたんだろうって、便利だけどそうしたらさっきのシーケンスとかそこら辺もぐちゃぐちゃになっちゃうんですよ。それが 4W 的なノリでできたんじゃないかなって、できなくはないですよね。そうですよね、こんな感じでね。

コレクションは何かしらのシチュエーションを取れる感が出てくる。そうですね、名称的にはハッシュもそのノリなんですかね。Equatable できそうなイメージ。そういうノリな感じがしますね。シーケンスがないコレクションはありえないよねと、ハッシュだけど同時に等価判定ができないのはないよねっていう、そういう価値観ね。ただ、独自定義でさっき見せたコレクションみたいにインデックスアクセスだけ保証して、先頭から順に取れるっていうことまでは保証しないっていう発想もありといえばありなんで、やっぱこの匙加減ですよね。そこまで分解すると使いづらい、数が少ないほうがいいですよね。そうですよね、どうせならね。

Swift の場合は順次アクセスできない範囲はレンジで表現してて、レンジはアッパーバウンドとロアーバウンドじゃないかな、確か。そうですね、アッパーバウンドとロアーバウンドがあって、これは範囲が有限とは語ってないですけど、とりあえずね、頭と尻尾があって、その間は順次たどれるとは限らない。これがさっき自分が独自で定義してみたコレクションと似た発想。インデックスアクセスまではちょっと保証してないですけどね。

こうやって考えていくとプロトコルを設計するっていうのも、結構難しいことを求められてますよね。オブジェクト指向みたいに、ついつい偶像的にあるものにフォーカスを当てて、それに純粋に設計を重ねていくとか、それとはちょっと違う感じですよね。Hashable に注目はするんだけど、その概念に Equatable を含ませるか、コレクションに順番にイテレーションの性格まで含ませるかどうか、なんか難しいですね。でもあんまりね、思い返してみると難しいってそんなに感じることも少ないしなーとかちょっと思ったりします。

とりあえず話を戻していこうかな。BidirectionalCollection は、後方からの順次アクセスが可能っていう制約が乗ったことによって、逆順にしたコレクションを取るよみたいな reverse がサポートされたり、最終要素に効率よくアクセスできる last とかも提供できたりっていう性格があるんです。それと、suffix とかも、効率よく後ろから何個目を取るみたいなことができるようになるっていう性格が BidirectionalCollection には規定されていて、それに準拠させるためにはコレクションが求めているプロトコルプラス index(before:) を追加してあげれば BidirectionalCollection になるよっていうプロトコルになっているんです。

あと、インデックスアクセスの前方移動と後方移動は必ず同じ量だけ移動するようにしてくださいねってコメントに書いてありました。要は index(before:) を取ったインデックスを index(after:) で再度進めてあげると元のところに戻ってくるよっていう。同じ距離感で移動しなさいっていうのが書いてあって、これ面白いなぁと思いました。あんまり考えたことなかったですけど、行きは1個ずつ帰りは2個ずつとかね、そういったことは BidirectionalCollection ではダメですよっていう感じです。

じゃあ、まぁこんなところですね。時間的にもちょうどいいので今日はこれぐらいにして、次回また引き続き RandomAccessCollection の方を見ていこうかなと思います。今日はこれで終わりにしますね。お疲れ様でした。ありがとうございました。