第82回

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

ここまででいったん標準ライブラリーのコレクションの確認は終わりにしておこうと思うのですけれど、ほかにも見ていけそうなところは色々あるので、余った時間でそんなあたりも思い浮かぶままに眺めてみようと思ってます。どうぞよろしくお願いします。

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

00:00 開始 00:44 これまでのおさらい 02:01 RandomAccessCollection 02:29 ランダムアクセス 04:01 シーケンシャルアクセス 04:43 ディスクアクセス 08:14 メモリーアクセス 11:19 シーケンシャルアクセスとランダムアクセス 11:37 Swift でいうランダムアクセス 12:11 Collection はシーケンシャルアクセスが基本 12:53 BidirectionalCollection もシーケンシャルアクセスが基本 13:19 RandomAccessCollection はランダムアクセスを想定 13:56 ランダムアクセスの計算量 15:25 性能を意識したコレクションの選定 16:21 ジェネリクスでは汎用的なプロトコルを想定する 19:10 Collection への準拠を想定した場合 21:20 性能を意識したジェネリクス 28:18 RandomAccessCollection を想定していく 29:30 RandomAccessCollection に準拠させるための要件 32:48 Index に対する Strideable の必要性は？ 35:51 独自の型をコレクションに準拠させるとき 40:41 イテレーター 42:31 クロージングと次回の展望 —————————————————————————————————————————————

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

はい、じゃあ始めていきますね。今日はコレクションについてです。これまでずっとコレクションを見てきましたが、今日扱うのはそのうちの三つ目、ランダムアクセスコレクションです。シンプルなコレクションというプロトコルがあって、それを継承したバイディレクショナルコレクション、さらにそれを継承した感じになっているのがランダムアクセスコレクションです。今日はこれについて見ていこうと思います。

今日初めて勉強会に参加する方もいるかもしれないので補足すると、この勉強会では普段「The Swift Programming Language」というApple公式の本を順々に見ていく感じになっています。しかし、途中でちょっとした好奇心からコレクションを改めて見ていくと面白そうだなという状況になったので、一旦その本からは外れて、Swiftの標準ライブラリから読み取れるコレクション周りについて見ていく回になっています。

では、ランダムアクセスコレクションについて見ていこうと思います。ランダムアクセスコレクションはバイディレクショナルコレクションの特徴に加えて、さらにランダムアクセスによる効率的なインデックス探索をサポートするコレクションです。基本的には、この特徴を抑えればランダムアクセスコレクションはOKです。

ランダムアクセスという言葉を聞けば、大体の人はある程度理解しているかもしれません。ランダムアクセスとは、ある記憶領域の中のある地点を自由に指定して直接参照できるものです。これだけではすごく当たり前のことを言っているように感じるかもしれませんので、もう少し具体的なイメージを膨らませてみましょう。

ランダムアクセスの対義語としては「シーケンシャルアクセス」があります。シーケンシャルアクセスとランダムアクセスを比較するとわかりやすくなると思います。私にとっては懐かしい考え方ですが、これらはディスクアクセスの概念に関連しています。具体的には補助記憶装置においてです。例えば、C言語やBASICなどでファイルをシーケンシャルアクセスモードで開くか、ランダムアクセスモードで開くかで動作が異なります。

シーケンシャルアクセスとランダムアクセスについて詳しく知っている方はいらっしゃいますか？ブロックデバイスとかシリアルデバイスの話にも関連しています。ブロックデバイスはランダムアクセスをサポートしており、これはOSやLinux、UNIX系の考え方でもよく見られます。

このように、ランダムアクセスコレクションは効率的なインデックス探索をサポートし、特定の要素に直接アクセスできる機能を持つコレクションです。これが基本的な考え方になります。 自分の中でシーケンシャルアクセスとランダムアクセスで思い出深いところというと、記憶装置がフロッピーディスクかカセットテープかというところです。カセットテープは、「記憶装置がフロッピーディスクか」で巻いていく感じになっているので、目的の位置を探すには先頭から順番に探していかないといけません。これがシーケンシャルアクセスの特徴です。特に昔のコンピューターを使っていたときには、フロッピーディスクやカセットテープを使っていました。

