結局C++とRustってどっちが良いの？ 2traits

**デフォルトの名無しさん** · 2023/04/02(日) 00:42:57.53

「C++の色々配慮してめんどくさい感じは好きだけど、実務になったらメモリ安全性とか考えて今後Rustに変わっていくんかな」
「うだうだ言ってないで仕事で必要なのをやればいいんだよ、趣味なら好きなのやればいい」

っていうスレ。

前スレ: 結局C++とRustってどっちが良いの？
https://mevius.5ch.net/test/read.cgi/tech/1677286186/

**デフォルトの名無しさん** · 2023/04/26(水) 16:36:01.06

>>591
嘘か書かないで。

**デフォルトの名無しさん** · 2023/04/26(水) 16:37:03.22

591の人はイマジネーションが不足している。

**デフォルトの名無しさん** · 2023/04/26(水) 16:37:48.41

591の人を始め、ここの人には、図を書いて考えてみることをお勧めします。

**デフォルトの名無しさん** · 2023/04/26(水) 16:47:25.16

小学校の算数かよ

ごめん俺、小学校の算数躓いた勢だったわｗｗ
ちょっと算数系の学習障害はいってるんかもしれん

**デフォルトの名無しさん** · 2023/04/26(水) 16:48:15.43

月面着陸船が落っこちたそうだが
Rustで書いてれば成功したはず
それにしてもローバーは活躍出来ず流産乙

**デフォルトの名無しさん** · 2023/04/26(水) 17:01:55.60

>Rustで書いてれば成功したはず
↑この発想がそのまま↓なんだと言う自覚ゼロ
>コンパイラ通せば終わり（キリッ）っていうバカ

**デフォルトの名無しさん** · 2023/04/26(水) 17:17:57.85

>>600
嘘書かないで

**デフォルトの名無しさん** · 2023/04/26(水) 18:28:24.85

>>600
どこの場でも同じだけど
正しい指摘ができずに
嘘！違う！とだけ言い出したら
その人は負けなんですよ
>>591に書かれていること自体は正しいと思いますよ

**デフォルトの名無しさん** · 2023/04/26(水) 18:39:00.36

>>607
最後、頭の良さが無い人に教えることは不可能。キリが無いから。

**デフォルトの名無しさん** · 2023/04/26(水) 18:42:01.34

言葉ではなく、脳内に画像的なイメージを描かないと駄目ですよ。
全然それが出来てない。

**デフォルトの名無しさん** · 2023/04/26(水) 19:01:03.33

この人はvector内にガチのclassやstruct入れてるんだな

**デフォルトの名無しさん** · 2023/04/26(水) 19:04:57.37

>>596
便利だと思うのは自由だけど
頭から順番にイテレートしてから挿入・削除するような使い方だと
Cache Localityの違いによってVectorより性能が劣る

性能が重要ならLinkedListは挿入・削除時にイテレートが必要ないようにして使う
HashMapとLinkedListを組み合わせたLRUキャッシュとかね

**デフォルトの名無しさん** · 2023/04/26(水) 19:11:34.98

>>611
ヒープに要素があってvectorがキャッシュされない状態だと要素のメンバーの条件によって削除挿入するなら
vectorの方が不利だよね？
それは理解出来る？

**デフォルトの名無しさん** · 2023/04/26(水) 19:12:21.18

vectorが　は間違えて入ってる

**デフォルトの名無しさん** · 2023/04/26(水) 19:38:13.57

>>612
メモリキャッシュ自体はヒープもスタックも関係ないが
もちろんスタック上は常にキャッシュに載るから
上限値が決まっているならば全てスタック上に載せたほうが有利
ヒープは確保と解放のコストもかかるから大きく不利

そのためベクター型でもスタックを利用するものを使うとさらに速くなる
例えばRustはスタックをなるべく多用するために3種類のベクター型が使い分けられている
(1) ArrayVec は上限値を定めてスタックのみを使うベクター型
(2) SmallVec は上限値を定めてその範囲内ならスタックのみを使って超えたらヒープを使うベクター型
(3) Vec はヒープを使うベクター型
それぞれコストとわずかに特性が異なる

