- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 477 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 18:50:25.63 ID:Izo/gJUY.net]
- >>466
あなたはやはり馬鹿だな。
それをいうなら、配列も同じ。
配列の添え字番号を覚えておくのに、別の配列が必要になる。
お分かりかな？
あなたは、双対を全く理解出来て無い。
- 478 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 18:53:09.31 ID:uSmUEadq.net]
- >>465
それってリンクリストの意味ある？
なんのためにリンクリストにするんだ？
- 479 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 18:57:11.39 ID:pGvlrRKC.net]
- Linked Listを使っているのにLinkを辿りたくないらしい
- 480 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 18:58:57.15 ID:uSmUEadq.net]
- アドレス保持してればなんでもランダムアクセスできるっていうなら
あらゆるデータ構造がランダムアクセス性を持つということになってしまうな
- 481 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:16:56.34 ID:/zln3poJ.net]
- >>466
Qちゃんお疲れ
> あなたはリンクリスト以外の何か別のデータ構造を使って
> リンクリストのアドレスを管理しようとしているようですが、
> ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
それは色んな人がわりと最初のころから既にツッコミ済みなのだよ…
ようやく議論に追いついたねキミは
- 482 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:42:21.78 ID:1e4/tv+M.net]
- >>470
実際、C言語などから高級言語にポインタの概念が入ってからはそうなった。
ただ、Rustはそうなって無いから問題なんだよ。
- 483 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:42:59.18 ID:ZOlCZyFx.net]
- >>462
ポインタの指す領域に1クロックでアクセスできるCPUなんてあるんですか？
ポインタの指す先がメモリにあるかキャッシュにあるかで異なりますがL1キャッシュにあっても数クロックかかるのではないかと思います
数クロックを争うような話をするなら実装がないと話にならないと思うので、まずは比較したい書く言語の実装を用意しましょうよ
既存のコードへのリンクで良いので
- 484 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:43:39.06 ID:1e4/tv+M.net]
- やっぱり、数学が出来ない人は、双対の概念に脳が追いついてこないらしい。
双対という言葉の意味が分からなくても、生まれつき頭のいい人なら、
俺の言っている意味がわかるはずだ。
- 485 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:44:13.37 ID:1e4/tv+M.net]
- >>473
キャッシュに載っていたらの話だ。
- 486 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:44:50.23 ID:ZOlCZyFx.net]
- >>472
任意のアドレスへのアクセスは本質的にunsafeだと思うのですが、safe rustでそれができないことにどのような問題があるのですか
- 487 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 19:45:41.68 ID:ZOlCZyFx.net]
- >>475
リンクリストは参照局所性が悪いのでキャッシュに載っていない確率が大きいのですが、本当に高速なのですか？
- 488 名前：ハノン mailto:sage [2021/11/28(日) 19:59:16.91 ID:DhOI6JvL.net]
- >>474
双対性にもいろいろありますよね…論理学上の双対命題（∩と∪、∀と∃の入れ替え）ならばその否定が証明できますが、そういう意味ですか？
それとも正十二面体と正二十面体の双対性ですか？
適当にペアにして双対と呼んでいるだけなのでは？
- 489 名前：ハノン mailto:sage [2021/11/28(日) 20:01:48.12 ID:DhOI6JvL.net]
- >>471
そうなんですね…
- 490 名前：ハノン mailto:sage [2021/11/28(日) 20:10:07.08 ID:DhOI6JvL.net]
- >>473
いや、突っ込みどころはそこではなくて、
「あるときは O(f) ランダウのオミクロンで話をしたかと思うと、次の瞬間、クロック数を問題にする」というバラバラな論理展開でしょう
ランダウでやるんだったら最後までランダウで統一してほしいのですが…
- 491 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 20:33:56.21 ID:tN4i8A7m.net]
- >>480
ランダウ記号は、大まかな分類しか示せない。例えば、
O(N)は、N→∞ の時に、
O(N)/N < α (alpha)
のように有る正の実数αによって、「抑えられる」という意味しか示せないし、
O(1) < α (alpha)
であることしか意味しない。
だから、O(1)であることよりも、1クロックであることの方がずっと意味が強い。
なので、ちゃんと1クロックであると分かっているなら1クロックと書いた方がいい。
- 492 名前：ハノン mailto:sage [2021/11/28(日) 20:51:47.55 ID:DhOI6JvL.net]
- >>481
ある数量に対応する空間的・時間的コストの依存状況を滔々と語っていたかと思うと、次の瞬間は実時間に関する話に都合のいいように鞍替えするのは論理的でない、といっているのです
実時間なら実時間、依存関係なら依存関係できっちり話をわけてほしいですね
- 493 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 20:59:23.99 ID:tN4i8A7m.net]
- >>482
悪いが、お前が馬鹿なだけだ。
数学的には、O(1)と書くこともあれば、実クロックで書くこともあり、
混ぜたらいけないなんてことは無い。
ちゃんと理解していれば、混ぜても問題ない。
- 494 名前：ハノン mailto:sage [2021/11/28(日) 21:06:52.79 ID:DhOI6JvL.net]
- >>483
「数学的」の定義を伺いたいものですが、それはさておき、実クロックなんて「おま環」な話をしても仕方がない場合も多いのですよ
今はキャッシュのヒット率で処理速度も大きく変わるから、実クロックによる考察なんてほとんど無意味です
しかしデータ数等の「ある数量」に対する時間的・空間的コストの評価ならば、それは、どの環境にもっていっても通用する、すなわち適用範囲が広いのです
何か評価をしたいのなら、広い環境で通用する評価方法の方が有用でしょう
あなたは、その二つの評価方法の意義の違い（「どちらが有意義か」）を知らないから「混ぜたらいけないなんてことはない」などとシレっといえるのですよ
- 495 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:14:34.22 ID:tN4i8A7m.net]
- >>484
そうじゃないんだ。実際のクロック数の事ではなくて、マシン語で書いたときに
1命令だということなんだ。
- 496 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:17:54.80 ID:tN4i8A7m.net]
- キャッシュの話なんかは状況が複雑すぎて議論を複雑にするだけで、本質を理解する
邪魔になる。
まず、それは横に置いておいて、基本を理解しないといけない。
キャッシュの影響についてはその次。
また、なら、最初から「1命令」と書いておけば良かったのに、という突っ込み
が予想されるが、1命令でも乗算命令なんかは13クロック(レイテンシ)以上かかるから
それとは区別するために1クロックと書いた。
キャッシュは複雑すぎて話が混乱するだけ。
ポインタを介してのアクセスが1〜2クロックなのは、今のx86系だとアーキテクチャに
依存せず必ず言えることだから、そう書いた。
- 497 名前：ハノン mailto:sage [2021/11/28(日) 21:20:07.26 ID:DhOI6JvL.net]
- >>485
命令数なんてもっと当てにならないですよ、内部で別形態に変換され並列に実行されたりするわけで、人手で最適化することは不可能なしろもの
そんな制御できないものを評価対象にしてもしかたがないのでは？
- 498 名前：ハノン mailto:sage [2021/11/28(日) 21:25:24.33 ID:DhOI6JvL.net]
- >>486
＞ポインタを介してのアクセスが1〜2クロックなのは、今のx86系だとアーキテクチャに
＞依存せず必ず言えることだから、そう書いた。
残念ですがキャッシュにヒットするかしないかで大きく実行時間は変わりますね、キャッシュにヒットせず、RAM 空間上から引っ張ってくる場合は数十クロックは必要でしょうね…
そんな「お前の環境でしか通用しない話だろう」的な曖昧な評価方法よりも、どの環境でも通用するランダウのO記号による評価の方が有意義でしょう
どちらの方が有効範囲が広い有意義な評価法なのかを知らないから、ちゃんぽんにして話をしても不自然さを感じないじゃないですか、あなたは？
- 499 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:26:27.36 ID:tN4i8A7m.net]
- >>487
そうでなくて、Rustでも、O(1)というものだけなら、作ろうと思えば作れるから
1クロックと書かざるを得なくなったんだよ。
Rustの場合は、O(1)でも、単なるポインタでは無く、配列を介すので、
乗算、足し算、境界チェックが入ってしまうのでトータルで20〜50クロック
くらい掛かる。このうち、境界チェックだけは外せるかも知れないが。
- 500 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:27:53.03 ID:tN4i8A7m.net]
- >>488
>>489 を見ろ。
「なぜあなたは文脈を考えて書かないんだ」
と はちみつ餃子にも指摘されてただろ。
- 501 名前：ハノン mailto:sage [2021/11/28(日) 21:30:30.36 ID:DhOI6JvL.net]
- >>489
＞乗算、足し算、境界チェックが入ってしまう
C/C++ の配列とても乗算・足し算は入りますよ…
そんな瑣末な話とO(1), O(N) の話をちゃんぽんにしても不自然さを感じない感性に私は大いに疑問を感じます
- 502 名前：ハノン mailto:sage [2021/11/28(日) 21:34:48.65 ID:DhOI6JvL.net]
- >>490
よくご存知ですね…
まあ、今日は基本的なデータ構造を基本的な言語を使用して白紙からコーディングする機会を下さったあなたには感謝してますよ、久々に脳細胞を使ったのでちょっといい気分です
- 503 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:40:43.94 ID:tN4i8A7m.net]
- Cの場合のリンクリストのポインタを介してのアクセスは、
mov ebx,ptr
mov eax,[ebx]
ので済む。配列の場合は、
mov ebx,index ;添え字番号
mov eax,[ebp+ebx+32] ;32はスタックの中での位置
だから、配列とポインタで速度が変わらない。むしろこの例だとリンクリスト
の方が僅かに速いくらい。
Rustの場合、借用規則で禁止されてしまうため、以下のようになってしまう。
このスレである人が実装を示した独自Cursorをrustcでマシン語に直したものを
アセンブリ言語で書いた場合、次のように成る:
mov ebx,pseudo_ptr ;Cursorの中味はポインタの変わりに配列の番号になってしまう。
cmp ebx,配列要素数 ;safeモードの配列の境界チェック(これと次の命令はオプションで外せるかも)
jae 境界チェックエラーのラベル ;条件ジャンプ命令は遅くなる原因になりやすい。
imul ebx,要素のバイト数 ;13〜35クロック位。CPUによってこの限りではない。
add ebx,配列の先頭アドレス ;Cursorの実装の内部で用いられていた配列の先頭アドレス
mov eax,[ebx] ;間接アドレッシングによって実際にアドレスebxにアクセスする。
これは、O(1)ではあるが、20〜50クロック位かかり、先に示したCの場合とは
雲泥の差である。
- 504 名前：デフォルトの名無しさん [2021/11/28(日) 21:42:26.92 ID:8j2GjV45.net]
- 俺は Rust 書けない C++ マンだけど、双方向リンクリストのサンプルコードを書いてみた。
Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
リストの要素数に関わらず insert, remove 操作を固定計算量で実行可能であればそれは O(1) です。
https://wandbox.org/permlink/AHWR4LIjkMCvWuZE
insert, remove 実装のコードだけここに貼ります。全てのコードは上記で確認願います。
--------------------------------
node *insert(node *target, int value) // ノードを target の直後へ挿入
{
node *n = new node;
n->value = value;
n->prev = target;
n->next = (target != nullptr) ? target->next : nullptr;
if (n->prev != nullptr) n->prev->next = n;
if (n->next != nullptr) n->next->prev = n;
if (head == nullptr) head = n;
if (tail == target) tail = n;
return n;
}
void remove(node *n) // 指定ノードを削除
{
if (n->next != nullptr) n->next->prev = n->prev;
if (n->prev != nullptr) n->prev->next = n->next;
delete n;
}
- 505 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:43:21.57 ID:tN4i8A7m.net]
- >>491
お前はアホか。
リンクリストの場合は、乗算が入らないんだよ。
>>493
ミス訂正:
配列の場合は、
mov ebx,index ;添え字番号
imul ebx,配列のバイト数
mov eax,[ebp+ebx+32] ;32はスタックの中での位置
従って、リンクリストの方が一般的にはアクセスが速い。
リンクリストは、1クロック位、配列の場合は、要素が一般のバイト数の場合は、
14〜36クロック位。
- 506 名前：デフォルトの名無しさん [2021/11/28(日) 21:47:47.53 ID:tN4i8A7m.net]
- >>494
>Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
そうじゃない。
Rustでも、insert, remove 自体は、標準実装でも O(1)で行える。
ところが、アクセスが、標準実装では、借用規則のために複数の
読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
辿る必要があるため、O(N)かかる。
特殊な独自実装をすると、アクセスがオーダー的にはO(1)で出来るが、
特殊実装な故に、>>493 の後半のようになってしまい、
20〜50クロック位かかる。
- 507 名前：ハノン mailto:sage [2021/11/28(日) 21:49:24.66 ID:DhOI6JvL.net]
- >>494
読みました
私の場合は双方向リストを循環させ、始点のみをポイントすることとしましたが、結果として記述はあまり簡単にはならなかったですね、うーむ
- 508 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:56:03.25 ID:tN4i8A7m.net]
- すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
- 509 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:56:11.42 ID:tN4i8A7m.net]
- すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
- 510 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 21:56:13.54 ID:tN4i8A7m.net]
- すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
- 511 名前：デフォルトの名無しさん [2021/11/28(日) 21:57:51.47 ID:8j2GjV45.net]
- remove メソッドにバグがあった (head, tail を更新していなかった) ので一応修正。
https://wandbox.org/permlink/GlDCsezlcix3aJvi
>>496
なるほど。アクセス時に通し番号的な物が必要になるのであれば
insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
>>497
双方向リンクリストは始点と終了をペアで持つという固定観念があったので、その発想はなかったです。
- 512 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:02:54.87 ID:tN4i8A7m.net]
- >>501
>なるほど。アクセス時に通し番号的な物が必要になるのであれば
>insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
先頭や末尾では無い途中のinsert、removeであれば、あなたの言うとおり。
追加する直前のノードにたどり付くまでに一般的にはO(N)の時間が掛かる。
ただまあ、末尾追加や先頭追加と、末尾削除、先頭削除なら、RustでもO(1)で
出来るだろう。
なお、Cursorを使えば、よくあるケースだけは高速に行えるようになっているかも知れないが。
あくまでも良くあるケースだけは、unsafeを使って特別対応しているだけ。
複雑な一般的なケースでは、やはり、O(N)かかってしまう。
その意味で、あなたの言っていることは正しい。
- 513 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:13:58.18 ID:uBLcCIA8.net]
- いつまで例のVecを使った謎LinkedList実装にこだわっているのだろう
- 514 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:17:12.75 ID:tN4i8A7m.net]
- >>503
こだわっているというか、あれは、オーダー的にはCと同じく、ほとんど全ての
動作をO(1)で出来てしまうリンクトリストをRustでも出来ているから、
注目に値する。
ただし、O(1)と言っても、実際には遅い。
また、Read After Delete、ダングリングポインタに相当するものがRustでも
生じる。たとえ、safeモードで書いても。
- 515 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:20:39.78 ID:qezuw3R9.net]
- なんでRustだけsafe前提なんすか？
- 516 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:21:32.31 ID:uBLcCIA8.net]
- >>504
要素追加でバッファ超えると配列全体をコピーするけどO(1)なんだ？
いいのかそれで？
- 517 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:26:36.40 ID:tN4i8A7m.net]
- >>505
Rustはそれを売りにしてるからだよ。
C/C++は最初から諦めてる。
>>506
その指摘は正しい。
平均的にはO(1)だが、スパイク状に(不定期に)O(N)のコピー動作が入ってしまう。
- 518 名前：ハノン mailto:sage [2021/11/28(日) 22:29:15.25 ID:DhOI6JvL.net]
- >>501
私のやり方でよかったことは、prev/next の無矛盾性のチェックが簡単に書けることくらいでした、他は複雑になってしまった…
- 519 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:50:50.98 ID:qezuw3R9.net]
- >>507
売りにしてるいうても結構厳しい制限だからデータ構造に直結するようなコードはsafeのみじゃ無茶だぞ
連結リストのようにユーザ側もダングリングとか多重参照とか気をつけなきゃいけないタイプのものは、
safeの範囲じゃ回りくどいことやるハメになるか、そもそも本当に無理になるかだ
- 520 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:53:17.54 ID:Z9Xk/5kf.net]
- >>496
>ところが、アクセスが、標準実装では、借用規則のために複数の
>読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
>先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
>辿る必要があるため、O(N)かかる。
そうなんだ
でもこれってC/C++でもメモリ安全で、スレッドセーフとかにしたら同じにならん？
- 521 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 22:59:54.62 ID:hrke4Ba5.net]
- 自分はがんばって数学の勉強をしてきたので自分の考えは絶対に正しい、間違うはずがないと思いこむ。
そうなると一度間違った考え(リンクドリストの任意の要素にO(1)でアクセスできる)を持ってもそれを間違った考えとは気づかずにその間違いを補強するようなチグハグな考え方をするようになる。
反ワクチンのようなトンデモ科学にはまっちゃう人に周囲の人がいくら正しい科学知識で説得しても自分の考えに疑問を持つどころか、自分の考えは絶対に正しい、周りのやつらは頭がおかしいと思いこんでしまう。
自分の考えが間違うこともあるのではないかと謙虚になることも重要だということだね。
- 522 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:00:17.08 ID:j8Nrs0jp.net]
- まずポインタで持てば1クロックは明らかに嘘
今後はクロックという言葉を使うのはやめなさい
次にポインタで持てばリンクリストはO(1)も明らかにおかしい
例えばハッシュテーブルもバイナリツリーもO(1)になってしまう
- 523 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:03:08.30 ID:tN4i8A7m.net]
- >>510
Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
すっきり分かり易いので安全になる。動作が素直だし。
むしろ、途中削除、途中挿入した場合、配列の方が扱いが難しい。
リンクリストは他のノードのアドレスが変わらないのでポインタの値は
変化させなくて良いが、配列の場合は操作をしたノードより後ろに
有るノードの添え字番号がずれてしまうため、そのたびに
管理番号を付け替えるようなことが必要になってしまい、
データ構造が複雑な時に管理がとても大変になる。
リンクリストだとそのような手間が要らないので便利。
ただし、(配列, 添え字) <--> (リンクリスト, アドレス) の双対関係
は常に念頭に置いておく必要がある。後者は基本的には決して
添え字(通し番号)を使ってはいけない。なぜなら、それは後者においては、
ID値としては使えないから。
ただそもそも配列は、添え字はID値としては不十分というか、配列には絶対不変の
ID値が存在しない。リンクリストはアドレスが絶対不変のID値として使える。
- 524 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:04:35.17 ID:tN4i8A7m.net]
- >>511 >>512
まずは、
- 525 名前：r> (配列, 添え字) <--> (リンクリスト, アドレス)
の双対関係を理解しよう。
これが理解出来て無い人は、リンクリストの本来の性能も、本来の使い方も
出来ない。 [] - [ここ壊れてます]
- 526 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:05:48.98 ID:tN4i8A7m.net]
- >>511
俺は頑張って勉強したから数学が得意だったのではない。
テキトーにやってただけで、出来た。
- 527 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:05:52.69 ID:Fw4ypgsa.net]
- そういうの双対って言わないから……
- 528 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:08:15.36 ID:j8Nrs0jp.net]
- じゃあハッシュテーブルもエントリーアドレスでアクセスできるからO(1)と言い出す気か？
- 529 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:11:15.41 ID:tN4i8A7m.net]
- >>514
[補足]
要は、「配列の世界」と「リンクリストの世界」では、世界自体が別物なので、
要素/ノードを識別する手段も違い、前者は添え字番号、後者はアドレスが基本量となる。
従って、リンクリストでは、ノードを識別するには、必ずアドレスを使うことが基本。
それが最も自然であり、高速であるから。
いつまでも、添え字番号で識別する方法しか理解できない人には、言っている意味が理解できない
だろう。
電気と磁気にもさまざまな双対関係がある。世界がある種の対称になっているから、
その際に、正確に対応する量を入れ替えてやら無ければならない。リンクリストでは
通し番号ではなくアドレスを使う。
そうしないと公平ではない。
- 530 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:11:50.99 ID:tN4i8A7m.net]
- >>516
双対の定義は、独自に決めてよい。
- 531 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:13:05.79 ID:tN4i8A7m.net]
- >>517
はあ？
ハッシュテーブルは、実質的にO(1)にとても近い速度で検索できるから
使われているんだが。
- 532 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:16:38.50 ID:sDAG0wCq.net]
- >>514
それは嘘だと誰でもわかる
リンクリストの個別要素のアドレスに対応するものは配列の個別要素のアドレスでありハッシュマップの個別要素のアドレスである
そしてアドレスを持てばO(1)とトンデモを言い出すならば全てのデータ構造がO(1)となる
つまりリンクリストのO(1)は嘘
- 533 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:18:09.73 ID:Z9Xk/5kf.net]
- >>513
>Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
>すっきり分かり易いので安全になる。動作が素直だし。
そんなに簡単だとかいうなら、試しに実装を見せてほし・・・
- 534 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:25:05.70 ID:tN4i8A7m.net]
- >>521
お前が生徒だったら0点つけてやる。
そもそも、動的配列は要素数が内部容量を超える時にアドレスが時々変わって
しまうから、ID番号として基本的にアドレスは使えない。
それをすると、末尾追加するだけでも、定期的にID番号が変わってしまうので
その際にID番号として使っているアドレスを全部修正しないといけなくなるから。
しかし、アプリ内のID番号を全部修正するのは、効率免で良くない。
だから、配列だと要素の一番ましなID番号は添え字番号。
一方、リンクリストで最も効率の良いID番号は、アドレス。
しかも、リンクリストの場合、任意の場所への挿入、任意のノードの削除を
行っても、他のノードのアドレスは変わらないので、アドレスをID番号
として用いている限り、どんな操作をしてもID番号の修正が不要となる。
こんなによいID番号はないわけで、敢えて添え字番号をID番号に使うのは
不適切。
- 535 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:26:21.97 ID:tN4i8A7m.net]
- >>522
Cの入門書で、リンクリストについて書いてあるもの読んで理解して、
頭が悪くなければ、そう自然に解釈できる。
根本的に馬鹿な人には無理かも。
- 536 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:38:14.43 ID:ZOlCZyFx.net]
- rust は safe じゃなきゃ意味がない論者の人かな
- 537 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:43:54.48 ID:tN4i8A7m.net]
- >>525
Cでは生ポインタ一個に対して、Rustは参照関連だけでも、20種類は下らないほど
色々な複雑な仕組みがあるのは、全て safe のためであるのに、safeでなくなったら
それこそCの圧勝になるが。
- 538 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:48:12.68 ID:qezuw3R9.net]
- >>526
コーディングはゲロのようにめんどくさくなるが、
速度面では別にCにそう負けるもんではない
多分最適化しきれなくてほんのちょっと遅くなる部分はありそうだが
- 539 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:48:45.22 ID:tN4i8A7m.net]
- >>477
それは、実はリンクリストも十分に局所性が有る。
というのは、追加するときには、リンクリスト全体のごく一部にバースト的に
挿入することが多いからだ。
そしてその時、ノードのアドレスは等間隔に並ぶ傾向が有るから。
- 540 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:49:16.38 ID:tN4i8A7m.net]
- >>527
いや、今回の例では劇的に遅くなるケースがあるといってるんだ。
- 541 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:51:28.85 ID:qezuw3R9.net]
- >>529
今回の例が何のことか把握してないが（QZが絡んでいるレスは読みづらすぎる）、
配列がどうたらとかの話なら別に配列なんていらんよ
- 542 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:52:03.44 ID:j8Nrs0jp.net]
- 結局この全員の合意とは無関係な些末な話ばかりだな
＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
- 543 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:53:36.07 ID:tN4i8A7m.net]
- >>531
デタラメを何度も書くな。
- 544 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:55:06.43 ID:j8Nrs0jp.net]
- >>532
もし反論があるならしてみたら？
- 545 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:58:27.96 ID:qezuw3R9.net]
- 極論だけど各メンバをUnsafeCellにしてunsafe使いまくれば、
shared XOR mutableルールぶち破れるから、
C/C++でできることはコーディングめんどくさくなるし安全性が結構悲しいことになるけど（でもCとかと同程度）
Rustでも不可能ってことはない
なんならCコードをRustコードに自動変換するやつすらあったような
成熟度は知らんが
- 546 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 23:58:30.48 ID:tN4i8A7m.net]
- >>533
全て書いてるのに理解力が無いから理解できないだけ。
Rust信者は馬鹿ばかり。
- 547 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:02:50.56 ID:g6qk7DwE.net]
- >>507
>Rustはそれを売りにしてるからだよ。
>C/C++は最初から諦めてる。
自分で C/C++ は安全じゃないから、って書いてるじゃん
それが結論でしょ
同じ安全性にしたら、同じになるだろ
- 548 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:05:09.36 ID:HgRvzIV4.net]
- >>536
同じ安全性にする必要がない。
- 549 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:15:16.20 ID:uM27l7Qv.net]
- 前から別の人が指摘しているけど、
リンクドリストとは別に配列を用意してリンクドリストの要素へのアドレスを保持するからリンクドリストの任意の要素にはO(1)でアクセスできる
と主張しているが
そのリンクドリストに追加または削除するたびに配列の要素も追加か削除しないといけなくなる。
リンクドリストの任意の位置に追加/削除するのはO(1)だけど、配列の任意の位置に要素を追加/削除するのはO(1)じゃない。
だからリンクドリストと配列を組み合わせて使うとリンクドリストのメリット(任意の位置への追加/削除がO(1))が無くなってしまう。
その配列に静的配列を使うならリンクドリストの最大サイズを予想してあらかじめ大きな配列を用意しないといけない。
動的配列を使うな要素を追加したときにときどきヒープの再確保がおきる。
- 550 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:21:59.31 ID:uYqg1Oz6.net]
- >>528
実際のメモリレイアウトがどうなるかは言語処理系のランタイムやlibcに依存すると思うのですが
例えば
- 551 名前：どの言語のどの処理系のどのランタイムを使使えばそうなることが確認されているのですか []
- [ここ壊れてます]
- 552 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:23:38.13 ID:HgRvzIV4.net]
- >>538
配列 + リンクリストの代わりに、リンクリスト + リンクリストにすれば解決するぞ。
- 553 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:24:11.08 ID:HgRvzIV4.net]
- >>539
malloc()の仕組みから言ってそう考えられる。
- 554 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:30:08.36 ID:4MgUQE5v.net]
- >>534
Rustはもっと単純
生ポインタを使えばC言語と全く同じ状態となる
fn main() {
let mut a: i32 = 123;
let raw_pointer = &mut a as *mut i32; // aの生ポインタを得る (unsafe不要)
let b = &a; // bがaの参照を借用
// a = 456; // これは借用ルールによりコンパイルエラーとなり書き換えできない
unsafe { *raw_pointer = 456; } // 生ポインタを使えば自由自在に書き換え可能
assert_eq!(a, 456); // 借用ルールを逸脱して書き換わっている
assert_eq!(*b, 456); // 借用している参照bから見ても当然書き換わっている
}
じゃあUnsafeCellなどはいつ使うの？と思うだろうけど
それはRustで安全な型を提供するための部品として用いる
例えばRefCellやOnceCellなどの安全な型は部品としてUnsafeCellを用いている
- 555 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:39:59.63 ID:zo5XubVi.net]
- >>541
最初の初期化時に（あまりフラグメンテーションが発生していない状態で）複数要素追加する以外に追加がほとんど発生しないっていう前提ならそうかもね
でも一般にそうじゃないから連結リスト使うんじゃないの？
- 556 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:42:22.65 ID:xTtlotpf.net]
- さすがにおちょくって遊ぶのを見るのも飽きてきたが
- 557 名前：デフォルトの名無しさん [2021/11/29(月) 00:45:55.70 ID:DszBoyLu.net]
- あわしろ氏もC++は危険と言ってる。
- 558 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:55:31.86 ID:27e/xIh/.net]
- >>541
参照局所性高めたいなら個々の要素ごとにmallocするのではなくarena的に割り当てすべきなのでは
>>543の言うとおり、フラグメンテーション発生してると何も保証できなくなる
- 559 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:59:52.29 ID:4MgUQE5v.net]
- >>542でコードを示したように
C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
したがって以下の合意事項は正しい
＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
- 560 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:00:10.18 ID:HgRvzIV4.net]
- しかし、配列の場合は、内部バッファのサイズが拡張される時には全コピーが
発生するから、キャッシュが大規模に乱れてしまうがな。
その点、リンクリストは乱れたとしてもそこまででは無い。
- 561 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:03:19.07 ID:HgRvzIV4.net]
- >>547
unsafe付けたら全体の安全性も失われるが。
メモリーの間違いには局所性がなくて原因箇所が分かりにくいからこそ、
Rustはメモリー安全に固執しているんだが。
逆にCはそもそもそれをユニットテストなどで徐々にテストしながら開発を進める
ことで確保する方針を採っている。
- 562 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:10:35.89 ID:HgRvzIV4.net]
- リンクリストでのキャッシュの乱れと言っても、アドレスが大幅に異なるものが入り混じっても、
必ずしもペナルティーが増えるわけでは無いぞ。
例えば、2つの大幅にアドレスが異なるノードを交互にアクセスする程度では
キャッシュの読み込み直しは通常の連続アドレスにアクセスした場合に比べて
特に追加発生はしない。
キャッシュメモリ1種類の連続メモリブロックしか収められないわけでは無いからな。
限界はあるが、いくつかのメモリブロックなら同時に収めることが出来るからな。
- 563 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:12:27.10 ID:HgRvzIV4.net]
- >>550
逆にキャッシュ制御せずにmemcpy()みたいなもので大きなメモリーをコピーした
場合、キャッシュが全フラッシュしてしまう可能性も有る。
動的配列の場合はそこに注意が必要。
- 564 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:17:45.41 ID:HgRvzIV4.net]
- >>550
図を書いておこう。2つのメモリー領域A, B があったとして、
リンクリストが
AAAAAAAAAAA
の状態の途中にノードを5つ追加して、
AAAAABBBBBAAAAAA
のようになっていてもそれほどキャッシュミスは起きない。
さらに、もし、
AABCBBACDBBAABBDBCCC
みたいになっている程度でも、そんなにキャッシュミスは起きない。
なぜなら、A,B,C,D の4箇所くらいならキャッシュにどれも収まるから。
- 565 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:20:38.16 ID:tPktcSTu.net]
- >>549
それはウソ
Rustは標準ライブラリの内部に至るところに多数のunsafeがあるのは事実だが
それにより全体の安全性に影響を与えることはない形でのみ提供している
まずunsafeの使用方法は大きく2つに分けられる
(1)影響が局所的に限定される場合
(2)影響が大域的に起き得る場合
つまりunsafeを用いたRustの様々な型やその操作インタフェース等は(1)が満たされている
つまりそれらを利用するプログラムには内部がどう実装されていようと影響をもたらさない
したがってRustのプログラム自体がコンパイラによって安全性を保証することが可能となっている
- 566 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:21:24.40 ID:zo5XubVi.net]
- ベンチも取らずにキャッシュヒット率の話するの時間の無駄すぎない？
あとVecに対するLinkedListの優位性の話されても誰もそんなことは問題にしてないぞ？
- 567 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:26:01.98 ID:HgRvzIV4.net]
- >>553
それはそうかもしれないが、リンクリストの場合、ノードの識別に
アドレスを使うのが、双対原理によって標準なので、その標準手法を
Rustで使おうとすると、unsafeをアプリ本体で使う必要が出てくる。
つまり、ライブラリの中にunsafeを閉じ込めることが不可能。
これは間違いないはずで譲れない。
- 568 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:26:35.85 ID:tPktcSTu.net]
- >>554
ほとんどのケースではLinkedListよりもVecを用いた方が有利
だから使用する言語に関わらず特殊なケースを除けばリンクリストではなくベクターが使われている
- 569 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:32:54.07 ID:HgRvzIV4.net]
- >>556
それが間違いなんだって。
そんな思想だから、ChromeではHTMLもtextareaへの文字列の末尾追加ですら遅いんだな。
計算量が理解出来て無い。
VisualStudioも異常に遅いし。
それに比べて日本人の作るVzEditor, WzEditor は速い。
それはなぜかというと、LinkedListも使っているから。
- 570 名前：デフォルトの名無しさん [2021/11/29(月) 01:44:20.89 ID:DszBoyLu.net]
- LinusもC++は糞言語と言ってる。
- 571 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:44:27.36 ID:27e/xIh/.net]
- 古いけどこんなのみつけた
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
insert/removeはO(1)なlistの方が速そうなものなのに要素サイズが小さいと10万要素でもvecの方が速いんだね
- 572 名前：デフォルトの名無しさん [2021/11/29(月) 01:47:20.54 ID:DszBoyLu.net]
- システムコールの実装によるのでは？
- 573 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:50:31.36 ID:HgRvzIV4.net]
- >>559
Push Front を見たら圧倒的に list が速い。
それにC++のライブラリの list はへたくそな実装になっている。
- 574 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:52:56.70 ID:27e/xIh/.net]
- >>561
deque無視しないでよ
先頭への追加削除が高速なvectorだよ
クラフをログスケールにするとわかるけどlistより速い
- 575 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:53:14.65 ID:HgRvzIV4.net]
- 沢山実験して、LinkedListの方が性能がいいことが分かってるからLinkedList
を使ってる。
ベンチマークは、ベンチマークを作る人が正しく理解してなければ、正しい
テストプログラムを書けないから、正しい結果が出ない。
CPUのベンチマークも実際の体感速度に比例しているとは限らないのと同様。
- 576 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:54:51.63 ID:HgRvzIV4.net]
- list の実装の仕方や使い方に問題があるだけだ。
何度も言ってるように、listは、双対原理から言って、添え字番号ではなく
アドレスを用いなければ成らないことをベンチマークプログラムを作ってる
人が理解出来て無いから、遅く出てることが多い。
- 577 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:56:39.58 ID:27e/xIh/.net]
- 2017年版あったからこっち見た方がよさそう
https://baptiste-wicht.com/posts/2017/05/cpp-containers-benchmark-vector-list-deque-plf-colony.html
>>563
あなたのワークロードではそうなんですね、なるほど
|
 |