逆に、ランダムアクセスについてですが、フロッピーディスクのように目的のセクターを指定するとそのセクターをすぐに取得できます。しかし、具体的な特性や構造を追求すると、フロッピーディスクでも円盤が回っていて、セクターを探すのに「シークタイム」がかかるという工夫が必要です。さらに、データの保存場所を管理するためにFAT（ファイルアロケーションテーブル）が必要で、これはファイルの配置情報を先頭に持っています。実際には、このようなファイルアロケーションテーブルのおかげでランダムアクセスが実現できています。

これがメモリになると、詳しくはわかりませんが、メモリにはアドレスバスというものが存在しています。バスには大きく分けて2つの種類があります。メモリーバスとシステムバスです。PCIスロットが接続されているバスやメモリが接続されているバスがあります。さらに、最近ではメモリとシステムバスが分かれていることが多いです。外部ストレージや外部拡張用のバスも存在しています。データバスもありますね。コメントでいただいた通り、IOバスもあります。IOアクセスはまた異なるものです。

私はMSX出身で、最初はMSX1から始めました。細かくいじり始めたのはターボRからです。MSX時代にはシステムバスやメモリーバスをあまり意識しなかったように思いますが、MSXのZ80はシステムバスが8ビットで、メモリーバスが16ビットありました。IOバスについて直接聞いたことはありませんが、IOアクセスする時とメモリアクセスする時の待ち時間が異なるという特性があります。ターボRではロムアクセスとラムアクセスでまた速度が異なっていました。

話がだいぶ混沌としてきたので、ここらで切り上げたいと思います。 とりあえず、シーケンシャルアクセスとランダムアクセスについて話を戻します。シーケンシャルアクセスは先頭から順次アクセスできるのに対し、ランダムアクセスは指定した位置に直接アクセスできるという違いがあります。

Swiftのプロトコルでいうと、シーケンシャルアクセスはシーケンスに対応し、ランダムアクセスはアドレスを直接指定してアクセスできるものです。これだけを聞くと、普通のコレクションプロトコルもランダムアクセスができるように思えますが、実際にはランダムアクセスコレクションに準拠しないとランダムアクセスは提供されません。いくらコレクションでインデックスアクセスができても、基本的なコレクションプロトコルでは先頭から順次アクセスするしかありません。

今までお話ししてきた内容を思い返せば分かりやすいと思いますが、通常のコレクションではindex(after:)メソッドを使って一個一個先頭からしか要素を取得できません。つまり、Swiftでいうコレクションはインデックスアクセスが可能であってもシーケンシャルアクセスまでしか想定されていないということです。

前回お話ししたバイディレクショナルコレクションについても、先頭からだけでなく末尾からもアクセスできるとはいえ、これはあくまで末尾からのシーケンシャルアクセスです。途中のインデックスにたどり着こうとする場合は先頭または末尾から順に探していかなければならないため、その分速度が遅くなります。

一方、ランダムアクセスコレクションプロトコルでは、インデックスを直接指定すれば先頭や末尾からたどる必要なく、そのインデックスにダイレクトにアクセスできるという特性が保証されています。また、ランダムアクセスコレクションという言葉の代わりにダイレクトアクセスという言葉を使うこともあります。

画面に表示されている2行目に注目してください。「任意の距離のインデックスに移動したり、インデックス間の距離計測が計算量オーダー1で行える」というのがランダムアクセスの最大のメリットです。ランダムアクセスコレクションも同じ歌う得点を持っているので、そういった移動や距離計測がオーダー1で行えることがランダムアクセスの大きな特徴です。

Swiftのプロトコルだけでなく、他の何かしらでランダムアクセスという言葉が出てきた場合も、移動や距離計測がオーダー1で行えると思って問題ないと思います。今のところ、それに関して大きな間違いは思いつきませんので、とりあえず大丈夫な気がします。 オーダー1になる、これがとても大事なところです。今までのコレクションの話でも何度か出てきたかと思いますが、コレクションというものはインデックスアクセスに依存する機能がとても多いんです。そのインデックスアクセスがオーダー1で行えるようになるということは、全体としてのパフォーマンス向上につながります。コレクションを想定するときには、できるだけ汎用的なコレクションばかりを想定するよりは、ランダムアクセスコレクションを想定したほうが速度的な品質を保ちながら活かせるものになってくると思います。