**デフォルトの名無しさん** · 2023/04/26(水) 20:22:03.82

https://ideone.com/hqXsfu
シャッフルされた数列を昇順にinsertした
{
std::vector<int> xs;
auto b = std::chrono::system_clock::now();
std::for_each(v.begin(), v.end(), [&xs](int x) {
auto pos = std::find_if(xs.begin(), xs.end(), [x](int y) { return x < y;});
xs.insert(pos, x);
});
auto e = std::chrono::system_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(e - b).count() << std::endl;
}
{
std::list<int> xs;
auto b = std::chrono::system_clock::now();
std::for_each(v.begin(), v.end(), [&xs](int x) {
auto pos = std::find_if(xs.begin(), xs.end(), [x](int y) { return x < y;});
xs.insert(pos, x);
});
auto e = std::chrono::system_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(e - b).count() << std::endl;
}

**デフォルトの名無しさん** · 2023/04/26(水) 20:41:37.78

>>614
イメージが違うな
シーケンシャルに要素が詰まってるんじゃなくてヒープに乱雑に詰まってる大きめの要素だとキャッシュに乗りにくいだろ
vectorはそのインデックス

**デフォルトの名無しさん** · 2023/04/26(水) 20:45:35.28

要素としてintが並んでるだけの実際にはないようなパターンの話をされても困るだろ
何らかのオブジェクトが大量にヒープのあちこちに詰まっててvaetorはそのポインタが入ってる

**デフォルトの名無しさん** · 2023/04/26(水) 20:47:03.66

前にrustスレをずっと荒らしてたおじいさんなのかな？

**デフォルトの名無しさん** · 2023/04/26(水) 20:51:22.56

>>616
大きなデータだとそういう二段階データ構造にする場合もあるというだけだろう
例えばソートは実体を移動させるよりもインデックスだけ移動させる新たなベクターを設ける
しかしその元の実体もベクターに格納したほうが有利なことが多い
ヒープに乱雑に格納するケースはかなり限られてくる

**デフォルトの名無しさん** · 2023/04/26(水) 20:56:32.56

>>615
実測いいね
リンクリストが遅い結果になるのは予想できたけど
ベクターの方が10倍以上も速いとは驚いた

**デフォルトの名無しさん** · 2023/04/26(水) 20:57:54.91

限られてはいないだろ
インサート、デリートを乱雑に繰り返して格納するケースだらけだろ

普通に要素数が分からないし、生成時期も分からないものを突っ込むことが多いんだから

**デフォルトの名無しさん** · 2023/04/26(水) 20:59:39.02

横から
>>610
何か問題でも?

**デフォルトの名無しさん** · 2023/04/26(水) 21:01:40.35

アプリ作ったことないの？

**デフォルトの名無しさん** · 2023/04/26(水) 21:01:40.98

>>621
vectorの方がインサートも速い
比較計測>>615の結果を見ろ

**デフォルトの名無しさん** · 2023/04/26(水) 21:02:25.41

>>624
intのvector比べて何になるんだよ

**デフォルトの名無しさん** · 2023/04/26(水) 21:03:19.22

intじゃなくて256byteぐらいのデータでやってみると逆転したり

**デフォルトの名無しさん** · 2023/04/26(水) 21:06:10.27

マンデルブロ画像の描画が速いと言ってるのと変わらない無意味な比較

**デフォルトの名無しさん** · 2023/04/26(水) 21:08:39.08

とても大きなデータならば
もう一つインデックス用vectorを用意すればよい
vectorのインサートは速いままだ

**デフォルトの名無しさん** · 2023/04/26(水) 21:32:20.97

>>615
リンクリストが唯一勝てそうなinsertまで敗北かよ
知らんかったわ
リンクリストの負けが確定だな

**デフォルトの名無しさん** · 2023/04/26(水) 21:39:12.36

