アルゴリズムを理解する

(音楽) (拍手) ご来場ありがとうございます これから40分間 私デイブが 私たちのプログラムが動く 仕組みをお話しします ただし 技術的なヒントや 特定のアルゴリズムが この話の主題ではありません 目的は コードに内在する 根幹的なものを 明らかにすることです

プログラミングとの 新たな関係性を― 提供できれば幸いです このアプローチの発見で 私のキャリアに転機が訪れました 私がソフトウェアライブラリを 重視する理由であり コードの信頼性 保守性 パフォーマンスにもつながります 本題の前に 友人を１人ご紹介しましょう

“クラスティ”です (拍手) 彼は古いタイプの人間で デバッガを信用せず 統合開発環境には目も向けません 彼が好むのは80文字24行の ターミナルウィンドウです 現代の流れに逆らう 彼のような人物を 21世紀に引きずり込むのは大変です 考え方が違います ただ 学べる点もいくつかあります

例えば 彼はこう言います “プログラミングは 真実を解き明かす” これを理解するため コードを書いてみました

“Shapes”というプログラムです

今は形状の配置機能だけですが 将来的に描画機能の追加も 目指しています

まず注目するのは “選択を削除”コマンド この実装を通じて 私は多くを学びました 配列からの削除を学ぶ際 恐らく皆さんも 似た経験をしたことでしょう 大抵は こんな風に始めます

これが削除です

ループで０から数え

目的の位置で “削除”を呼び出します そしてループが続いて… おっと 問題発生です

反復回数より 配列が短くなってしまいました 幸い Swiftのテストで このバグは発見できます しかしＣ言語だと そう簡単にはいかないでしょう これを修正する場合 forループをwhileループにし 各反復でカウントを調べます

しかし これにもバグはあります 隣り合う２つの要素を選択し １つ目を削除すると―

続く要素が移動します

このバグは少し厄介です テストを実行しない限り 見つかりません

運良く気付けた場合 インクリメントを elseブロックで囲み修正します

これで本当に うまくいったでしょうか？ 恐らく問題なく動くはずです これで試練を１つ乗り越えました この９行を頭にたたき込めば 将来 削除をする時に使えます

ただ 異論のある人もいるでしょう もっといい方法がありますからね いったん この方法を見つければ 前の９行は もう必要ありません 反復制限と次のアイテムの インデックスは “remove(at: i)”により 常に変わります ｉのあとの配列の一部が 変わるからです

でも後ろ向きなら 未変更の配列の反復で済みます この方法なら 不具合も起こらないので 私は愛用してきました

でも数ヵ月前―

アプリケーションを いじっていた時のことです 複雑なキャンバスから 図形の半分を削除しようとしたら iPadが３秒ほどフリーズしました

私はサーマルカップに入れた ラテを飲みながら 取り得る選択肢を考えました

コードはクリーンで 処理も単純なのに 何が悪かったのでしょうか？

調べると ホットスポットはここです 私は困りました

その時 コーヒー豆を抱えた クラスティが現れ こう聞いてきたんです “お手上げか？”

私はうなずき 状況を説明しました

“関連のドキュメンテーションは 見たのか？”

私は“remove(at:)”の クイックヘルプを見てみました

“ほら 問題はそこだ”

と言って 画面に 指紋を付けてきました

私は その指紋を クロスで拭き取りました

“どうだ 分かったか？”

私は答えました “配列の長さに比例した ステップ数が―” “要素の削除には必要だ” 配列では後続の要素は 新たな位置に動くので 理にかないます

“そのことと 選択を削除との関連性は？” 私は考えます

彼はのど飴を取り出し 並べ始めました “試してみろ”

“選択を削除”では 選択した要素ごとに O(n)の処理を行います 選択できるのはｎ個までの要素で ステップ総数はｎの２乗に 比例します

クラスティは付け加えます “順方向でも逆方向でも それは二次式だ”

要素の数が10から20の 小さなテストの場合 ステップ数は数百のみです 速さも申し分ありません 問題は数が増えた時です