たとえば、プロトコルを使うときにこれは自分の価値観だけなのかちょっと分からないですが、いや、たぶん一般的だと思うんですけど、例えばプロトコルでこの前話に出てきた Hashable っていうプロトコルがあります。そのプロトコルは Equatable に準拠しています。要は、これは正しいか間違っているかという話ではなく、もう少しシンプルな話です。

例えば、関数として全てがユニークかどうか、重複しないかどうかを判断するようなジェネリック関数を作ろうと思ったとき、任意のPを取り、そこで Hashable を取るという形にして、例えば次のように書きます。

func checkUniqueness<T: Hashable>(values: [T]) -> Bool {
    // 何らかの処理をして結果を返す
}

ですが、このときに Hashable というプロトコルを想定して作ってしまうと、このユニーク関数に対して渡せる配列は Hashable に準拠した配列しか渡せなくなります。しかし、もし比較要素だけで十分であれば、Equatable で作っておいたほうがより広い範囲の値を扱える配列を渡せます。Hashable に準拠していないけれど Equatable に準拠している値を扱う配列も渡せるわけです。こうすると、より汎用性が高まってユニーク判定できる機会が広がっていきます。

コレクションに関しても、何でもかんでも何かしらの関数があって、それでコレクションを想定すると、このコレクションはシーケンシャルアクセスしかできないインデックスアクセス可能なコレクションを想定してしまいます。しかし、これだと例えば次のような場面で影響を受けます。カウントを取ったときの計算量がオーダーNになってしまうといった感じです。

パフォーマンスを考慮するなら、ランダムアクセスコレクションを想定しないといけません。ランダムアクセスコレクションはインデックスアクセスがオーダー1で行えるので、パフォーマンスを保証できます。ジェネリックプログラミングをする際には、シーケンシャルアクセスとランダムアクセスの違いを意識する必要があります。

たとえば Collection の定義を見ると、ランダムアクセスコレクションの場合には計算量が早くなるような仕様があったりします。例えば、次のようなものがあります。

var count: Int { get }

この count は通常オーダーNですが、ランダムアクセスコレクションの場合はオーダー1になります。プロトコルに準拠させるには、必ずオーダー1で実装しないといけないのかどうかは、記載の解釈によりますが、目安となるべきでしょう。

基本的な考え方としては、シーケンシャルアクセスならオーダーN、ランダムアクセスならオーダー1といった形で書かれているものです。コレクションに関しても、ランダムアクセスコレクションを想定しつつ、一般的なコレクションにも対応するためにはオーバーロードを利用することが考えられます。どちらの場合も対応できるように実装しておくことが重要です。

そうすることで最適なパフォーマンスを引き出すことができるようになります。 とりあえず出てくるんですよ、どこかにね。せっかくだからちょっと大げさだけど、これはレギュラーエクスプレッションなら、この後任意の文字が続いて、その後バーカウントとかやると見つかるのかな？見つからなかったですね。ダメか、任意の文字ここまでオッケー。ここまでになるのか、カウントカウント。そっか、開業まで含まないから任意の文字とコレクションで一旦文字区切りを終えて、で任意の文字と開業とかやればマッチするのかな？ダメか。そこまで言うときかなかったか。じゃあいいや、俺開業もマッチした気がするからちゃんと書いていけばできそうな気がするけど、まあいいや。

とりあえずね、エクステンションのコレクションの中に count が既定の実装で提供されていて、同様にランダムアクセスコレクションの既定の実装に count が提供されているんですよ。で、そっちのほうではランダムアクセスを想定した高速に動く count が既定の実装で提供されているのでしょう。そういうふうに最適なものを選んでもらえるようにジェネリックプログラミングで作られてるよ、っていうね、そういった感じになってるんです。