データ構造の操作に限ればキャッシュにのるかのらんかで全然違うよな
まあ、リストでもスタック内で作ればいつものるけどね

**デフォルトの名無しさん** · 2023/04/26(水) 21:40:47.62

チョコチョコやっててもキリがないけどとりあえず少しだけ…
これ以上グズグズやってもうざいやろからこれで最後ね

>>626
> intじゃなくて256byteぐらいのデータでやってみると逆転したり
https://ideone.com/8p2nq0
struct foo {
int value, a[(256 / 4) - 1];
foo(int value) : value(value) {}
};
352　←ベクタ
296　←リスト
ちな128bytesだとまだベクタが速かった

>>617
> 何らかのオブジェクトが大量にヒープのあちこちに詰まっててvaetorはそのポインタが入ってる
https://ideone.com/8bwMkQ
上記の生ポインタ版。
53　←ベクタ
245　←リスト

**デフォルトの名無しさん** · 2023/04/26(水) 21:42:50.60

このスレを　リンクリストで抽出してレスしてる人を見ると1人を除いて多分ほぼ同じ人だと思うわ

**デフォルトの名無しさん** · 2023/04/26(水) 21:43:32.25

部分列が外から捕捉される場合があって、その場合はメインのリストから取り除かれて以降も長生きして欲しくて、それでRcRefCell使ってるという事情があるんだがなあ
そもそも目的は高速な反復処理じゃなくて状態の管理だし
>>581とかも勝手に途中のノードまでborrow_mut()して平気な顔してるし

まあそういう可能性を考えられない人は単純な構図にして勝ちを取るのに必死なんですね
ご自分の制作物にその知恵が生きるといいですね

**デフォルトの名無しさん** · 2023/04/26(水) 21:49:09.99

>>630
どちらもヒープで比較してるからスタックか否かは関係ない
linked listは本質的に遅い

**デフォルトの名無しさん** · 2023/04/26(水) 21:58:07.18

moveコンストラクタが働けばサイズ関係ないのでは?

**デフォルトの名無しさん** · 2023/04/26(水) 22:02:01.47

>>631
よく見たらコードへんじゃない？
linkedlistが不利になるだろそれｗ

**デフォルトの名無しさん** · 2023/04/26(水) 22:13:00.95

前提条件や用途を限定せずに性能議論しても無駄ではある
超長い配列に挿入したり探索したりが同時に発生する場合や
挿入順序維持して末尾に追加したいだけの場合はlinkedlist

**デフォルトの名無しさん** · 2023/04/26(水) 22:16:05.39

これで収束かな
おじいさん沈黙したから

**デフォルトの名無しさん** · 2023/04/26(水) 22:18:45.74

>>634
ベクタだとまとまってるからヒープでもキャッシュにのりやすくね？

**デフォルトの名無しさん** · 2023/04/26(水) 22:36:48.98

>>637
> 挿入順序維持して末尾に追加したいだけの場合はlinkedlist
https://ideone.com/6plvA3
172　←ベクタ(push_back(foo(i)))
107　←リスト(push_back(foo(i)))
74　←ベクタ(reserve(n), push_back(foo(i)))
64　←ベクタ(reserve(n), emplace_back(i))
105　←リスト(emplace_back(i))

こんな実測チマチマしてっても意味ないのは同意なのでもう寝ます
性能は状況状況に応じて各自が把握してたら十分と思います

**デフォルトの名無しさん** · 2023/04/26(水) 22:41:35.56

>>640
さっきのバグレベルのlinkedlistのコードは修正しないで寝るのか
残念

**デフォルトの名無しさん** · 2023/04/26(水) 22:46:15.95

のんびりまったりやれよ
Rust勢はめんどくさい、とか言われたいかｗ

C++は、テスト通りゃいいんだよまであるぜ
いろいろと自由だからねはよunsafe来いｗ

**デフォルトの名無しさん** · 2023/04/26(水) 22:55:15.76

