Rust part9

**デフォルトの名無しさん** · 2020/08/23(日) 01:07:35.52

Mozilla発のRust言語のスレ

公式
https://www.rust-lang.org/
https://blog.rust-lang.org/
https://github.com/rust-lang/rust

Web上の実行環境
https://play.rust-lang.org

前スレ
Rust part8
https://mevius.5ch.net/test/read.cgi/tech/1579834072/

**デフォルトの名無しさん** · 2020/09/03(木) 22:16:06.69

>>52
それをセルフホストできてないというかどうかは知らんがビルドしたいならx.py使えよ。
bootstrapにはそれ用のオプションがちゃんとある。

**デフォルトの名無しさん** · 2020/09/04(金) 08:11:24.22

rustc: 1.48.0-nightly (130359cb0 2020-09-01)
src: 1.46.0
でもダメだった

>>53
丸ごとビルドしたい訳じゃなくて一部だけビルドしたい
ttps://qiita.com/kotetuco/items/54af67d5663013ad0db7#rust-core-library%E3%82%92%E7%94%A8%E6%84%8F%E3%81%99%E3%82%8B
こんな感じ。実際にはコンパイルオプションを調整したいけど
コンパイルできる組み合わせを探すしかないのか？stableとnightlyじゃコードツリーのディレクトリ構造からして違う有様だしなぁ

**デフォルトの名無しさん** · 2020/09/04(金) 10:04:14.14

>>54
coreだけでもビルドできるが…。さすがに開発中に毎回bootstrapするわけない。
https://rustc-dev-guide.rust-lang.org/building/how-to-build-and-run.html#build-specific-components

自己流で試行錯誤するよりまず公式通りにやってからカスタマイズする方がいいのでは。

**デフォルトの名無しさん** · 2020/09/04(金) 15:34:10.06

>>55
thx。それを実行するにあたって最低限必要な物ってなんだろ。書いていないような・・・
Pythonとbetaなコンパイラが必要そうっぽい事は判るけど
というかコンパイラも含めたビルドは出来るだけ避けたい
環境(Windows)やマシン(2Core/8GB)のリソース的に成功するか判らないし失敗した場合の
トラブルシュートも難しい

あとそのコマンドはnightly？beta？限定のような。1.46.0 stableのコードツリーだとディレクトリ名が違う

**デフォルトの名無しさん** · 2020/09/04(金) 18:04:10.13

>>51
ほんそれ。
ある程度はシュガライズすべき

**デフォルトの名無しさん** · 2020/09/04(金) 18:33:08.78

>>56
環境構築はREADMEだな。
https://github.com/rust-lang/rust#building-on-windows

ディレクトリはちょうど運悪く先月くらいに構成変わってて、今betaまで反映されてるから次のリリースでstableも同じになる。
とりあえず今のstableなら以下でcoreだけビルドできるはず。
./x.py build --stage 0 src/libcore
コンパイラはx.pyが適切なバージョンを勝手に取ってくるから任せればよい。

**デフォルトの名無しさん** · 2020/09/05(土) 10:06:13.78

2Core/8GBでLLVMビルドするのかなりつらそう

**デフォルトの名無しさん** · 2020/09/05(土) 13:17:51.96

forとiterの使い分けってどうしたらいいんだろ
用途？

**デフォルトの名無しさん** · 2020/09/05(土) 15:05:36.16

コードが読みやすくなる方を使う

**デフォルトの名無しさん** · 2020/09/05(土) 21:40:57.16

codewarsをRustで解いてるけどなかなか勉強になる

**デフォルトの名無しさん** · 2020/09/06(日) 00:09:09.42

戦争反対

**デフォルトの名無しさん** · 2020/09/06(日) 00:12:10.28

敗戦国に対する差別を助長するとアメリカで主張していこうな！

**デフォルトの名無しさん** · 2020/09/06(日) 13:05:53.33

Cargo.tomlにrustのバージョン指定する方法ってどうやるっけ？
どこかで見た気がするんだけどcargo reference探してもないから知ってる人いる？

**デフォルトの名無しさん** · 2020/09/06(日) 13:33:28.17

>>65
Cargoにその機能はないな。rustupの機能として
rust-toolchainファイルにバージョンとかnightlyとか書けるよ。
当然rustupを使っていないと効果はないけど。

