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/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には、メタデータなんて無いから、話がそもそもかみ合わなかったので
初歩的な情報を提供したつもり。

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

Intelの最適化マニュアルを見ると、不規則なメモリアクセスで
ハードウェアプリフェッチが有効に機能しないシチュエーションでは
ソフトウェアプリフェッチが有効であると書いてある。つまり
>>141 ２．５　次アクセスするメモリに対しプリフェッチ出来る命令を実行する
みたいにすればメモリのランダムアクセスに起因するレイテンシを短縮できる

あとサーチの場合メモリ配置の局所性以外の要因でも配列とリンクリストの速度差は発生する
リンクリストの場合メモリ帯域の一部をアドレスのロードに取られるのでデータのロードに使える帯域は減少する
配列の場合はレジスタにおいたアドレスを使ってロードできるし
ストリング命令が使えるプロセッサであればサーチ命令を使用する事も出来る

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

Twitterによくいるトンチンカンな知識の割に
謎の上から目線で口上垂れてる同類だな

**108** · 2020/09/18(金) 21:29:14.35

Elixir では、リストへの全走査が主体。
フィルターとか

ランダムアクセスではない。
全探索が基本

全探索はリスト、ランダムアクセスは配列。
リストは、次の要素しか分からないから

「1, 2, 3, 4, 5」という要素があって、奇数だけをフィルタリングしたら、
「1 -> 3 -> 5」みたいに、リンクをつなぎ直す。
2, 4 はGC の対象になる

こういう全走査では、リストが圧倒的！

これが動的配列なら、2の削除で、345 を前に移動して、
4の削除で、5 を前に移動してと、コピーの連続になって大変

だから、Elixir では、リストが主体になっている。
関数型では状態を変えず、パイプラインで、新たな要素を作っていくのが基本

全走査が基本で、ランダムアクセスしないからだろう

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

>>153
次の要素のアドレスが把握できたタイミングから
そのアドレスにあるデータを利用するまでにプリフェッチが完了するような場合なら
微妙に速度が向上する可能性がないとは言わないが
それは>>135の記事にあるようなVecとLinkedListの比較で意味のある違いにはならないでしょ

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

>>148
>Piece Table, Gap Buffer, Ropeのいずれか
なにそれ面白そう

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

VS Codeの異常に早い検索はそれで実現されてるのか

**デフォルトの名無しさん** · 2020/09/19(土) 01:43:40.66

IteratorでItemがimpl Futureをしてる型を返すっていう実装したいんですが、方法が分かりません。
どのように解決すればよいのでしょうか？
while Some(fut) = fut_iter.next() {
let result = fut.await;
}

**デフォルトの名無しさん** · 2020/09/19(土) 02:11:22.63

>>154
数学が分からん人には、LinkedListの優秀性も理解できない。
実験しても実験の仕方が間違っているので間違った結果になっているが、
本人が気づかない。
C++のStrousstrup氏も間違っている。
集団幻想。
それだけ数学的なことは才能が必要だということだ。
多数決では、ArrayListが圧勝と言うことになってしまっているが、それは
本等は間違い。

**デフォルトの名無しさん** · 2020/09/19(土) 02:19:57.57

数学的なことは、99%位の人が正しく理解できないので、ベンチマークテスト
のプログラムも1%位の人しか正しくかけない。
だからデタラメな集団幻想が、LinkedListが過小評価に繋がっている。
まだ、雑誌などでは学歴フィルターというか、頭の良さフィルターをかけて入社
させない仕組みがあるので、あまり間違ってはないが、ネットはめちゃくちゃ。
見ていたら、論文にまでしてしまっているひとまでいるようだが、間違っている。

**デフォルトの名無しさん** · 2020/09/19(土) 02:23:16.42

>>95
グラフ表現とかでもlinkedlist使わんの？

**デフォルトの名無しさん** · 2020/09/19(土) 03:22:40.39

あーあっち側の人すかー
有意義な議論ができるかと思ってた
皆さまご苦労さまです

**デフォルトの名無しさん** · 2020/09/19(土) 11:06:03.78

とりあえずベンチマーク取ってみたらええやん。。よくいる種類の馬鹿だよね。
こういうタイプはフィボナッチヒープとか大好きなんだよな。

**デフォルトの名無しさん** · 2020/09/19(土) 11:36:48.27

ArrayListおじさんはArrayDequeをどう評価するの？