>>636
あなたは間違ってるとか嘘とか言うだけで反論として正しいコードや正しい説明を出せたことがありません
そんなことをしていてはまわりから信頼を失いますよ

**デフォルトの名無しさん** · 2023/04/26(水) 23:11:23.22

順序維持の追加だけだと>>640のようにベクタもリストもイーブン
しかし追加するだけで終わるわけはなくそれを使うことになる
そうなると結局ベクタが有利

特定の使い方で両端から取り出して使うだけならリストが有利でないか？との疑問はあるだろう
しかしその場合もリストではなく両端キュー(double-ended queue)つまりC++ではstd::dequeueを使う
その内部実装は配列やベクタを利用となっている

**デフォルトの名無しさん** · 2023/04/26(水) 23:17:21.42

>>643
誰と勘違いしてるのか知らないけど俺は一度も嘘とか言ってないよ

コード見ればわかるけどlist使ってるほうは条件にあった場所で挿入しなくて
また無駄に頭から挿入位置までiterしてるように見えるでしょ？

おじいさんはコードも読めない

**デフォルトの名無しさん** · 2023/04/26(水) 23:39:33.42

>>633
borrowもborrow_mutもコストは同じだが二度のコストは避けたほうがいいんじゃないか
RefCellはスレッド内部専用だから並行して他のコードがborrowを試みるとこもないしあってはいけない
だからそこはborrow_mutのみで済ませてよい

**デフォルトの名無しさん** · 2023/04/26(水) 23:59:51.46

>>646
呼び出し元がずっとRef掴んでたら死ぬが

**デフォルトの名無しさん** · 2023/04/27(木) 00:07:20.74

>>647
つかまない実現コードがあれば教えて

**デフォルトの名無しさん** · 2023/04/27(木) 00:16:45.43

他人のことは初心者呼ばわりしておいて自分の見落としも初心者レベルじゃん
誰とは言わんがさすが

**デフォルトの名無しさん** · 2023/04/27(木) 00:29:02.36

>>647
Refはロックガードにすぎない
ブロックスコープを抜ければ自動解放
掴んだままになることはない

**デフォルトの名無しさん** · 2023/04/27(木) 05:33:00.85

>>647
関数から返すようなことさえしなければ、関数呼び出しが終わるとつかみ続けることはできず、解除される
RAIIを勉強しなさい

**デフォルトの名無しさん** · 2023/04/27(木) 06:57:25.28

>>645
vectorもlistもその部分は同じコードだぜ

**デフォルトの名無しさん** · 2023/04/27(木) 08:53:10.05

>>640
(cacheにヒットするかとは別に)cold memoryと言う状態があってbenchmarkの場合は気を付けてください

一応今回のコードでは影響はないと思われます
https://ideone.com/lP1xkO
vector::push_back: 192
256
list::push_back: 113
vector::push_back: 194
reserve, vector::push_back: 81
reserve, vector::emplace_back: 63
list::emplace_back: 111

**デフォルトの名無しさん** · 2023/04/27(木) 10:17:01.26

>>653
手元でやったらvectorの完勝だった(clang-O3)
それとRamMapのあと何回か試すとcold memory?の影響も出たする

list::emplace_back: 101
vector::push_back: 74
256
list::push_back: 102
vector::push_back: 57
reserve, vector::push_back: 15
reserve, vector::emplace_back: 15
list::emplace_back: 97

**デフォルトの名無しさん** · 2023/04/27(木) 11:18:48.87

int value, a[(256 / 4) - 1];
この配列aはcopyもmoveもないので計測には意味がないのでは?

**デフォルトの名無しさん** · 2023/04/27(木) 11:58:43.55

ランダムアクセスの性能が重要な状況で
頭からリニアにアクセスする時点で終わってる

**デフォルトの名無しさん** · 2023/04/27(木) 11:59:27.22

敢えてdefaultを明示しても特段の変化ないけど、違う話？
foo& operator= ( const foo & ) = default;
foo ( foo&& other) noexcept{
*this = other;
}

