あまりにも多すぎる連結リストでRustを学ぶ

問題がある、または完成したコードを一度に全部確認したいですか？すべてGithubにあります！

注記: この本の現在の版はRust 2018を対象に書かれています。 Rust 2018はrustc 1.31（2018年12月8日）で初めてリリースされました。あなたのRustツールチェーンが十分に新しい場合、cargo newが作成するCargo.tomlファイルには edition = "2018"という行が含まれているはずです（あるいは、これを遠い未来に読んでいるなら、もっと大きな数字かもしれません！）。古いツールチェーンを使うことも可能ですが、秘密のハードモードが解放され、本書の本文ではまったく触れられていない追加のコンパイラーエラーに遭遇することになります。わあ、楽しそうですね！

Rustで連結リストを実装する方法について、かなり頻繁に質問されます。正直なところ、答えは要件によって変わりますし、その場で質問に答えるのがそれほど簡単ではないのは明らかです。そのため、この疑問に包括的に、そしてきっぱりと答えるために、この本を書くことにしました。

このシリーズでは、6つの連結リストを実装してもらうことだけを通じて、基本的および高度なRustプログラミングを教えます。その過程で、次のことを学べるはずです。

次のポインター型: &, &mut, Box, Rc, Arc, *const, *mut, NonNull(?)
所有権、借用、継承された可変性、内部可変性、Copy
すべてのキーワード: struct, enum, fn, pub, impl, use, …
パターンマッチング、ジェネリクス、デストラクター
テスト、新しいツールチェーンのインストール、miriの使用
Unsafe Rust: 生ポインター、エイリアシング、stacked borrows、UnsafeCell、variance

そうです。連結リストは本当にひどいので、それを現実のものにするだけで、これらすべての概念に向き合うことになります。

すべてサイドバーにあります（モバイルでは折りたたまれているかもしれません）が、すぐに参照できるように、これから作るものを以下に示します。

認識をそろえておくために、私がターミナルに入力するコマンドはすべて書き出します。また、このプロジェクトの開発にはRustの標準パッケージマネージャーであるCargoも使います。 Rustプログラムを書くのにCargoが必須というわけではありませんが、rustcを直接使うより はるかに優れています。ちょっといじってみたいだけなら、 play.rust-lang.orgを使ってブラウザー上で簡単なプログラムを実行することもできます。

後のセクションでは、追加のRustツールをインストールするために「rustup」を使います。すべてのRustツールチェーンをrustupでインストールすることを強くおすすめします。

さっそく始めて、プロジェクトを作りましょう。

> cargo new --lib lists
> cd lists

作業内容を失わないように、各リストは別々のファイルに配置します。

本物のRust学習体験には、コードを書き、コンパイラーに怒鳴られ、それがいったい何を意味するのかを理解しようとすることが含まれる、という点には触れておくべきでしょう。私は、これができるだけ頻繁に起こるよう慎重に配慮します。 Rustの一般に非常に優れたコンパイラーエラーとドキュメントを読み、理解することを学ぶのは、生産的なRustプログラマーになるうえで信じられないほど重要です。

とはいえ、実はこれは嘘です。これを書いている間、ここで見せているよりも はるかに多くのコンパイラーエラーに遭遇しました。特に後半の章では、どの言語でも遭遇するような、ランダムな「入力（コピペ）を間違えた」系のエラーはあまり見せません。これは、コンパイラーに怒鳴られることのガイド付きツアーです。

かなりゆっくり進めていきますし、正直なところ、ほぼずっとあまり真面目にはやりません。プログラミングは楽しいものであるべきだと思うんです、まったく！もしあなたが、最大限に情報密度が高く、真面目で、形式的な内容を求めるタイプの人なら、この本はあなた向けではありません。私がこれから作るものは何ひとつ、あなた向けではありません。あなたは間違っています。

義務的な公共広告

完全に100%明確にしておくと、私は連結リストが嫌いです。心の底から。連結リストはひどいデータ構造です。もちろん、連結リストにはいくつか素晴らしいユースケースがあります。

大きなリストの分割やマージを大量に行いたい。大量に。
すごいロックフリー並行処理の何かをやっている。
カーネル/組み込み系のものを書いていて、侵入的リストを使いたい。
純粋関数型言語を使っていて、限定された意味論と変更の不在によって連結リストのほうが扱いやすくなっている。
… などなど！