50の２乗は2500 100の２乗なら１万

テストが左下の小さな範囲内なら 問題はないでしょう しかし 人々が管理する データ量は増え続けており それに伴い デバイスの メモリ容量も増えています 予測されるニーズにとって スケーラビリティは重要です

問題は分かりましたが どう対応すべきでしょうか？ クラスティは 飴を口に入れながら言います “そのためのアルゴリズムがある”

しかし私はアプリケーションの デベロッパです アルゴリズムのことは 専門外になります アルゴリズムのデータ構造も 仕事の面接対策で 勉強した程度にすぎません 実際のプログラミングで 新人と一流を分けるのは コントローラなどをまとめ システムを作る能力です

“間抜けめ”と彼は言いました

“コンピュータの仕事は？”

計算です “どこに計算の方法が？”

私のコードに アルゴリズムは見当たりません

彼は否定します “そんなことはない この辞書で意味を調べてみろ”

私は辞書を脇によけ “アルゴリズムの定義”と Spotlightに入力しました

“演算手続き･問題解決の プロセスまたは一連のルール”

確かにコードに似ていますが 確証は持てません “筆算だってアルゴリズムだ” 彼は言います

再びSpotlightに入力しかかると “紙に！”と言われ 困って 話題をコードに戻しました

では― どんなアルゴリズムが 私の問題を解決できますか？ “手本を見せる お前のマシンを貸せ” “トラックパッドをオフにして…” “まずは この役立たずを消す”

“そしてshapes.removeAll…と 入力” “さあ これで試してみろ” クラスティは席を離れました 私にコードを検証させるためです

調べてみると コードの問題は 解決されていました 次に 私はクイックヘルプを開き “removeAll(where:)”を 調べました

“remove(at:)”のように 計算量はコレクションの長さに 比例するようです でもループには入れないので これが すべての処理の計算量です これがもたらす 違いの一部をご紹介しましょう

ｎが意味する アルゴリズムの 実行時間と問題のサイズは 線形比例します オレンジはｎの２乗の線です 一次のアルゴリズムは 小さな問題では効率が悪く 徐々に二次よりも高くなります ちなみに一次のアルゴリズムの コストがいくら高くても それは問題ではありません 問題のサイズが大きくなれば ある点以降 一次が常に上回ります なお これは スケーラビリティの話です

さて スケーラビリティの問題は 解決しましたが 逆方向の削除に対して 標準ライブラリはどう改善するのか？ Swiftはオープンソースなので GitHubからデータを引き出せます

目に付くのはコメントの部分です クイックヘルプのソースで アルゴリズムの動きと計算量を 記述しています

次に“removeAll(where:)”は 単なるメソッドではありません 汎用アルゴリズムで 他のコレクションでも動作します 主な機能は次の２つ 要素を並べ替える “MutableCollection”と 長さと構造を変える “RangeReplaceableCollection”

ベースは複数の O(n)アルゴリズムです １つ目は “halfStablePartition” ある述語を満たす要素を 後ろに移動し―

接尾辞の先頭を示します “halfStable”は “半安定”という意味です 動かない要素の順序は保持しますが 後ろに移動する要素は入れ換えます

次の“removeSubrange”は 場合により下位範囲を削除します

部分範囲の表記は

コレクションの終わりの範囲を 記すのに便利です

“removeSubrange”は パブリックAPIの一部ですが “halfStablePartition”は 実装の詳細になります

ここでは 一部だけを 取り上げます まず 接尾辞の先頭の要素の 位置を検索する― “firstIndex(where:)”を 呼び出します ループ変数をｊに設定 ループインデックスｊが 反復ごとに１つを前に動かします ｊが要素を１回 通過するわけです

順序と計算量が見てとれます

最後に このメソッドは 長さを変えず要素を再配置するため 可変コレクションの 適合性に依存します

これが私の学んだ― Swiftの標準ライブラリです 性能特性が文書化された― 一連のアルゴリズムが 含まれています 実装についても触れましたが それなしでも使えるよう 設計されています