**デフォルトの名無しさん** · 2020/09/06(日) 13:50:50.21

低レイヤーのアルゴリズム実装てrustは実は向いてないんだよ。

**デフォルトの名無しさん** · 2020/09/06(日) 20:53:31.66

>>65
MSRVのことかな
https://rust-lang.github.io/rfcs/2495-min-rust-version.html

**デフォルトの名無しさん** · 2020/09/07(月) 05:35:58.44

>>68
おお、そうそう。ありがとう

**デフォルトの名無しさん** · 2020/09/08(火) 14:08:21.21

なんでIteratorの方にはchunksとかwindowsとかないの？
Vecに変換するのめんどくさい

**デフォルトの名無しさん** · 2020/09/08(火) 14:14:25.89

stdにない理由はしらんけどItertoolsでできるっしょ

**デフォルトの名無しさん** · 2020/09/08(火) 16:58:13.30

rustのormって何でdieselしかないの？dieselが完成されてるから？それともrustがdb使う用途に使われることが少ないとか？

**デフォルトの名無しさん** · 2020/09/08(火) 18:04:31.50

rustに関わらずormって限らられたシーンでしか使えない印象

**デフォルトの名無しさん** · 2020/09/08(火) 20:34:32.20

>>70
任意のimpl Iteratorからスライス作るためにはcollectしてVecを作るなど、比較的重めの処理が必要になる
コストのかかる処理は明示的にやらせるというのがstdのポリシーなので、用意されていないのでは
あと利用者側で .collect::<Vec<_>>() を追加するだけでよくて対処が難しくないのもわざわざstdに追加しようとする人が現れない理由だと思う

**デフォルトの名無しさん** · 2020/09/09(水) 18:10:37.98

>>74
コストのかかる処理はってIteratorにないからコストかかってるのでその理由は成り立たない気がする
個人的にはIteratorとスライスという違う型に同じメソッド名が生えてるのがあれなのかなと思った

**デフォルトの名無しさん** · 2020/09/09(水) 18:23:13.97

>>72
Dieselが早いうちに作られて支配的に使われるようになって他の連携クレートもdiesel用を用意してそして誰もいなくなった的な展開
個人的にはdieselは癖強いから完成度高くないと思う、ただ連携はかなり強い

**デフォルトの名無しさん** · 2020/09/09(水) 18:58:45.43

sqlxが本名だと思う

**デフォルトの名無しさん** · 2020/09/09(水) 21:48:02.38

Sqlx良いね

**デフォルトの名無しさん** · 2020/09/09(水) 22:34:56.87

>>75
allocation不要なchunks/windowsの実装ってどうやるの？
Iterator ではなくて std::vec::IntoIter などに実装するということ？

**デフォルトの名無しさん** · 2020/09/10(木) 07:20:42.22

itertoolsの実装どんなんかしらんけど、
itertoolsのchunksは各チャンクがイテレータになってるし、
windowsのほうはtupleで帰ってくるからアロケーションしないんじゃね？

**デフォルトの名無しさん** · 2020/09/10(木) 07:23:35.08

すまん、チャンク・ウィンドウの個数分のアロケーションはさすがに発生してると思うわ多分

**デフォルトの名無しさん** · 2020/09/13(日) 20:54:26.61

VS2019の拡張機能にRustがあるんだけど、これは本物ですか？
VSCodeのとは違うみたいで情報がない

**デフォルトの名無しさん** · 2020/09/14(月) 01:42:47.60

&'static strってデータかテキスト領域どっちに入るの？デバッグ方法分からん

**デフォルトの名無しさん** · 2020/09/16(水) 01:12:00.89

Rustってむずくないですか
これ最初にプログラムやる言語じゃないよね…昔にC触ったとかそんなレベルだと全然わからん

**デフォルトの名無しさん** · 2020/09/16(水) 10:24:27.14

むずくない
めんどくい

**デフォルトの名無しさん** · 2020/09/16(水) 11:57:04.37

std::collections とかが複数形でstd::markerが単数形な理由ってなに？

**デフォルトの名無しさん** · 2020/09/16(水) 12:36:20.15

>>85
この言語は、深いことをやろうとするとメンドクサイだけではなく、
ちゃんと仕様が公開されて無い事が多いから難しくなる。

**デフォルトの名無しさん** · 2020/09/16(水) 13:09:08.47