**デフォルトの名無しさん** · 2023/04/27(木) 12:18:28.50

vectorはcapacityが不十分なときにfooのcopy（move）を呼ぶ
fooのデフォルトのcopyもmoveも
aの要素をcopyもmoveもしないので
fooのメンバーにaがある意味がない

**デフォルトの名無しさん** · 2023/04/27(木) 12:33:19.96

>>658
C++に不慣れなRust使いさんですか？

fooもgooもmemcpyされてる
https://godbolt.org/z/xMxesqcss

>aの要素をcopyもmoveもしないので
これのソースは？

**デフォルトの名無しさん** · 2023/04/27(木) 13:29:59.90

>>659
あれ!? すまん
今の今までメンバーの配列は
デフォルトでcopyもmoveもしないのかと思ってた

**デフォルトの名無しさん** · 2023/04/27(木) 13:51:50.04

>>543
>>545
コンパイルしてみないとどれだけ容量食うか判らないのは可笑しいな
コンパイル前に今のcrates全部で3GB食うからそれ以上空けてないと
コンパイル開始しないで警告するようなオプション無いかな

**デフォルトの名無しさん** · 2023/04/27(木) 14:41:22.34

ポインタをちゃんと理解出来て無い人が、誤った使い方でLinkedListの性能
が悪いと思い込んでいるに一票。

**デフォルトの名無しさん** · 2023/04/27(木) 15:20:28.37

その件は、リニアでもランダムでも個別要素に総なめアクセスするだけの問題→vector+reserveサイズで悩むだけだな

それ以外の状況は千差万別だけど、データ構造を再発明してもしょうがない、知識をつけないとね
>>599みたいな状況→LRUCache→>>592のLinkedHashMap(listと配列のハイブリッド)みたいに

**デフォルトの名無しさん** · 2023/04/27(木) 16:24:47.29

>個別要素に総なめアクセスするだけの問題
なら、Arena方式がOKの場合としてstd::pmr::monotonic_buffer_resourceを使ってみた

vector::push_back: 53
256
vector::push_back: 52
reserve, vector::push_back: 15
reserve, vector::emplace_back: 15
list::push_back: 96
list::emplace_back: 94
list<foo,Arena>::push_back: 22
list<foo,Arena>::emplace_back: 22

**デフォルトの名無しさん** · 2023/04/27(木) 18:52:14.07

>vector+reserveサイズで悩む
見積を間違うとかえって遅くなるんだ(なんで?)
list+Arenaは使いどころがあるかもね

vector::push_back: 58
reserve, vector::push_back: 17 *
reserve, vector::emplace_back: 15 *
80% reserve, vector::push_back: 43 x
80% reserve, vector::emplace_back: 44 x
50% reserve, vector::push_back: 32
50% reserve, vector::emplace_back: 34
20% reserve, vector::push_back: 66 xx
20% reserve, vector::emplace_back: 66 xx
vector<foo,Arena>::push_back: 58
vector<foo,Arena>::emplace_back: 60
list::push_back: 94
list::emplace_back: 95
list<foo,Arena>::push_back: 22 *
list<foo,Arena>::emplace_back: 22 *

**デフォルトの名無しさん** · 2023/04/27(木) 19:26:23.25

個人的には思ってたより面白い展開だけど
Rustで手を動かして晒す人が出てくるまで
C++側は控えても良いんじゃないかな？

でないと>>604みたいなのが増えるだけや

**デフォルトの名無しさん** · 2023/04/27(木) 19:41:41.02

>>662
逆やろｗ
ポインタも知らず実測したこともない子が
listに対して過剰に期待寄せてるだけで
実際C++書いてるやつならもっと冷静よ

**デフォルトの名無しさん** · 2023/04/27(木) 22:08:12.11

データ構造の性能比べはスレ違いだからそろそろやめねえか

**デフォルトの名無しさん** · 2023/04/27(木) 22:18:15.37