ライブラリを効率的に使うには 公式ドキュメントが便利です “Playground”の解説もあります 内容が盛りだくさんで 大変に見えますが 全部 覚えなくても大丈夫 内容に触れて知るだけで 次につながります

最後に クラスティによる 別の教えも紹介しましょう 左右どちらが簡潔明快ですか？

左の場合 読んで 考える必要があります コメントも加えましょう ただ コメントを付けても 逆順の反復は厄介です 他の人も触れるよう さらに説明を加えましょう

一方で― 右のコードは末尾クロージャで より明快です

では 再びご覧ください どちらが正しいですか？ 左はコメントが付いていても 比べると 右の方が ずっと効率的に見えます アルゴリズムを使ったおかげです

ショーン･ペアレントは コードの指針を提案しました “ループは アルゴリズムの 呼び出しで置き換える” “ない場合は自作し そのアルゴリズムにループを移す”

その意味を理解いただけるよう さらに説明を続けたいと思います そこで 皆さんが最後に見た― スパゲッティコードを 思い出してください

ループだらけ？　でしょうね

では こちらを 速度も簡潔さも勝るコードを 書いてみました 私はクラスティに礼を言い― 仕事を切り上げて 帰り支度を始めました しかし 彼は疑念の目を向けます “とんでもないミスをしてるぞ”

私は帰るのを諦め コードのループを探し始めます ファイルのコマンドは―

最前面に移動

最背面に移動

選択した図形を１つ前面に移動 繰り返しましょう

選択した図形を１つ背面に移動

最後に 左のリスト内で直接移動

操作自体はシンプルに見えますよね でも隣接しない図形を 複数 選んでも 正しく動作させる必要があります

理にかなうのは 選択された複数の要素を 隣接させることでしょう １番前の選択図形を前に出したあと 残りの選択図形を その下にまとめる

背面に移動する時は― １番下の選択図形を移動し 残りを その上にまとめる

話の全部を理解できなくても 大丈夫ですよ この詳細を説明できるような コードを用意しました

これは“bringToFront”です

このコードを見ると “shapes”にO(n)ループがあり removeとinsertの ２つのO(n)演算があります つまりこれはｎの２乗です

他の４つのコマンドにも 同じ問題が見られます これらは配列上をループし 挿入と削除を実行 いずれも二次です

この時点で私は心が折れ クラスティに助けを求めました “今夜は社交ダンスに行くので 時間がないが―” “とにかく始めよう” 私はコードを見せました

彼の最初の質問は “この仕組みは？”です

whileループがあり ｊは挿入ポイント ｉは要素を追跡します “コードでなく言葉で説明を！” 彼は言いました

選択された図形を前面に移動し 順序は維持します

“コメントで記入し読み上げろ”

入力は速いんです

選択図形を前面に移動し 順序は維持

“内容に聞き覚えは？” これはまるで “halfStablePartition”です こちらは完全に “stable”ですがね “これの名前は？” “stablePartition？”

“そのとおりだ” “オープンソースのファイルが 実装の参考になる”

私はファイルを入手 コードにコメントは残したまま コーディングを再開しました

しかし問題が発生します

“stablePartition”は 接尾辞への要素の移動を示す 述語を取ります “bringToFront”では 後方に動かす観点が必要です クラスティは “思い描いてみろ”と言います 私は未選択の図形が 後ろに集まる様子を想像し 答えを得ました

“sendToBack”では述語を逆にし 選択図形を後ろに送ります

いよいよコーディングの時間です クラスティも夜のダンスへと 繰り出すと思ったのですが “ちょっと待て”と私を止めました “スケーラビリティを チェックするんだ”

確かに クイックヘルプを開きます

計算量は(n log n)

これを考えるため log nに注目します

すぐに水平になり 大きくなるほど 増加は鈍化し 一定に近づいていきます これにｎを掛けます

O(n)ほど増加することなく 徐々に線形に近づいていきます 従ってO(n log n)は O(n)と同じものとして扱えます

この結果には非常に満足しています