え？仕様公開されてるだろ英語で

**デフォルトの名無しさん** · 2020/09/16(水) 13:54:55.78

自分の足も撃ち抜けない不自由な言語

**デフォルトの名無しさん** · 2020/09/16(水) 14:23:57.05

>>87
公開されていないというより確定していないことは結構ある。
細かいところでは処理系の実装の現実に頼らないとしゃーないってのは
C/C++ でもなんでも同じだし、
まあそんなもんです。

**デフォルトの名無しさん** · 2020/09/16(水) 20:12:39.40

具体的な話をしてくれ

**デフォルトの名無しさん** · 2020/09/17(木) 04:57:16.23

>>88
公開されてない。

**デフォルトの名無しさん** · 2020/09/17(木) 06:48:06.13

何の仕様が知りたくて見つけられなかったのか言ってくれよ

**デフォルトの名無しさん** · 2020/09/17(木) 09:31:52.63

チュートリアル追ってみたらLinkedListの実装に結局
unsafeなことやらなきゃいけないみたいに書いてあって
やる気なくしたアホくさ

**デフォルトの名無しさん** · 2020/09/17(木) 09:38:19.49

LinkedListはもうオワコン
あれはCPUが遅くてキャッシュミスとかあまり考えなくても良かった時代のもの

**デフォルトの名無しさん** · 2020/09/17(木) 09:49:42.39

初心者が「まずは独自コンテナクラスでも実装してみるか」っていって討ち死にしていくのはしばしば見られるよな。
Rustのコンテナ実装は高難度なので素直に標準ライブラリを使いましょう、ってどこかに書いてあるべきかも。

**デフォルトの名無しさん** · 2020/09/17(木) 09:53:23.90

高難度？ただ面倒なだけじゃなくて？

**デフォルトの名無しさん** · 2020/09/17(木) 10:01:04.46

>>97
大抵の人にとってhello worldの次にやる課題としては高難度過ぎると思うけど。
もちろんおまえにとっては簡単で面倒なだけってのは別に否定しないが。

**デフォルトの名無しさん** · 2020/09/17(木) 10:11:43.63

別にRustのチュートリアルはプログラミング初心者のためにあるわけじゃないし

**デフォルトの名無しさん** · 2020/09/17(木) 10:53:28.83

>>93
一番問題なのは、ヒープに対する参照の詳細が英語でもどこを探してもないこと。
Box<T>, Rc<T>, RefCell<T>
などの詳細と、生存期間、所有、借用、コンストラクト時のMoveの処理の話。
Option<T>はまだ分かるが。

**デフォルトの名無しさん** · 2020/09/17(木) 10:55:15.75

>>95
それは信頼できる情報か。
キャッシュミスし易いから、LinkedListは、もう動的配列より絶対的に劣る、
などというようなことを書いたまともな論文でもどこかにあるのか。

**デフォルトの名無しさん** · 2020/09/17(木) 11:01:24.99

Cアルゴリズム入門的な本があるように
Rustアルゴリズム入門的な記事があっていい気がする

**デフォルトの名無しさん** · 2020/09/17(木) 11:06:01.57

任意の場所への挿入・削除とかは動的配列よりLinkedListでやったほうが効率いいし

**デフォルトの名無しさん** · 2020/09/17(木) 11:19:25.01

>>94
unsafe使わなくてもできるよ
stdのLinkedListがunsafe使ってるのはパフォーマンスのため

独自実装のLinkedListなんでプロダクションでは使わないだろう
unsafe使わないやり方で作ってみればいいと思うよ

**デフォルトの名無しさん** · 2020/09/17(木) 11:22:36.45

>>101
まともな論文ではないけどC++のハゲがそんなこと言ってなかったっけ

**デフォルトの名無しさん** · 2020/09/17(木) 11:27:31.41

キャッシュミスしやすいのはそうだろう
メモリが連続してないんだから当然だね
ただ時代遅れってのは勝手に付け足したろ

**デフォルトの名無しさん** · 2020/09/17(木) 11:33:13.70

>>100
「ヒープに対する参照の詳細」って何じゃい？

Box<T>, Rc<T>, RefCell<T>は標準ライブラリだからライブラリのリファレンスを見る

