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/08/23(日) 10:31:18.31

Rustを学びたい人はまず最初に公式のThe Bookを読むこと
https://doc.rust-lang.org/book/

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

いちおつ

**デフォルトの名無しさん** · 2020/08/23(日) 13:15:25.53

最近は初学者向けの文書も充実してきてるね

Tour of Rust
https://tourofrust.com

Rust explained using easy English
https://github.com/Dhghomon/easy_rust

**デフォルトの名無しさん** · 2020/08/23(日) 15:24:56.55

http://zsiciarz.github.io/24daysofrust/index.html
今これ読んでる

**デフォルトの名無しさん** · 2020/08/24(月) 02:54:03.17

日本語でおけ

**デフォルトの名無しさん** · 2020/08/24(月) 03:09:08.38

web_sys使って意図的にHTML食わせてDOM操作とかしたいんだけどこれって出来ない？
https://docs.rs/web-sys/0.3.44/web_sys/

**デフォルトの名無しさん** · 2020/08/25(火) 22:04:20.93

>>7
rustからDOM叩くのはバインディングさえ用意すれば出来るけど"意図的にHTML食わせて"の意味がわからん。

**デフォルトの名無しさん** · 2020/08/26(水) 09:25:11.81

>>8
HTMLのテキストをDocument::from(&html_text)みたいに読ませて、そこからDOM操作してDOMのvalueとかattrとか読みたい。
他のHTMLパーサーは規格がバラバラだからweb_sys使いたい

**デフォルトの名無しさん** · 2020/08/26(水) 09:37:17.33

>>9
DOM操作なんかしないで、これ使おうぜ
https://github.com/tanakh/easy-scraper

**デフォルトの名無しさん** · 2020/08/26(水) 10:49:33.15

>>10
それkuchikiをそのまま使うのに比べてどういうメリットがあるの？
css selectorで指定できたほうが簡単で柔軟だと思うんだけど

>>9
HTMLパーサーの有名どころは、scraper, select, kuchikiの3つだけど
どれも内部的にservoのhtml5everを使ってるから一緒じゃない？

**デフォルトの名無しさん** · 2020/08/26(水) 14:28:06.12

easy-scraperは個人的に仕様がダサいと思う

>>11
web_sysのドキュメント見たら分かるけど、APIがかなり豊富でMDN遵守してるし、wasmにも移管できる。
その三つは楽だけどそれ以外はweb_sysの方が良いから

**デフォルトの名無しさん** · 2020/08/26(水) 15:34:22.88

>>12
wasmにも移管できるって、web-sysはwasm前提だと思うんだけどwasm以外で使えるの？

**デフォルトの名無しさん** · 2020/08/26(水) 17:13:59.22

>>12
ダサいといえばダサいんだが、綺麗さより楽さを取ったデザインって感じの話が作者のブログに書いてあったよ。

**デフォルトの名無しさん** · 2020/08/26(水) 21:28:36.70

>>9
whatwg DOMにDOM Level3 Load & Saveがないから今のDOMで外部ファイルのパースはできない。
適当なAPIでファイル読んでwasmにコンパイルした他のDOM Level3実装に食わせればいい。
rustで書かれたDOM Level3実装が見当たらないから他言語になるかな。

whatwgのDOMはesからhtml操作する以外は考えてないから、そういう事したいなら他でやるしかないね。

**デフォルトの名無しさん** · 2020/08/26(水) 22:06:03.86

綺麗に作れないから自分が楽な設計をしたというだけ
アラフォープログラマにありがちな言い訳

**デフォルトの名無しさん** · 2020/08/27(木) 02:24:33.81

無能の僻みかな

**デフォルトの名無しさん** · 2020/08/27(木) 03:10:08.73

>>16
「楽な」は「楽に使える」という意味だぞ。
綺麗な設計を捨てる方が作るのは大変に決まっとろうが……。

**デフォルトの名無しさん** · 2020/08/27(木) 04:23:21.10

>>13
ごめん、そこらへん認識甘いかも
wasmのランタイムじゃなくて、普通にrustcでも動くんじゃない？

>>15
そうなんだ、貴重な情報ありがとう。

**デフォルトの名無しさん** · 2020/08/27(木) 08:43:15.31

>>18
そう主張してるが本人が楽なだけ