少し話を戻しましょう “bringForward()”は 一番前の選択図形を前に出して 後ろに他の選択図形を集めます ただ クラスティは この方法に反対です “あの図形は並んで ダンスでも踊るつもりなのか？”

そして再び のど飴を出すと―

軽やかな手さばきで “bringForward()”を実行しました

“もう１回見せよう” ペテン師のカモになった気分です

“見覚えは？” ないよ 彼は数を減らします

“これでどうだ？”

なるほど “stablePartition”です 何となく分かりました

選択された最前面の図形を その前に移動します そこから始まる 配列のセクションを分離すれば それを分割できます

でも コレクションの 一部だけを修正する方法は？ “スライスを知らないのか？”

“predecessor”で始まる “shapes”

“これをアルゴリズムに取り込み 調整するんだ”

さて…

計算の効率性と正確性への 人類の探求は コンピュータに先んじ 古代エジプトから続いています コンピュータの発明以降 それは活発化しました

標準ライブラリに 必要なものがなくても テストや文書などが 利用できるかもしれません 必要なものを検索できる 能力が問われます

コードに戻りましょう 先ほどのスライスですが 型を調べると 配列ではありませんでした

ここまで“stablePartition”を 配列などに使い 配列スライスにも使えました 汎用的なのかもしれません “もちろんだ” “stablePartition”と 配列の仕様の関係は？ “関係はない” “bringForwardは 図形や選択と どう関係してると思う？”

図形に作用し 選択図形を前面に送ります “そうだ 関係ない” 私の話は無視です

“のど飴の列で bringForwardできるか？”

“もちろんできる” つまり図形と関係はない

ジェネリックにしろと いうことですか？ 時期尚早の気もします 私の質問に答えず クラスティは質問します “このメソッドのテスト方法は？”

キャンバスを作成し ランダムに図形を追加 その一部を選択して 最後に… でも マズい考えだと 分かっていました それを全部やっても 関数や初期化子の― テストになるかは分かりません IsSelectedプロパティや AddShapeメソッドも同じです テストケースが必要ですが そのコードには― テストの必要がないのが 理想でしょう のど飴を前に送る場合は “Playground”の int型が使えそうです こんな感じで ３で割れる数を前に送ります

その一方 ランダムに生成される― 膨大なテストデータを投げ アルゴリズムの拡張性を確認します しかし今のコードでは どちらも簡単ではありません 私はクラスティの正しさを認め “bringForward”を ジェネリックに変え始めました 最初に“Canvas”から 切り離します

そして“Shape”の配列に移動 これにより“shapes”を “self”に変えます

そして図形の動きを示す 述語を渡すことで “Selected”から切り離します

コンパイルできました すばらしい この時点で“shapes”に 依存関係はなくなりました where節を削除できます

これで どんな配列でも 前に出せます ダンスの練習をしていた クラスティの方に目をやりました 彼は私に質問します

“bringForwardと配列の関係は？”

ありません この依存関係も取り除きます

この“stablePartition”は 可変コレクションの適合性を 要求します このコレクションを移動します

インデックス型が int型と一致しませんね これを直します

これをしたことは？ お勧めしません

これを見たクラスティは 踊るのをやめました

何か？ “それは新人のやることだ”

“まず０と比較するが 配列スライスには適さない”

このインデックスの始まりは ０じゃないんですね スライスのインデックスは 元のコレクションの インデックスに対応しています

スライスを利用した 汎用アルゴリズムでは この関係は重要です

この問題の解決には 開始インデックスを比較します “本当の問題は bringForwardが どのように…” 整数インデックスに関係するか ですよね？ 減算することで ｉの前に インデックスを取得します

クラスティは また飴を出しました

そして 机に２本の指を置き 右手が最初に緑色の飴を 指すまで 動かしました

“後ろ向きの動きじゃない” これはアルゴリズムだと 私は気付きました “これをindexBeforeFirstと 名付けよう” “コードは他の人が書いたと思って 注意深く見るんだ” 彼は不要な部分を消し始めました これに これも