>生存期間、所有、借用、コンストラクト時のMoveの処理の話。
こっちは一般原則だから普通に明記されてると思うけど
Language Reference本も完成はしてないから書いてない詳細もあるだろうけど
それで困るのは一般原則的なことじゃないでしょ

**デフォルトの名無しさん** · 2020/09/17(木) 12:26:42.19

C++ のコンテナは、デフォルトでベクター

ゲームプログラミングでは、プログラマー自身がまとめてメモリを確保する、
メモリ管理システムの例が、よく載っているけど、

一般用途では、ベクターの速度には勝てないのじゃないか？
2分木とか、特殊用途なら別だが

Elixir でも、リストは先頭・末尾だけが速いだけで、
中間の要素を取得するには、N / 2 要素をたどる必要がある

ただ、Elixirは関数型で、元の要素が変化しないから、
更新時だけ、要素をコピーすればよい

**デフォルトの名無しさん** · 2020/09/17(木) 13:19:52.64

C++のvectorでも深い考え無しに闇雲に使うと
要素コピー発生しまくりなアホなコードになる

**デフォルトの名無しさん** · 2020/09/17(木) 13:41:43.66

LinkedListと動的配列の違いは速度だけの問題じゃないんだな、これが。
前者はプログラミング上、後者より圧倒的に有利な場面がある。
それは、要素の識別性だ。

**デフォルトの名無しさん** · 2020/09/17(木) 14:10:37.15

C++のRAIIイディオム、SharedPointer、Moveセマンティクス
でRustにメモリ安全でどこまで対抗可能かな

**デフォルトの名無しさん** · 2020/09/17(木) 15:25:52.19

とりあえず二重開放でコケますね

**デフォルトの名無しさん** · 2020/09/17(木) 15:58:39.73

C++は確かに道具は十分揃ってるんだけど、
適切に使えるかどうかはプログラマーの注意力次第なので厳しい…。

**デフォルトの名無しさん** · 2020/09/17(木) 20:47:10.45

LinkedListが役に立たないと知ったのは結構前だな
Javaのスレで色々議論があったんだけど
LinkedListが優位になるであろう場面でもArrayListのほうが早いと断言するやつが居て
バカじゃねーの？と思いつつも実装してみたら完全にArrayListのほうが早かった
古い知識でイキってた当時の自分が恥ずかしい

**デフォルトの名無しさん** · 2020/09/17(木) 21:46:41.57

> C++は確かに道具は十分揃ってるんだけど、
> 適切に使えるかどうかはプログラマーの注意力次第なので厳しい…。
そもそもC++は注意力の前に必要知識が多すぎる

>>114
ベンチのソースとか記事ないの？

**デフォルトの名無しさん** · 2020/09/17(木) 21:47:07.97

その早いって何が？
要素の検索が？挿入・削除が？

**デフォルトの名無しさん** · 2020/09/17(木) 21:56:39.63

適当に検索した記事みてみたら普通に予想通りの内容だったけど

**デフォルトの名無しさん** · 2020/09/17(木) 22:27:03.14

リンクリストのキャッシュミスが問題になるのであれば
探索時にプリフェッチしておけばよくね？
今時の高性能なプロセッサなら大抵そういう命令を装備しているだろ
遅いのは実装がウンコなだけなんじゃ

**デフォルトの名無しさん** · 2020/09/18(金) 00:33:25.64

リストの要素がそれぞれ離れたアドレスにあるような実装だったら、クソデカキャッシュ必要になったりしない？

**デフォルトの名無しさん** · 2020/09/18(金) 02:24:56.35

最近のDDR4(?)メモリの速度の進化も凄いから、キャッシュミスがあっても、
キャッシュがヒットした場合の3倍位の速度低下で済むんじゃないかと思うし、
少なくとも、キャッシュミスによる速度低下には上限がある。
一方、LinkedList、動的配列の途中への挿入や、途中要素の削除にかかる時間は、
全体の要素数を N とした時、それぞれ、O(1)、O(N)となる。
キャッシュミスによる速度低下が高々3倍程度なのに対し、
動的配列の遅さは、要素数 N に比例してしまうから上限がない。
だから、本質的に要素数が多くなった場合には、
キャッシュミスによる速度低下とは比べ物にならないくらい
速度差は歴然たるものとなる。

**デフォルトの名無しさん** · 2020/09/18(金) 02:26:46.51