**デフォルトの名無しさん** · 2020/09/19(土) 12:38:52.28

>>162
グラフは何かしらのツリー構造を使うからLinkedListは使わないでしょ

**デフォルトの名無しさん** · 2020/09/19(土) 16:29:00.47

https://ideone.com/lH56m8
ArrayListとLinkedListを思いつくままに比較した。
結論は特に無し。

**デフォルトの名無しさん** · 2020/09/19(土) 16:47:45.15

https://ideone.com/O4aPii
sumi2 1,222,328 164,294,013 (1.000000:134.410742)
を追加。

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

まだ続くなら、動的配列とリストの具体的なベンチマークのコードを載せてくれ
rustが好ましい

**デフォルトの名無しさん** · 2020/09/19(土) 18:25:43.76

>>167
Javaでは、末尾追加の aitと、途中削除の rit、先頭への追加は、LinkedListの方が
速いという結果だね。
この場合、要素数が2万個だけど、もっと多くなると理論上、その差はいくらでも開いて行く。
また、単純に全要素を足すsumitとsumforでは、0.25%, 1.4% の差しかない。
逆に、末尾追加のalastは、ArrayListの方が4.8倍速い。
これはLinkedListの場合、1要素ずつメモリアロケーターを呼び出しているので遅くなっており、
予想通り。
しかし、先頭追加のa0とalastの時間差が、LinkedListではほとんどない(理論上は全くないのだが)
のに対し、ArrayListでは82倍もあるのも予想通りの結果。
LinkedListは、先頭、末尾、途中のどこを操作しても、理論上、時間差が(ほぼ)ないが、
ArrayListは、大きく違ってくるというのが理論上予想されたことで、このベンチマークは正しく
それを反映している。

**デフォルトの名無しさん** · 2020/09/19(土) 18:27:51.00

>>170
なお、末尾追加も、同じサイズのノードに限定したものなら、メモリアロケーターが
劇速のものが作れるので、LinkedListでも、ArrayListに匹敵するくらい速度が
出るように作れる。

**デフォルトの名無しさん** · 2020/09/19(土) 18:28:30.00

>>171
間違った。
匹敵どころか、要素数が多くなった場合、LinkedListが追い抜く。

**デフォルトの名無しさん** · 2020/09/19(土) 18:30:31.19

この結果は、JavaのLinkedListが、素直にLinkedListを素朴に実装しているから
出てきたもの。
一方、STLは、設計が悪いので初心者が誤解を招く結果が出てしまう。
それは、追加する場所をアドレスではなく、先頭からの通し番号で指定する
ことが標準になっていたりするから。

**デフォルトの名無しさん** · 2020/09/19(土) 18:48:41.03

>>173
> 先頭からの通し番号で指定することが標準になっていたりするから。

なんでそんな間違った前提を置いてるんだ？
C++ の std::list にそんな機能はないってことをたびたび指摘されてるが、
あんたは今までリンクリストの優位性がどうこう言ってたのとは別の人なんか？
(いや、そんなはずはないよな、こんな荒らし野郎が何人もいるとは思いたくない。)

**デフォルトの名無しさん** · 2020/09/19(土) 19:00:07.16

Javaはmalloc/freeが超速いので、他の言語よりはLinkedListに優しい

**デフォルトの名無しさん** · 2020/09/19(土) 19:14:15.33

>>175
どうせ妄想を書いてるだけだろ

**デフォルトの名無しさん** · 2020/09/19(土) 19:22:13.23

GC言語は領域の再利用をgc時に行うからnewの時に空きを探す手間が少ない。
単純に端っこから割り当てていくだけ。

**デフォルトの名無しさん** · 2020/09/19(土) 19:39:34.30

>>174
あ、記憶違いだったわ。
STLが汚すぎて。

**デフォルトの名無しさん** · 2020/09/19(土) 19:57:18.05

Listスレかな?

**デフォルトの名無しさん** · 2020/09/19(土) 23:26:19.32

https://ideone.com/NZEWm8
vectorとlistも比較した。
listのsumiとsumi2が小さすぎるので何か間違ってる予感。
全体的に古臭い書き方ですまそ。

**デフォルトの名無しさん** · 2020/09/19(土) 23:52:44.02

ゲームエンジン・データベースなどの本には、メモリプールを作る方法が、よく載っている

同じサイズの要素を、まとめて確保して、そのプール内で管理する方法

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