**デフォルトの名無しさん** · 2020/08/28(金) 01:00:10.14

easy-scraperのブログみて試しにkuchikiでやってみたけどドキュメントがなさすぎてkichikuだった

次はscraperにする

**デフォルトの名無しさん** · 2020/08/28(金) 10:56:42.59

今月の新機能　Option::zip　の使いどころが分からない
こんなの要らないだろ
https://doc.rust-lang.org/stable/std/option/enum.Option.html#method.zip

**デフォルトの名無しさん** · 2020/08/28(金) 15:11:57.10

使うならOption版の論理演算とかかな

**デフォルトの名無しさん** · 2020/08/28(金) 23:01:39.34

the bookの分かりやすい更新履歴みたいのってある？

1度読み終わって以降に新しく追加された章や節がないかを確認したいんだけど
githubのcommitログ眺めていく以外の現実的な方法が見つからなくて困ってる

**デフォルトの名無しさん** · 2020/08/29(土) 00:41:53.30

>>22
cons cellにしてからflatするの面倒くさい。
俺はvec::Drainをas_sliceする用途がよくわからん。ただの変換用だろうか。

こっちの互換性残ってよかった。
ttps://github.com/rust-lang/rust/pull/74150/

**デフォルトの名無しさん** · 2020/08/29(土) 17:57:40.88

anyhowとthiserror 初めて知ったわ
std::Errorが便利になるまではこれ使っとけばよさそうだね

**デフォルトの名無しさん** · 2020/08/29(土) 22:59:59.85

とっくにfailureのフィードバック終わってるけど、ver古くない？

**デフォルトの名無しさん** · 2020/08/29(土) 23:02:55.48

結局今は何使うべきなの？
std::Error？　failure？　anyhow？

**デフォルトの名無しさん** · 2020/08/30(日) 03:03:14.91

@rustlangって日本語のRTもするのか
機械翻訳で読んだのかな

**デフォルトの名無しさん** · 2020/08/30(日) 11:07:07.53

いつになったらベンチマークStableにすんだよな

**デフォルトの名無しさん** · 2020/08/30(日) 18:03:13.46

ベアメタル用のコードを-C opt-level=0でコンパイルして乗算のオーバーフローチェック等のpanic機構って使用できる？
アセンブラリストを出力すると存在しないラベルの分岐命令が出力されるんだが正常な動作なのか・・・

31 · 2020/08/30(日) 18:53:07.92

例えばこんな感じ
ttps://uploader.purinka.work/src/17641.png
callqの行き先が不明

**デフォルトの名無しさん** · 2020/08/30(日) 19:51:29.80

--emit asmってlibcoreとリンクしたもの吐くの？
リンクされてないだけでここ呼んでるだけな気がする
https://github.com/rust-lang/rust/blob/1.46.0/src/libcore/panicking.rs#L39

**デフォルトの名無しさん** · 2020/08/30(日) 22:35:01.08

>>28
failureは役目を終えた。std::error::Error,thiserror,anyhowでfailure相当になる。
最近はenumxのcexで静的例外風にかけるけど。

>>31-33
panic_handlerを書いた覚えがないなら自分で書く。stdにはデフォルトの実装が用意されてる。
The Embedded Rust Bookに詳しく書いてあるから、rustupでローカルにダウンロードしてrustup docで開ける。

emitだとコンパイルまでしかしない。依存先すらコンパイルしてなかったと思う。

31 · 2020/08/30(日) 23:57:14.44

サンキュ

>>33
ビンゴだった。でも欲しいのはアセンブルリストなのでlibcoreを含むリストをどう入手するかが課題です
objdumpだと元のソースコードの行数等のデバッグ情報が失われるみたいだしグローバルの有無等の取得方法も判らないし
そもそもgasフォーマットじゃないから見方が判らないところがあるし

>>34
panic_handlerを自分で書きたいのはヤマヤマですが記述例が見つからず棚上げ状態です
ttps://rust-embedded.github.io/book/start/panicking.html
は見ていますが記述例は見あたりませんし

**デフォルトの名無しさん** · 2020/08/31(月) 08:19:34.04

ターミナル上で色つけるのとテキストポジションを決めたいだけの簡単なTUIアプリ作りたいんだけど、有名なTUIクレートが多くて迷ってます。
適切なクレートが何か分かる方教えてください。

