リーナス・トーバルズの連結リスト削除術に海外で賛否
姉妹サイトの新着
2016年のTEDインタビューでリーナス・トーバルズは、Cで単方向連結リストからノードを削除する2つの書き方を示し、『良いプログラミングの趣味』とは何かを説明した。先頭ノードだけ特別扱いするif文を使う方法と、ポインタへのポインタ(Node **indirect)で特別扱いそのものを無くす方法だ。この動画が4chanの/g/(技術板)で改めて話題になり、『そもそも今はVectorのような汎用コンテナを使うべきで単方向連結リストは不要』という意見と、『標準ライブラリに頼れないブートローダーやカーネルのようなシステムプログラミングでは今も有効』という反論が交わされ、C言語にジェネリクスや所有権の概念が無いことをめぐる議論に発展した。
多くのプログラマーは『直前のノード』を記憶しておき、リストの先頭を削除する場合だけ特別扱いのif文を書く。
リーナスは『ポインタへのポインタ(Node **indirect)』を使えば、この特別扱いそのものを丸ごと無くせることを示した。
その使いどころは?
特に無い
どの言語でもこんなのただの list.remove(thing) で済む
このトリックがあるから、Cは連結リストを扱うには本気で最強の言語だと思う。ノードの『next』フィールドへのポインタが作れない言語だと、先頭や末尾を特別扱いするしかなくなる。
そうそう、だからCを使うんだよ。コンピュータは与えられた通りに動くし、Cはそのコンピュータの動きに直接アクセスできる。とはいえCにもまだ改良の余地はあって、C委員会は実装が固まるまで何もしてくれないから、こういうトランスパイラでCを拡張するしかない → https://github.com/loosestrife/c42
うん、自分も同じやり方にすると思う
単方向連結リストの使いどころ? さあね
>C言語なのに
>ジェネリックなコンテナ
なるほど、何が言いたいかは分かった(笑)
>言語そのものにプリミティブとして組み込まれるべき基本機能
vectorのどこにもプリミティブな要素なんて無いだろ
つまりプリミティブじゃないってことだな
なんで4chanで嘘つくんだよ
こんなのは標準ライブラリに入ってて当然のやつだろ
どうやって? これはCだぞ。ジェネリクスが無いし、あったとしてもデストラクタや所有権(ownership)の概念も無い。あらゆる単方向連結リストに通用する形でこの関数を汎用化するなんて絶対無理だ
あくまでおもちゃの例だよ
他サイトの新着
英語が第二言語の奴の意見なんて興味ない
それってループごとに参照と参照解除が1回余計に増えてない?
いや、同じことだよ
可変サイズの逐次データ格納
カーネルのソースを読めば分かる
この話題の背景と論点
この元ネタは2016年にTEDで行われたリーナス・トーバルズのインタビューで、彼が「プログラマーに必要なのは才能より良い趣味(taste)だ」と説明する際に使った具体例。先頭ノードだけを特別扱いするコードは一見自然だが、ポインタへのポインタを使えば特殊処理そのものを消せるというのが核心で、「分岐を減らすこと」自体が『良いコード』の指標だという主張だった。スレで割れたのは、この考え方が現代のC/C++開発でどれほど実用的かという点。Vector派は汎用コンテナの利便性とキャッシュ効率を主張し、反対派はブートローダーやカーネル開発のような標準ライブラリに依存できない現場では、単方向連結リストと手書きポインタ操作が今も現役であることを挙げた。なお、スレには国籍を揶揄する差別的なレスが複数あったため、記事では除外している。
※本記事は海外掲示板 4chan /g/ (Technology) のスレッド「> In a 2016 TED interview, Linus Torvalds showed two ways to delete a node from a singly linked list in C to explain wha」から抜粋し、編集部で日本語に意訳したものです。訳文の責任は当サイトにあります。









まだコメントはありません。