データ追加の計測をしてるようだけど
実際にはその後にそれらデータを使うため
listは各ポインタをたどるところで不利になってしまう

vectorはreserve無しだと再配置コストがかかるけど
最大個数Mのときに再配置コスト累計はM～2Mで固定
使えば使うほど誤差になっていくので
パフォーマンスを気になるような使い方なら無視してよいかと

**デフォルトの名無しさん** · 2023/04/28(金) 00:29:13.98

ここの人達が馬鹿なのは、LinkedListだけ本来の使い方が出来てないこと。
ポインタの使い方が根本的に理解できてないことが分かる。

**デフォルトの名無しさん** · 2023/04/28(金) 00:39:40.76

vectorは、要素のラベルとしてindexを使うが、indexは初心者でも理解し易い。
ところが、LinkedListは、要素のラベルとしてポインタを使う。
ポインタを理解できない人は、いつまでもindexを使おうとする。
それでLinkedListの本来の性能が出ないので、LinkedListはvectorより遅い
と思い込むが、実際はその人の使い方が未熟だからに過ぎない。
多くはキャッシュのせいではなく、その人がまともに使いこなせて無い事が原因。

**デフォルトの名無しさん** · 2023/04/28(金) 00:45:03.56

どうして馬鹿な人に限って「キャッシュのせいで」というかといえば、
キャッシュは、ケースバイケースなので、優秀な人でも断定的に語ることが
できないから、馬鹿な人でも優秀な人と似たような状況になって、能力の差異を
ごまかすことが出来そうに思えてしまうから。
キャッシュは、事を行なう順序によって、本当に千差万別の状況が生まれるし、
CPUの世代によっても変わってきてしまうから、語るのが難しいものであるが、
それ故に、理解力が無いから語れない人も、「ごまかすチャンス」を与える
ことが可能となる誤魔化しのユートピアとなる。

**デフォルトの名無しさん** · 2023/04/28(金) 01:11:32.25

コードを出せないキチガイが連投

**デフォルトの名無しさん** · 2023/04/28(金) 01:28:17.16

>>671
>vectorは、要素のラベルとしてindexを使うが、indexは初心者でも理解し易い。
STLのalgorithmの関数群に渡すときはiteratorのみ

**デフォルトの名無しさん** · 2023/04/28(金) 01:28:26.76

>>673
なんでそんな面倒なことを俺がやらなきゃならないんだよ。

**デフォルトの名無しさん** · 2023/04/28(金) 01:34:03.77

率直に申し上げると
CとRustの相性は割と良いが
C++とRustの相性は良いとは
(特にテンプレ)言い切れない
即ちCからのリプレースに於いて
Rustが最適解に成り得るのに対し
C++はそのままC++で使い続けるが良かろう

**デフォルトの名無しさん** · 2023/04/28(金) 01:59:46.36

>>672
ケースバイケースじゃないですよ
cache hierarchyとcache localityという常識を学んでください
大昔ならいざ知らず今は大学1年生レベルでみんな習う常識ですよ

**デフォルトの名無しさん** · 2023/04/28(金) 02:05:44.40

>>677
キャッシュは、そういう問題じゃなく、前に何をやったかによって、
キャッシュに乗るかどうかが変わってくると言うことが起きることを
「ケースバイケース」と言っている。
だから、LinkedListにおいて、要素を交換するとしても、ソートの様に
ランダムに近い2つが交換した後のソート後の集合を先頭から最後まで巡る場合には
キャッシュミスが多くなるが、必ず隣り合う前後を交換することを２個おきにやった
場合の集合を最初から最後まで巡る場合は、キャッシュミスはほとんど起きない
という事情がある。
だから、LinkedListで要素を交換すると必ず遅い、というような法則は存在
しない。

**デフォルトの名無しさん** · 2023/04/28(金) 05:07:15.20

間違った使い方をしていると主張するならば
他の人たちのように実際にコードを示して
そして比較計測することで実証しよう