もし今後コレクションを想定するジェネリック関数なりジェネリック型なりを作るときには、ランダムアクセスコレクションも想定したほうが安定的に使えるのか、そういったところは大事にしないといけないところだなというところですね。このあたり、ランダムアクセスコレクションを渡せばコレクションを想定してても勝手に速くなるとは限らない。どうも見ていく感じ、早々簡単に速くしてくれない印象もあったりするのでね。一部だけかもしれないけど、やっぱりこうやって両方のプロトコルを想定するっていうのは大事になってくるんだなと。

あと、Hashable と Equatable もせっかく出てきたけれど、これもね、こういった機能の使い方が大事です。じゃあ一回話を戻してみましょうか。それくらいで大体オッケーですね。3行目、3行目というか3行目ですけど、インデックスの移動や距離に依存する操作が大幅に効率化される。なのでランダムアクセスコレクションを想定するっていうことは大事だよっていうことですね。

そのランダムアクセスコレクションに準拠させるためには何が必要かっていうところなんですけど、これまでに見てきたバイディレクショナルコレクションプロトコルに準拠させるところまでで必要な機能要求がありましたけど、これ以上のものは特に追加要件としてはないんです。ただし、関連型については追加の要求があって、制約かな、制約があって、Indices インデックスの範囲ね、それを表現する方はランダムアクセスコレクションに準拠している必要がある。これによってインデックスの任意の場所をランダムアクセスできるよっていうインデックスの移動が O(1) でできるよっていう約束といったものも追加される。

あと、サブシーケンスもランダムアクセスコレクションに準拠していることっていう条件が付いている。これは何でですかね？ランダムアクセスコレクションの部分コレクションはランダムアクセスコレクションっていう性格を継承しますよっていう、ただの約束ごとかな。そんな気がしますけど。確かに全体的なパフォーマンスは上がってきますからね、メソッドチェーンとかしたようなとき。それと、あとは性能を保証するためにインデックスの方が Strideable に準拠しているっていう必要があるんです。インデックスの方が Strideable に準拠していることっていうことは、Strideable は次が何っていうのがわかるっていう性格ですよね。これを性能の保証につながるのか、なんとなくどうかなとも思いましたけど、いまいちピンとこないな。インデックスの方が Strideable に準拠していなかったとするとランダムアクセスコレクションの性能が落ちてくるんですかね？ index(after:) や index(before:) が O(1) で行えるぐらいの特徴しか伺えないですけれど、他に何かあるのかな。 とりあえず、もう1個先を見ていきましょう。インデックスオフセットバイとディスタンスフロムがオーダー1で実行できることは大事なところですね。これがランダムアクセスコレクションの根幹です。オフセットでオーダー1で移動でき、ディスタンスがオーダー1で取れるっていうのは非常に重要です。

ここで、ストライダブルが何でインデックスの型として求められるのだろうと思った方はいませんか？ストライダブルは何を要求しているのでしょうね。インデックスはComparable（比較可能）ですよね。比較可能性は、今までのコレクションでも準拠していました。そしてストライダブルは距離が取れるんですね。これが欲しいのでしょうか。でも実装次第でなんとかなるため、ランダムアクセスコレクションプロトコルがわざわざ制約として加える必要があるのかまではわかりません。ただ、ストライダブルはストライドとして距離があり、distance(to:)で他のストライド、つまり自分自身との距離がオーダー1で取れたり、advance(by:)で移動することがオーダー1で行えると約束されているので、これを期待しているのかもしれません。

そうかもしれないですね。一連の流れとして、ストライダブルに準拠していなければランダムアクセスコレクションがオーダー1を保証できなくなるわけではないですが、効率化を想定するとインデックスの型がストライダブルであるほうが良いです。インデックスをオーダー1で自由に扱えるし、インデックスオフセットバイやディスタンスフロムもそうですし、インディシーズもランダムアクセスコレクションの準拠性を同時に満たすようになってきます。

オーダー1、オーダーN、その辺りの必須なのか任意なのかについてのコメントがありましたが、結局のところ、トータルで見てランダムアクセスを提供するにはこういう規定が必要だということですね。半端なランダムアクセスコレクションであれば、バイディレクショナルコレクションに準拠させて「このカウントはオーダー1です」みたいにコメントで書いてあげるくらいのことで済むかもしれません。