“predecessorは―” “述語が満たされる最初よりも 前のインデックスだ” “いいコードができたぞ” 確かに 彼の言葉は正しいですね 図形 選択 配列 整数の 詳細を取り除いたことで クリアになりました 本質のみが残りましたからね

“indexBeforeFirstを 自分でコードで書けるか？”

徐々に理解できているので いけそうな気がします

タイプは得意なんですよ “後続が述語と一致する 最初のインデックスを返す”

この出来には満足です クラスティ 次の問題を！

“何か忘れてないか？” 彼は言います 何のことでしょうか コードは簡潔明瞭です “セマンティクスだ 意味が分からないと使えない”

その時 気付きました 新しいアルゴリズムを使う時 コードの意味や効率を知るため ドキュメントを参照します アルゴリズムは流用改変が多く 参照ドキュメントは同じです

私は最近 ある面接で 文書の役割について聞きました 彼の言葉は印象的でした “本当に重要なものです”

“文書は いわば 抽象化の塔と言えます” “私たちが下を気にせず 上に構築ができるのは―” “文書化された 基盤があるからです”

アプリケーション開発者として あなたは 塔の最上階で 働いているとしましょう ハードウェア基盤から伸び フレームワークを貫く塔です

そうした中で 独自のメソッドを使う場合は 文書化しましょう

面接の彼は採用され そこにいます

私は 新しいアルゴリズムを 文書化しました

これで実装のことは忘れられます

疑問点にはクイックヘルプです

“bringForward”も文書化を

いいですね

問題はすべて解決できましたが ここで“stablePartition”の 中身を見たくなりました 結果 美しく建設的な アルゴリズムでひと安心です パブリックメソッドが コレクションの数を取り ヘルパに渡します

使うのは分割統治法です カウントが２未満の場合 基本ケースを処理し 分割点が コレクションの 先頭か末尾かを判断します

次に コレクションを ２つに分けます

ここでは アルゴリズムの挙動を 信じなければなりません 左半分に “stablePartition”を実行 右半分にも

両端を見た時 すべてが 正しい位置にあるのが分かります

でも中央の部分は交換が必要です

なお この例のように 長さは一定とは限りません 交換にも 幸いアルゴリズムがあります それは“rotate”です

“rotate”には詳しく触れませんが “stablePartition”と 同じファイルで 実装が見られます

話を戻しましょう こちらは―

図形リストへのドラッグの実装です 複雑でバグも少なくありません 戦略は 一時バッファを 割り当て―

挿入点の前の図形をループします 選択した図形を抽出して 挿入点を調整 残りの図形を別々にループし その後 選択したものを抽出します

最後に 再挿入です

やっと正しいコードができたので もう触りたくありません 最後のバグは１週間前でした

ただ このプロセスは うまくいったので 一度 可視化しようと思っています

今の見覚えあるな　もう１回見よう

まず これを行い 次にパーツを別々に扱う…

そうか 逆の述語を持つ ２つの“stablePartition”だ

汎用アルゴリズムは ２つにまで縮小されました

これが“Canvas”の内容です

古い方と並べてみます

悪くありません

再利用可能で 文書化された― 汎用アルゴリズムに変身しました

ここまで見てきたのは― アプリケーションドメインに 固有の詳細 コードの基本的な動作 再利用可能な 汎用コードでの再現です 練習を必要とします 実用的な観点から言うと 汎用アルゴリズムは 不必要な細部を切り離せます 再利用可能で検証も簡単 それに より明確です また プログラミング好きに やりがいを与えてくれます それから 実際にハードウェアの 制約の中で行う― 真実と美の探求でもあります まさに“プログラミングは 真実を解き明かす”です

計算を一級市民と考えましょう 権利と義務を背負って 型とアーキテクチャに向き合い 識別し 名前を付け テストし 意味と性能を文書化しましょう

最後にショーン･ペアレントの 言葉をご紹介します

“コードの品質を上げたいなら” “コーディングの基準を No Raw Loopsに置き換えよう”

以上です (拍手)