しかし、Rustプログラムを書く人にとって、これらのケースはどれも非常にまれです。 99%の場合はVec（配列スタック）を使うべきで、残りの1%のうち99%の場合は VecDeque（配列デック）を使うべきです。これらは、アロケーション頻度の低さ、メモリオーバーヘッドの低さ、真のランダムアクセス、キャッシュ局所性により、ほとんどのワークロードに対して明らかに優れたデータ構造です。

連結リストは、トライと同じくらいニッチで曖昧なデータ構造です。トライは、平均的なプログラマーが生産的なキャリア全体を通じて知らなくても幸せに過ごせるニッチな構造だと私が主張しても、反発する人はほとんどいないでしょう。にもかかわらず、連結リストには何やら奇妙な有名人のような地位があります。私たちはすべての学部生に連結リストの書き方を教えています。これは、私がstd::collectionsから排除できなかった唯一のニッチなコレクションです。 C++ではあのリストです！

私たちはコミュニティとして、「標準的な」データ構造としての連結リストにノーと言うべきです。連結リストは、いくつかの素晴らしいユースケースを持つ立派なデータ構造ですが、それらのユースケースは一般的ではなく、例外的なものです。

どうやら何人かの人は、この公共広告の最初の段落を読んだだけで、そこで読むのをやめてしまうようです。文字どおり、私の素晴らしいユースケースのリストにある項目の1つを挙げて、私の主張に反論しようとします。最初の段落のすぐ後にあるものです！

詳細な議論へ直接リンクできるように、私が目にした反論の試みをいくつか挙げ、それらへの回答を示します。Rustを学びたいだけなら、最初の章へ自由に進んでください！

パフォーマンスが常に重要とは限らない

そのとおりです！アプリケーションがI/Oバウンドかもしれませんし、問題のコードがまったく重要ではないコールドケースにあるのかもしれません。しかし、これは連結リストを使うための議論ですらありません。これは何でも好きなものを使うための議論です。なぜ連結リストで妥協するのでしょうか？連結ハッシュマップを使いましょう！

パフォーマンスが重要でないなら、配列という自然なデフォルトを適用しても 確実に問題ないはずです。

その場所へのポインターがあれば、O(1)で分割・追加・挿入・削除できる

そのとおりです！ただし、Bjarne Stroustrupが指摘しているように、そのポインターを取得するのにかかる時間が、配列内のすべての要素を単にコピーするのにかかる時間（実際にはかなり速い）を完全に圧倒してしまうなら、これは実際には重要ではありません。

分割とマージのコストが非常に支配的なワークロードでない限り、キャッシュ効果とコードの複雑さにより それ以外すべての操作が受けるペナルティによって、理論上の利点は打ち消されます。

とはいえ、アプリケーションをプロファイリングした結果、分割とマージに多くの時間を費やしているなら、連結リストで利益を得られる可能性はあります。

償却コストを受け入れられない

あなたはすでにかなりニッチな領域に入っています – ほとんどの用途では償却を許容できます。それでも、配列のコストは最悪ケースで償却されます。配列を使っているからといって、償却コストが発生するとは限りません。格納する要素数を予測できるなら（あるいは上限だけでも分かっているなら）、必要な領域をすべて事前に予約できます。私の経験では、必要になる要素数を予測できることは非常によくあります。特に Rust では、まさにこの場合のために、すべてのイテレーターが size_hint を提供しています。

そうすれば、push と pop は真に O(1) の操作になります。そしてそれらは、リンクリストでの push と pop よりもかなり高速になるでしょう。ポインターをオフセットし、バイトを書き込み、整数をインクリメントするだけです。どんな種類のアロケーターを呼び出す必要もありません。

低レイテンシとしてはどうでしょう？

しかし確かに、負荷を予測できない場合には、最悪ケースのレイテンシを削減できます！

リンクリストはスペースの無駄が少ない

さて、これは複雑です。「標準的な」配列のリサイズ戦略は、配列の空きが最大でも半分になるように拡大または縮小することです。これは確かに大量の無駄なスペースです。特に Rust では、コレクションを自動的には縮小しません（どうせまた埋め戻すなら無駄だからです）。そのため、無駄は無限大に近づき得ます！

しかし、これは最悪ケースのシナリオです。最良ケースでは、配列スタックには配列全体でポインター3つ分のオーバーヘッドしかありません。基本的にオーバーヘッドはありません。