>>120
[補足]
動的配列で途中への挿入や途中要素の削除では、平均で、 N/2 要素程度のコピー動作が
入る。これを

**デフォルトの名無しさん** · 2020/09/18(金) 02:33:02.97

>>121
これをMoveに置き換えて高速になるのは、要素の中身が、Heap領域など、要素自体
とは別の場所に有る場合である。たとえば、
struct Element {
　const char *m_pszText;　// new char[]で確保したHeap領域を指す0終端文字列
};
簡単のためこれの固定長配列を書いてみれば：
Element g_arr[1024];
となる。この要素のデータを読み取る場合は次のようになる、
for ( int i=0; i<1024; i++) {
　printf( "i=%d, text=%s\n", i, g_arr[i].m_pszText );
}
この場合、m_pszTextは、ヒープ領域にとってあるから、結局、配列でも
キャッシュミスは生じ得る。
ということで、動的配列でMove動作が有効である例では、たとえ動的配列で
あっても、結局、キャッシュミスは生じる。

**デフォルトの名無しさん** · 2020/09/18(金) 03:33:15.49

ここまでベンチなんもないのでとりあえず適当に拾ったやつ
https://dzone.com/articles/performance-of-array-vs-linked-list-on-modern-comp

総データ量がキャッシュをはるかに超えるとかだと多分変わってくるんだとは思う
その場合でもUnrolled linked listとかを使うのがいいってことにはなるのかな？

**デフォルトの名無しさん** · 2020/09/18(金) 03:52:17.29

>>123
大体そういう人は、リンクリストの本質を理解できてないので、
「先頭から10番目の場所に挿入する」
などという馬鹿な書き方をしている。
例え博士課程とかの人でもそういう馬鹿な人がいる。

**デフォルトの名無しさん** · 2020/09/18(金) 03:53:47.62

推測するな、計測せよ

**デフォルトの名無しさん** · 2020/09/18(金) 03:54:10.38

>>124
C++のSTLは設計は馬鹿なので、先頭から k 番目に挿入するなど言う
馬鹿な統一関数がある。
それは、リンクリストにとって最悪の挿入法で、O(N)の時間が掛かる。
だから遅い。
数学的なイマジネーションが無いので、その間違いに気づかない。

**デフォルトの名無しさん** · 2020/09/18(金) 03:54:37.58

>>125
いくら測定しても、理屈が間違っていれば、間違った実験結果となる。

**デフォルトの名無しさん** · 2020/09/18(金) 03:56:20.84

>>125
グラフだけ書いて、ソースがない。
どうせ、k 番目に挿入すると言う馬鹿コードになっている。
いくら言っても、同じ間違いをする人が続出する。

**デフォルトの名無しさん** · 2020/09/18(金) 03:58:23.37

数学が出来ない人は、生まれつき脳が馬鹿なので、
この人も、乱数で番号を発生させて、先頭からk番目の位置に挿入する
という馬鹿なベンチマークを作って、リンクリストが遅いなどと言っている
のだろう。
そんなことすれば遅くなるに決まっているが、彼は馬鹿なので分からない。

**デフォルトの名無しさん** · 2020/09/18(金) 04:01:14.05

数学脳を持ってない人にヒントをかいておくと、
リンクリストは、途中への挿入は O(1)で可能だが、
先頭から k 番目という番号を指定した位置への挿入は、O(N)の時間が掛かる。
こういうベンチマークを取って論文にしてしまうような人は、
プログラミングもコンピュータサイエンスにも全く向いてない。

**デフォルトの名無しさん** · 2020/09/18(金) 04:04:00.76

アメリカの大学生の非常に多くのがポインタやアドレスの概念が理解できないらしい。
この人もそれに近い状態だから、途中への挿入を、先頭からの番号で指定すると言う
発想しか出来ないのだろう。
ポインタが何故頭のいい人に好まれるか、そういう人種の人にはわからない。
そして、間違ったベンチマークを大真面目に論文にしてしまう。

**デフォルトの名無しさん** · 2020/09/18(金) 06:34:01.52

>C++のSTLは設計は馬鹿なので、先頭から k 番目に挿入するなど言う
>馬鹿な統一関数がある
え？ここ見る限りそんなのないけど
https://cpprefjp.github.io/reference/list/list/insert.html

**デフォルトの名無しさん** · 2020/09/18(金) 08:12:28.71