**デフォルトの名無しさん** · 2023/04/28(金) 07:29:21.75

>>678
>キャッシュは、そういう問題じゃなく、前に何をやったかによって、
>キャッシュに乗るかどうかが変わってくると言うことが起きることを
>「ケースバイケース」と言っている。
君がそう思って書いてるのはわかってるよ
それが的外れだから勉強したほうがいいよと言ってるんだよ

> 必ず隣り合う前後を交換することを２個おきにやった場合の集合を最初から最後まで巡る場合
この処理がvectorより速くなるとでも？
遅い速いは相対的なものなんだから何と比べてるかくらいはわかるでしょ？

**デフォルトの名無しさん** · 2023/04/28(金) 08:50:10.99

Rustはグラフ的な構造が作れないから
単純な構造しか扱わないシステムプログラミングにはC++より
優れてると思う

**デフォルトの名無しさん** · 2023/04/28(金) 09:06:54.24

キチガイ
的外れ
初心者

このあたりも頻出ワード

**デフォルトの名無しさん** · 2023/04/28(金) 09:39:41.22

>>681
そのへんはどの言語も同じ
作れないとか優劣とかない
言語よりアルゴリズムの差が大きい

**デフォルトの名無しさん** · 2023/04/28(金) 10:57:08.12

Rustは、要素のラベルとしてindexを使うが、indexは初心者でも理解し易い。
ところが、C++は、要素のラベルとしてpointerを使う。
pointerを理解できない人は、いつまでもindexを使おうとする。
それでC++の本来の性能が出ないので、C++はRustよりunsafe
と思い込むが、実際はその人の使い方が未熟だからに過ぎない。
多くはC++のせいではなく、その人がまともに使いこなせて無い事が原因。

**デフォルトの名無しさん** · 2023/04/28(金) 12:02:14.73

こういう人は、「汗をかく人」違った意味で論外＞＜

**デフォルトの名無しさん** · 2023/04/28(金) 12:39:05.67

>>671
vectorの使い方すら知らないのかよ
プログラムを書いたことがないんだな
次の要素や前の要素を指すにはindexを増減させるのではなく
イテレータを使いポインタでアクセスだ
次の要素を指すには++で要素の大きさ分が加算されるだけなので速い

**デフォルトの名無しさん** · 2023/04/28(金) 12:52:16.57

>>678
linked listのワーストケースはその通りキャッシュが効かず順にたどるのも遅くなる
そこまでわかっているならvectorが速いことも理解できるだろ

**デフォルトの名無しさん** · 2023/04/28(金) 12:54:59.10

>680
>> 必ず隣り合う前後を交換することを２個おきにやった場合の集合を最初から最後まで巡る場合
>この処理がvectorより速くなるとでも？
>遅い速いは相対的なものなんだから何と比べてるかくらいはわかるでしょ？
>686
>イテレータを使いポインタでアクセスだ

コードを晒すのはやめるけど、カスタムリストのポインタ操作で実装したらリストの方が速かった
sizeof(foo)= 256 back swap
std::vector, swap(xs[i],xs[i+1]) 55 15
std::vector, swap(*it1,*it2) 54 15
std::list, swap(*it1,*it2) 22 15
LinkList, modify prev/next 22 4

**デフォルトの名無しさん** · 2023/04/28(金) 13:04:21.51

backは末尾追加(push_backでもemplace_backでも同じ)
swapは>>678が言っている「必ず隣り合う前後を交換することを２個おきにやった場合の集合を最初から最後まで巡る場合」

試してみたら言っている通りだったけど、256バイトなのが効いている結果だと思う
それとstd::listはポインタ操作をやらせてくれなのかな？

**デフォルトの名無しさん** · 2023/04/28(金) 13:12:38.01

デカいものはそのようなそれ自体を動かすことはしない
例えばソートする場合でもポインタもしくはインデックスだけをソートする

**デフォルトの名無しさん** · 2023/04/28(金) 14:35:42.23