何にしてもランダムアクセスコレクションに準拠していたほうが、最適なパフォーマンスが得られます。特にコレクションは標準ライブラリ内のさまざまな場所、ほぼ全体で使われているため、パフォーマンスがランダムアクセスコレクションを保証できれば全面的な効率改善が期待できます。これが重要な点です。

たとえば、自分のストラクトを作るときに、これがインデックスアクセスできるよねと思ったとき、「これをコレクションに準拠させよう」と発想を止めるのではなく、「これは逆順アクセスもできるよね」と考えて、バイディレクショナルコレクションにも準拠させてみるのが得策です。また、インデックスアクセスを効率的にオーダー1で実現できるように工夫して、ランダムアクセスコレクションに準拠させることも一考です。その際、インディシーズはランダムアクセスコレクションを想定し、サブシーケンスもランダムアクセスコレクションに準拠させるようにするのが良いでしょう。そしてインデックスアクセスをストライダブルにしてうまく調整することで、全体としてランダムアクセスを提供できるようにするのが良いと思います。

こうした考え方でプロトコル、特にコレクションプロトコルを扱っていくとよいです。このように見てみると、自分自身があまりランダムアクセスコレクションに準拠させていなかったことに気づきました。ジェネリック型やジェネリック関数をあまり使っていなかったこともあり、いまいちなコードを書いていたかもしれません。 そういう意味でも振り返ってみると、自分の中でランダムアクセスコレクションに準拠させるとか、ランダムアクセスコレクションを想定したジェネリック型を普通に作る感覚がある人はどれくらいいるでしょうか。どちらかというと、そんなつもりじゃなかったけど結果としてランダムアクセスコレクションができた、という方が多い気がします。

これはジェネリック型のときの話ですが、関数ジェネリック関数やジェネリック型、そういうプロトタイプのコードを書くとき、とりあえずコレクションでいいよね、と思って書いても結果的にランダムアクセスコレクションができ上がったりします。コレクションであるけれどもランダムアクセスコレクションではないコレクションを作る方が難しくないですか？

そうですよね、確かに。今思い浮かぶ唯一のランダムアクセスコレクションじゃないものは、本当に String だけです。コード体系によってバイト数が変わるやつです。それ以外に、コレクションであるけれどもランダムアクセスコレクションではないものってありますかね？もしくは、シーケンスだったら一方向通行のシーケンスをよく作っていたのですが、それはシーケンスであって、コレクションではないです。コレクションでありながらランダムアクセスコレクションではないものって、あまり思い浮かびませんね。

コメントでイテレーターはシーケンシャルのみでランダムアクセスに対応していないといただきましたが、イテレーターはシーケンスの場合も結構ありますよね。中身を壊していったりするので、でもイテレーターはコレクションではない。

そうですね、インデックスアクセスをする機会のあるイテレーターは少なそうです。イテレーターは毎回実行するときに同じ結果を得られる保証がないはずなので、コレクションではないはずです。

そうですね、保証するイテレーターというのもありますね。インデックス付きのイテレータープロトコルをちょっと見てみましょう。インデックス付きのイテレータープロトコルは、これは別に何かに準拠しているわけではないですね。イテレーターシーケンスってなんだ？ストラクトか、そんなのもあるんですか。そうですね。

とりあえず、イテレーターで仮にコレクションみたいなインデックスアクセスが必要なものがあったとしても、イテレーターの役割としてはシーケンシャルで十分なので、わざわざランダムアクセスをしないですね。シーケンスよりですね。時間も結構引いてきて、微妙な感じで終わる回になりそうですが、もしこの性格で「これはシンプルなコレクションが最適だ」と思いつく人がいましたら、ぜひ思いついたときにこの勉強会内、またはOJTチャンネルでも教えてください。新しい発見がありそうで楽しみです。

はい、じゃあ時間になりましたので、今日の勉強会はこれで終わりにしようと思います。次回以降はまた「The Swift Programming Language」のランゲージガイドに戻っていこうと思いますので、またよろしくお願いします。お疲れ様でした。ありがとうございました。