DDRメモリのセットアップタイムをググったらcrucialが判りやすい資料を公開していた
ttps://www.crucial.jp/articles/about-memory/difference-between-speed-and-latency
これはメモリ単体での値だから実際にはCPU内キャッシュの探索時間、バスの調停時間
メモリコントローラの動作時間が積まれる。L3まで探って未ヒットだった場合CPUが3GHzとしても
30サイクル以上は待たされそう

今時のPCで使用されるプロセッサはL1からのロードですらノーウェイトではないし計画的なロードは超重要

**デフォルトの名無しさん** · 2020/09/18(金) 09:09:51.55

先頭や末尾への挿入削除だけならVecDequeでよくね

**デフォルトの名無しさん** · 2020/09/18(金) 09:26:18.23

>>123が参照してる記事でもっと詳細あったわ
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

こっちは、挿入が挿入箇所のサーチも加わったことを断った上で比較してますね
サーチを加えてもデータサイズがでかい・コンストラクタのコストが重い場合はlistが有利っすね

挿入位置のサーチの分のコストを含めるかは難しいところだけど、先頭・末尾以外の一定位置にだけ挿入するってシチュエーションはそうそうないだろうし、
この程度の比較でいいんじゃねーのかな

**デフォルトの名無しさん** · 2020/09/18(金) 09:34:00.68

>>132
イテレータであらかじめ挿入位置を探しておくんすよ
その操作はO(n)かかって、その後insertメンバ関数で挿入する

**デフォルトの名無しさん** · 2020/09/18(金) 09:59:55.15

実際には、挿入箇所のサーチなど必要無い事が多いので、リンクリストが速い。
テストする人は馬鹿なので、実際的な「ランダム」の意味が分かってない。

**デフォルトの名無しさん** · 2020/09/18(金) 10:03:14.54

>>135
>挿入位置のサーチの分のコストを含めるかは難しいところだけど、先頭・末尾以外の一定位置にだけ挿入するってシチュエーションはそうそうないだろうし、
>この程度の比較でいいんじゃねーのかな
違う。
サーチが必要なく、分かっている途中の場所に挿入するケースが圧倒的に多い。

**デフォルトの名無しさん** · 2020/09/18(金) 10:30:57.15

>>133
それはリンクリストだけの問題ではなく、>>122のように、動的配列でも
現実的には事情は変わらない事が多い。
動的配列は、要素のサイズが小さくて、Heap領域へのポインタなどを中に持ってない
場合のみ、リンクリストに勝てる。
たとえば、この条件に当てはまっている典型的な例として、文字列を文字の集合とみなした場合や、
3Dの頂点座標などは、(動的/固定)配列で持っているのは正しい判断で、リンクリストで
持つべきではない。
たとえば、要素がメンバとして、CStringやstd::stringなどの文字列を持つ構造体の場合は、
>>122の状況が生じるので、要素を配列で持ってもキャッシュミスは避けられない。

**デフォルトの名無しさん** · 2020/09/18(金) 10:40:12.02

STLの設計も悪いが、リンクリストに対するランダム挿入のテストで、
ランダムな整数kを求めて「k番目の要素」の直前に挿入するような
馬鹿なテストをしている場合、リンクリストは、先頭からk番目までを
丁寧に辿らなければならないので、その時にO(k)の時間がかかる。
全体の要素がN個の場合、このようなランダムの場合、平均でN/2に比例した時間が
掛かるのでO(N)と表現される。
しかもこのとき、要素をk個もたどらなければならないので、キャッシュミスがあったら
かなりの時間が掛かってしまう。
逆に、動的配列の場合は、先頭からkまでをたどったとしても、キャッシュミスは軽微。
しかし、現実の途中の挿入は、このような「辿る操作」が全く必要無い事が多いので、
リンクリストは速い。
要素を識別するために、先頭から「k番」という番号で行うのは、「配列流」で
あって、ポインタが理解できない人には、それしか方法が分からないが、リンクリストは
そのような方法で要素を識別しない。
そして、その識別方法こそが、リンクリストが配列よりも圧倒的に便利であることに繋がる。
ポインタはとても賢い方法なのだが、頭が悪い人には理解できないので、どうしても、
先頭からの番号でしか要素を識別したがらない。
そしてそのことこそが、あらゆることを遅くし、プログラムを見通しの悪いものにしている
ことにも気づかない。