今はmoveコン実装しとけばデカくても関係ない

**デフォルトの名無しさん** · 2023/04/28(金) 16:30:32.81

それはポインタ格納だな

**デフォルトの名無しさん** · 2023/04/28(金) 16:54:55.41

いやポインタじゃなくインスタンス格納だよ

**デフォルトの名無しさん** · 2023/04/28(金) 17:25:35.41

ポインタのインスタンス、だろ。リリースビルドではポインタだけになってるかもしれないけど。

**デフォルトの名無しさん** · 2023/04/28(金) 18:50:51.20

そのvectorに格納している要素が大きな実体なのかそこへのポインタ(アドレス)なのかを理解していないとまずいぜ
要素がポインタを含めて小さい実体ならばvectorの要素の入れ替え・挿入・削除は非常に速い

**デフォルトの名無しさん** · 2023/04/28(金) 19:02:15.28

一斉シフトが起きる形の挿入削除をしないならば実体をそのまま格納が有利

**デフォルトの名無しさん** · 2023/04/28(金) 19:07:38.08

scanは先頭からvalue(int 4Byte)にアクセスしてダミーXOR演算する処理
dual link listのポインタ操作版(LinkList)はswapした後のscanが256Byteで激落ちだった xx
ForwardLinkListはforward linkかつallocate時のnextを別途キープし続けるデータ構造

sizeof(foo)= 256 n=1000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 52.986 3.461 14.739 3.458 74.644
std::list, swap(*it1,*it2) 22.574 6.470 16.252 6.375 51.672
LinkList, modify prev/next 21.940 6.509 4.229 39.717 72.395 xx
ForwardLinkList, modify next 22.824 6.532 4.395 5.861 39.611 *

sizeof(foo)= 128 n=2000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 60.411 6.789 14.340 7.144 88.683
std::list, swap(*it1,*it2) 28.981 13.839 16.871 14.124 73.815
LinkList, modify prev/next 27.969 13.845 10.074 16.062 67.951 *
ForwardLinkList, modify next 28.204 13.980 9.802 13.791 65.778 *

sizeof(foo)= 64 n=4000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 62.683 7.733 14.140 7.768 92.325
std::list, swap(*it1,*it2) 35.496 14.177 18.950 14.136 82.759 *
LinkList, modify prev/next 32.240 14.129 19.082 14.404 79.856 *
ForwardLinkList, modify next 33.547 14.197 19.169 13.922 80.835 *

sizeof(foo)= 32 n=8000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 61.452 8.084 14.104 8.230 91.870 *
std::list, swap(*it1,*it2) 51.176 17.195 22.936 17.336 108.643
LinkList, modify prev/next 47.231 17.226 23.422 17.519 105.398
ForwardLinkList, modify next 48.123 17.387 23.529 17.408 106.447

**デフォルトの名無しさん** · 2023/04/28(金) 19:11:25.99

C++側としては面白がって人の作ったベースを弄り始めたんだけれど、
sortしたり途中挿入削除しないリニアアクセスだけの問題ならどっちでも良いなw

ただし要素が小さくて途中挿入削除しないのならvector

sizeof(foo)= 16 n=16000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 61.891 9.511 13.994 9.677 95.074 **
std::list, swap(*it1,*it2) 90.948 22.966 34.215 23.463 171.592
LinkList, modify prev/next 76.692 22.989 32.457 23.262 155.400
ForwardLinkList, modify next 76.857 23.095 31.426 23.639 155.018

sizeof(foo)= 8 n=32000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 63.911 9.002 14.222 8.933 96.068 ***
std::list, swap(*it1,*it2) 171.875 52.681 71.011 43.465 339.032
LinkList, modify prev/next 142.104 39.655 52.617 40.589 274.964
ForwardLinkList, modify next 141.527 39.843 49.236 39.779 270.385

>>696に同意です

**デフォルトの名無しさん** · 2023/04/28(金) 19:16:02.37

だからmoveコン実装しとけばコピーは発生せんよ