**デフォルトの名無しさん** · 2020/08/31(月) 10:44:07.07

複雑なことしないなら termion

なんてどう？

**デフォルトの名無しさん** · 2020/08/31(月) 20:17:03.77

>>37
ありがとうございます。一度見てみます。

**デフォルトの名無しさん** · 2020/08/31(月) 22:50:36.76

>>35
英語読めないって話？
>A behavior can be chosen by declaring a #[panic_handler] function. This function must appear exactly once in the dependency graph of a program, and must have the following signature: fn(&PanicInfo) -> !, where PanicInfo is a struct containing information about the location of the panic.
>Given that embedded systems range from user facing to safety critical (cannot crash) there's no one size fits all panicking behavior but there are plenty of commonly used behaviors. These common behaviors have been packaged into crates that define the #[panic_handler] function. Some examples include:

**デフォルトの名無しさん** · 2020/09/01(火) 00:12:49.85

MirakurunクローンのmirakcってRustでかかれてるのか

ソースちょっとのぞいてみたけどサッパリだった

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

よく作れるよなあ

**デフォルトの名無しさん** · 2020/09/01(火) 00:23:01.46

>>35
記述例が見たいならそこからリンクされてるpanicハンドラクレートのソースを見ればいい。
例えばこれとか。

https://github.com/japaric/panic-abort/blob/master/src/lib.rs

**デフォルトの名無しさん** · 2020/09/02(水) 00:14:27.98

>>42
そうじゃなくて
>Given that embedded systems range from user facing to safety critical (cannot crash) there's no one size fits all panicking behavior
の意味がわからないんだろう。ベアメタルで人の書いたpanic handlerの中身なんて読んでも意味ないし。

31 · 2020/09/02(水) 08:06:57.73

>>42
それだと基本的に>>32と大差なく見えるというかリンク後に逆アセンブラリストを追いかけたら
最終的にfn panicへ制御が渡っている事を確認しています
>>34でpanic_handler書いていないみたいな事が書かれていたので別の書き方があるのかと・・

**デフォルトの名無しさん** · 2020/09/03(木) 00:54:39.65

Supporting Linux kernel development in Rust
https://lwn.net/SubscriberLink/829858/281103f9c6fd0dc2/

**デフォルトの名無しさん** · 2020/09/03(木) 13:59:41.08

お前らの考えとしてぶっちゃけどうよ？
今後10年でc/c++を凌駕する存在になり得るのかRustは

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

10年もありゃRustベースのもっといいやつが出てきそう

**デフォルトの名無しさん** · 2020/09/03(木) 14:28:37.24

Dはもう20年になるのか胸熱

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

C++ 30よりは普及するんじゃないか。
（30とかどんな魔境になってるんだろうか…）

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

Rust++もそこそこの魔境になるから大丈夫

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

折角Edition分けしてんだし、一部後方互換性をバッサリ捨てて冗長な表現を纏めて++回避したら流行りそう
なおロードマップ見渡してもその予定は一切御座いません(笑)

**デフォルトの名無しさん** · 2020/09/03(木) 21:15:25.18

Rustって未だにセルフホストできていない事に驚いた
標準添付のライブラリのビルドを試みたら
>error[E0554]: `#![feature]` may not be used on the stable release channel
等が大量に吐かれたｗ　要nightlyかよ

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

**デフォルトの名無しさん** · 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万行のコピー動作が必要になり、その際に
キャッシュを浪費してしまう。

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

L1,L2はkbyteオーダーだろ
余裕でキャッシュミスするわ

>>189
一言多いってよく言われないか？

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

>>195
>L1,L2はkbyteオーダーだろ
>余裕でキャッシュミスするわ
そこは、ArrayListで挿入する時の移動動作でもね。

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

なんでテキストエディタの例でArratListが出てくるんだ

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

スレ間違ってますよ

**デフォルトの名無しさん** · 2020/09/21(月) 04:23:45.31

>>195
すみません。
スレチ馬鹿が多いので言わないと分からないかと思い書いてしまいました。

**デフォルトの名無しさん** · 2020/09/22(火) 01:30:08.72

CSのスレでも立てればいいのにな
無駄なマウントとプライドで議論になってないじゃん