次はhashmap vs vector

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

ここで定番のRustハッシュ関数遅い問題で一悶着

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

>>167
実行順やJITの兼ね合いがあるから
ちゃんとやるならJMHで測ったほうがいいよ

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

>>181
システムコールの呼び出し回数を押さえるため？
でも通常のmalloc/freeもプロセス再起動されなければ領域再利用されるよね。
なら最初にmallocでガバっと取って、実際に使う時にfreeしてmallocしなおせば良くない？
ゲーム専用機の場合はシステムのAPIもいまいちだったりするから自前でメモリ管理もありだと思うし、DBの場合もキャッシュやら共有メモリやらmmapしてどうたらで自前で管理したいのもわかる。
でもそれ以外で普通のOS上のアプリで自前でメモリプール管理するメリットってどれだけあるの？

**デフォルトの名無しさん** · 2020/09/20(日) 01:12:40.58

予め決まったサイズを確保することが多いから、予めまとめて確保しておいて数珠繋ぎにしておけば最速で出し入れできる

**デフォルトの名無しさん** · 2020/09/20(日) 01:16:59.26

16msecの間にすべての処理を完了しないといけないからmalloc呼び出しなんてありえないよ

**デフォルトの名無しさん** · 2020/09/20(日) 01:29:40.54

>>167
このデータの作り方だとLinkedListでもかなり連続したメモリ領域が使われてる可能性が高いような気がする

Javaの場合はList<int>じゃなくList<Integer>で
値を使うケースだとポインタを辿る必要があるのでそれも結果に影響しそう

**デフォルトの名無しさん** · 2020/09/20(日) 03:23:18.11

>>159 に答えれる方いませんか？
ここはリスト議論のスレッドですか？

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

>>184
情報サンクス。
JMH勉強になりました。存在すら知らなかったです。

>>188
AutoboxingとUnboxingも大事なところで平然とやりまくってるので、
こちらもご指摘のとおり結果をぼやかしちゃってると思います。
LinkedListはなるべく不連続にリンクされたデータを準備してみよう！
という心意気は当初あったのですが、サボりましたｗ

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

挿入が必要なら普通はヒープ組むのになんで誰も突っ込まんの？

**デフォルトの名無しさん** · 2020/09/20(日) 10:27:51.76

テキストエディタのようなものだと、アプリを起動して編集し始めた時から、
新しく追加したデータに関しては、対応するノードは、Heapからアロケートしても、
連続したアドレスに載っている。
ロードした直後、最後の行のノードのアドレスと、編集で追加したノード
のアドレスが近い。
編集で追加した行の直前直後のノードのアドレスと、編集で追加したノードのアドレスは
不連続である。
しかし、キャッシュは、何も、最後の1つのページだけしか覚えておけないわけでなく、
1000種類位は覚えておける。
だから、このくらいだと、どちらもキャッシュに乗ることになる。

なお、ArrayListの場合、途中へ追加すると、半分近くの要素に対してコピー動作が
必要になるが、その際、キャッシュを全て使い切ってしまうことがある。
配列の全データが100MBだとすると、このコピー動作のために100MB分のデータが
いったんキャッシュに読み込まれる必要がある。
キャッシュはL3ですら8MB程度しかないので、これだと全くキャッシュが足りなくなる。
その点、LinkedListは、このようなキャッシュ汚染は生じない。

**デフォルトの名無しさん** · 2020/09/20(日) 10:32:00.78

>>192
さらに、100MBのようなデータだと、ArrayListで全データを巡る際でも、
キャッシュミスもキャッシュ汚染も生じる。
だから、ArrayListがキャッシュで有利と言っても、現実的には2MBくらいまで
がその優位性は維持できない。
そしてLinkedListも実際的な用途では、>>192に述べたような状況になるので、
キャッシュミスは余り生じない。

**デフォルトの名無しさん** · 2020/09/20(日) 10:48:59.50

>>193
テキストエディタの例だと、100万行のファイルを読み込んだとしても、
実際に閲覧したり、書き込んだりしたい場所は、数箇所に集中することが
多い。
LinkedListの場合だと、編集時に行を挿入する場合、全データを移動する
必要が無いので、1行当たり、数10バイトくらいのコピーで済む。
この場合、キャッシュ汚染はほとんど生じない。
一方、ArrayListだと、100万行のコピー動作が必要になり、その際に
キャッシュを浪費してしまう。