**デフォルトの名無しさん** · 2020/09/18(金) 11:07:59.09

リンクリストをサーチする場合
１．次の要素のアドレスを取得
２．次の要素のメタデータを取得
３．データを評価
４．アンマッチだったら１に戻る
を繰り返すので、メモリ配置次第ではランダムアクセスになりやすく
無策だとキャッシュミスを発生させやすいって話じゃないの？

**デフォルトの名無しさん** · 2020/09/18(金) 12:20:02.02

>>141
でも、要素の中にstd::stringなどを入れていた場合、そのstringの中味は、
Heap領域を指しているので、どうせ動的配列でもキャッシュミスは生じる。
だから動的配列がサーチで有利になるのは要素がトリビアルな場合のみ。
また、サーチしても、削除などを行うととたんに動的配列は遅くなる。
この場合、O(N)個のCopyまたはMoveが生じる。Moveでも
コピー動作が全く生じないわけではないので(途中の)1個の要素の削除でも、
動的配列はO(N)の時間が掛かる。
一方、リンクリストは、O(1)。

読み取りが中心になる場合は、動的配列はもちろん速い。

**デフォルトの名無しさん** · 2020/09/18(金) 12:35:56.71

>>141
リンクリストをサーチするのは pure Cで書けばこんなに簡単で、物凄く効率が良い:
CNode *pNode = pTop;
while (pNode != NULL ) {
　(pNodeを検査);
　pNode = pNode->m_pNext;
}

**デフォルトの名無しさん** · 2020/09/18(金) 14:22:59.83

( ´,_ゝ｀)ﾌﾟｯ

**デフォルトの名無しさん** · 2020/09/18(金) 15:09:39.89

>>141
同じO(n)でもLocalityの違いでVecとLinkedListじゃ桁違いの差が出るよって話

「無策だと」って言っても現実的にLinkedListをVecと同じようにCache Friendlyにする方法ないよね？

**デフォルトの名無しさん** · 2020/09/18(金) 15:41:38.07

実際にテキストエディタでも作ってみれば、LinkedListの優秀さが分かる。
行数が大きくなった場合、動的配列では遅くてどうしようもない。

**デフォルトの名無しさん** · 2020/09/18(金) 16:53:33.12

なるほどね
テキストエディタという具体例があったか

**デフォルトの名無しさん** · 2020/09/18(金) 17:30:51.35

エディタの場合はO(n)の探索じゃ困るからLinkedListで作られてるメジャーなのないでしょ
Piece Table, Gap Buffer, RopeのいずれかでRope以外は基本的に配列を中心に実装されてる

VS Codeの例
https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation

Heap ManagerとかMemory Allocatorみたいなのは内部的にLinkedList使ってる

**デフォルトの名無しさん** · 2020/09/18(金) 18:36:08.52

>>148
>エディタの場合はO(n)の探索じゃ困るからLinkedListで作られてるメジャーなのないでしょ
「探索」とは何のことか知らないが、
「検索」に関しては、ArrayListでもLinkedListでもbig O表記は変わらないが。

**デフォルトの名無しさん** · 2020/09/18(金) 18:40:53.97

StackOverflowも、これに関してはデタラメ。
実測してLinkedListの挿入が遅いとした人のコード見てたら、
ノードの個数Nの値が、1から100までしかならないようになっていて、
それを、以下の様に外側から100000回くらいループした、二重ループになっていた。
for(100000回のループ) {
　リストの変数を作成
　for(100回挿入するループ) {
　}
}
これだと、LinkedListのNodeがHeapから作製される遅さばかりを測定しているだけで、
全く、LinkedListの真骨頂であるところのNが大きな時の挿入はテストできていない。
StackOverflowはとても高度なことを答えている人もいるが、この件に関しては、
レベルの低い人の書き込みが目立っている。あれを信じてはいけない。

**デフォルトの名無しさん** · 2020/09/18(金) 18:42:40.33

>>141がかなり素朴にキャッシュミスの話をしてくれてるのに
平然と>>143を返すあたりでもうコイツから得られる有益な情報は無いので解散

**デフォルトの名無しさん** · 2020/09/18(金) 18:49:50.54

>>151
LinkedListには、メタデータなんて無いから、話がそもそもかみ合わなかったので
初歩的な情報を提供したつもり。