一方、リンクリストは要素ごとに無条件にスペースを浪費します。単方向リンクリストはポインター1つ分を浪費し、双方向リンクリストは 2つ分を浪費します。配列とは異なり、相対的な無駄は要素のサイズに比例します。巨大な要素なら、この無駄は 0 に近づきます。小さな要素（たとえばバイト）なら、これは最大で 16 倍ものメモリオーバーヘッド（32 ビットでは 8 倍）になり得ます！

実際には、バイトにパディングが追加され、ノード全体のサイズがポインターにアラインされるため、23 倍（32 ビットでは 11 倍）に近くなります。

これはまた、アロケーターにとっての最良ケース、つまりノードの割り当てと解放が密に行われており、断片化でメモリを失っていない場合を仮定しています。

しかし確かに、巨大な要素を扱い、負荷を予測できず、まともなアロケーターがあるなら、メモリを節約できます！

私は<関数型言語>でリンクリストを常用しています

素晴らしい！リンクリストは関数型言語では非常にエレガントに使えます。なぜなら、一切の変更なしに操作でき、再帰的に記述でき、さらに遅延評価の魔法によって無限リストも扱えるからです。

具体的には、リンクリストの良いところは、可変状態を必要とせずに反復を表現できることです。次のステップは、単に次のサブリストを訪問するだけです。

Rust では、この種のことは主にイテレーターで行います。それらは無限にもでき、関数型のリストと同じように map、filter、reverse、concatenate でき、しかもすべてが同じように遅延的に行われます！

Rust では、部分配列を*スライス*として簡単に扱うこともできます。関数型言語でよく使う head/tail の分割は、単に slice.split_at_mut(1)です。長い間、Rust にはスライスに対するパターンマッチングの実験的な仕組みがあり、それは非常にクールでしたが、その機能は安定化された際に簡略化されました。それでも、基本的なスライスパターンは気が利いています！もちろん、スライスはイテレーターに変換できます！

しかし確かに、イミュータブルなセマンティクスに制限されているなら、リンクリストは非常に便利です。

なお、関数型プログラミングが必ずしも弱いとか悪いと言っているわけではありません。しかし、それは根本的にセマンティクス上の制約があります。つまり、物事がどのようにあるかについて語ることは主に許されますが、それらがどのように行われるべきかについては語れません。これは実際には機能です。なぜなら、コンパイラーが大量の特殊な変換を行えるようになり、あなたが心配しなくても、物事を行う最善の方法を見つけられる可能性があるからです。しかしこれは、それについて心配することが できる余地を失う代償を伴います。たいていはエスケープハッチがありますが、ある限界を超えると、結局また手続き型コードを書いているだけになります。

関数型言語であっても、実際にデータ構造が必要なときには、その仕事に適したデータ構造を使うよう努めるべきです。確かに、単方向リンクリストは制御フローの主要な道具ですが、大量のデータを実際に保存して問い合わせる方法としては、本当に貧弱です。

リンクリストは並行データ構造を構築するのに優れています！

はい！とはいえ、並行データ構造を書くことは実際にはまったく別物であり、軽く見るべきものではありません。間違いなく、多くの人が検討すらするようなものではありません。いったんそれが書かれてしまえば、あなたは実際にはリンクリストを使うことを選んでいるわけでもありません。MPSC キューか何かを使うことを選んでいるのです。この場合、実装戦略はかなり遠いところにあります！

しかし確かに、リンクリストはロックフリー並行性という暗黒の世界のデファクトの英雄です。

むにゃむにゃ、カーネル、組み込み、何とかかんとか、intrusive。

それはニッチです。自分の言語のランタイムすら使っていない状況について話しているのです。それは、自分が何か奇妙なことをしているという危険信号ではないのでしょうか？

それはまた、非常に unsafe でもあります。

ですが、もちろん。スタック上に素晴らしいゼロアロケーションリストを構築してください。

イテレーターは無関係な挿入/削除によって無効化されない

それは繊細なダンスをしているようなものです。特に、ガベージコレクターがない場合はそうです。詳細次第では、あなたの制御フローと所有権のパターンはおそらく少し絡まりすぎている、と私は主張するかもしれません。

しかし確かに、カーソルを使えば本当にクールでクレイジーなことができます。

リンクリストは単純で、教育に最適です！

まあ、そうですね。あなたはまさにその前提に捧げられた本を読んでいるのです。単方向リンクリストはかなり単純です。双方向リンクリストは、これから見るように、少し厄介になり得ます。

一息つきましょう

さて。これで片付きました。山ほどリンクリストを書きましょう。

第1章へ進みましょう！

Keyboard shortcuts

Learning Rust With Entirely Too Many Linked Lists 日本語版