- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 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
あなたのワークロードではそうなんですね、なるほど
- 578 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 01:57:29.30 ID:tPktcSTu.net]
- >>557
ついにGoogleとMicrosoftを批判しだしたのか
>>561
C++擁護派なのにC++のライブラリまで批判しだしたのか
君が間違っているとは考えないのね？
- 579 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:04:18.84 ID:HgRvzIV4.net]
- >>565
要素サイズが128バイトや4096バイトの時には、listの方がvectorより速い。
それに、NonTrivialの時こそ list が効率がいいはずなのに結果が逆になって
いたり、listは、安定なはずなのに、trivial 128 で list のグラフが
途中で直線になってないこともおかしい。
listは、どんなときでも速度が変化しにくい性質があるはず。
何かそのテストはおかしい。
- 580 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:05:00.82 ID:HgRvzIV4.net]
- >>566
俺はCと言っていたが。
C++のSTLには設計に問題が有ると行っているぞ、昔から。
- 581 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:07:29.41 ID:HgRvzIV4.net]
- 実際に自分で実験したこそが無いのに、誰かが実験したものを信じるな。
実際に一般的なケースでは、vectorとlistでは、listの方が速いことが多い。
- 582 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:09:04.94 ID:tPktcSTu.net]
- >>569
ほとんどの用途でベクターが速い
だからほとんどのケースではリンクリストではなくベクターが使われている
- 583 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:12:28.28 ID:HgRvzIV4.net]
- >>570
数理に弱いアメリカ人。
だから、VisualStudioも激オソなんだな。
アメリカ人の作るものは何でもでかくて速度が遅い。
車もでかくて燃費が悪い。
- 584 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:15:22.14 ID:27e/xIh/.net]
- >>567
NonTrivialはMovableな要素だから追加削除時には要素あたりポインタ数個分のデータがコピーされるだけで小サイズと同じ特性になるのは不思議ではないのでは
listについては要素サイズの変化に対して他のコンテナよりも安定的に見えるけど
さすがに要素のコピー分のコストはかかるから要素サイズ変わっても全く同じという訳ではないけど
- 585 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:21:21.41 ID:HgRvzIV4.net]
- こういうベンチマークには、ファクトチェックが必要だ。
今までネットのこういう変な結果のベンチマークを見てきたが、
ソースを見てみると変なことをしてることが多かった。
多かったというより、結果がおかしいと思って調べてみたら全て変なことしてた。
秀才以外が行ったベンチマークは信用できない。
まだ、雑誌は信用できることが多いが、ネットのベンチマークはおかしい。
- 586 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:23:11.00 ID:tPktcSTu.net]
- 『リンクリスト vs. ベクター』のスレ立ててそこでやったら？
少なくともこのスレでやることではない
- 587 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:25:44.21 ID:zo5XubVi.net]
- ではどうぞ、ファクトチェックしてくださいまし
https://github.com/wichtounet/articles/blob/master/src/vector_list_update_1/bench.cpp
- 588 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:29:42.73 ID:27e/xIh/.net]
- 誰かこのベンチマークをRustに移植してみてよ
- 589 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:44:22.88 ID:HgRvzIV4.net]
- 作業時間が発生するものを持ち込まないで欲しい。
こっちはボランティアに馬鹿に説明してやってるだけなんだから。
ソースを出せ、と言ってくるのは抽象的理解が出来ないから。
とても簡単なことを言ってるだけなのに、少しでも抽象的(symbolic)
な言葉で語ると全然理解できない。
数学とは抽象性(symbolic)な学問であるから、数学が出来ない人は
コードを示さないと理解できないらしい。
- 590 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 02:59:57.67 ID:qK4xTYr2.net]
- ベンチマークとかはどうでもいいが、
CだろうがRustだろうが実装可能って話にしか見えん
- 591 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 07:57:57.28 ID:cydEy5/m.net]
- >>538
これな。
結局のところ実体へのポインタの配列であればリンクトリストになってなくても話は同じなんじゃないかな。
- 592 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 08:02:08.66 ID:LzdsKRC
]
- [ここ壊れてます]
- 593 名前：S.net mailto: 実体へのポインタの配列だけでいいよなｗ
それで実体にはすべて到達できるもんｗ
ある実体の次も、前も、それも両方分かるしｗ [] - [ここ壊れてます]
- 594 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 10:19:47.16 ID:zFB6Wt84.net]
- 抽象はabstract
- 595 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 11:26:03.41 ID:ynhRtjt2.net]
- >>579
違う。
リンクトリスト + 配列だと >>538 が指摘している現象が生じてしまうが、
リンクトリスト + リンクリスト だと生じない。
こういっても、数学力の無い人は理解できないだろうな。
数学力は数学という学問だけの能力ではなくて、脳内のワーキングエリアや
イマジネーションなどに関係しているから、生まれつきの影響が大きい。
- 596 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 11:29:51.75 ID:ynhRtjt2.net]
- >>582
[補足]
抽象的理解が難しい人に具体的に書いておいてやろう。
LinkedList ll;
ArrayList al; //自動伸張方式の動的配列だと仮定する
al[0] = ll.append("りんご");
al[1] = ll.append("みかん");
al[2] = ll.append("バナナ");
だと >>538 が指摘しているような不具合が起きる。しかし、
LinkedList ll;
LinkedList ll2;
ll2.append( ll.append("りんご") );
ll2.append( ll.append("みかん") );
ll2.append( ll.append("バナナ") );
だと起きない。
- 597 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 11:36:08.77 ID:27e/xIh/.net]
- >>583
中身が同じリストを二個用意しても意味がないのでもう少し実践的な例の方が理解のためにはよろしいのでは
スキップリストみたいな構造とは違うのですか？
- 598 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 11:36:25.33 ID:ynhRtjt2.net]
- >>583
もっと具体的に書いてやろう。
リンクリストの中の追加した6つの果物の内、4つを他の配列やリンクリストの
中から参照する例を示しておこう。
これの応用としてリンクリスト内の1000個の品物の内、何らかの条件で選び取った10個を
別の配列やリンクリストから参照することが出来る。
1. リンクリスト + 配列
LinkedList ll;
ArrayList al; //自動伸張方式の動的配列だと仮定する
al[0] = ll.append("りんご");
ll.append("みかん");
al[1] = ll.append("バナナ");
ll.append("すいか");
al[2] = ll.append("パイナップル");
al[3] = ll.append("ブドウ");
2. リンクリスト + リンクリスト
LinkedList ll;
LinkedList ll2;
ll2.append( ll.append("りんご") );
ll.append("みかん");
ll2.append( ll.append("バナナ") );
ll.append("すいか");
ll2.append( ll.append("パイナップル") );
ll2.append( ll.append("ブドウ") );
- 599 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 11:36:55.60 ID:ynhRtjt2.net]
- >>584
>>585 を見ろ。
- 600 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 11:39:40.44 ID:ynhRtjt2.net]
- >>585
これがどういう時に起きるかといえば、最初に1000個の品物の入った
リンクリスト ll がある時、条件に合う品物を1つ探してリンクリスト ll2
の末尾に参照を追加する。
それを10回繰り返した後に、実質的に生じる。
- 601 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 12:08:42.24 ID:27e/xIh/.net]
- >>587
queryに対する抽出結果をリストとして保持しておいて元のリストの更新に応じてquery結果も適宜更新されるイメージですか？
- 602 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 12:10:54.78 ID:qK4xTYr2.net]
- 一部のノードが2つのリストで共有されてんのこれ？
- 603 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 12:15:46.59 ID:V8SeceOD.net]
- l2のリストに入れる数によって変わるので結局O(N)の操作じゃね？
- 604 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 12:42:23.24 ID:G+erg93y.net]
- >>590
正確にはll2のサイズN_ll2の半分に近づくね。
ll2のサイズが大きくなるなら、大きめに初期化するのが無難。スカスカならバランス木のmapかね。
- 605 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 12:43:56.81 ID:4MgUQE5v.net]
- リンクリストを少し調べたところ様々な種類のものが使われているようで
様々な分類が生じるうち今回関係するノードの参照については以下の4種類あるようだ
(A) データを挿入しても作られたノード自体は返さない方式
実際にこの仕様でも困らない用途も多いようでこの方式も普通に使われている
もちろん問題は何も生じない
(B) データを挿入して作られたノードのポインタを直接返す方式
これは危険で最も推奨されない方式
ポインタを握っていても使う時にそのノードは削除されているかもしれない
削除で開放されてヒープに戻され更に再利用されているとデータの中身もnext辿りも滅茶苦茶になりうる
そしてデータの扱い次第で実際に削除は起き得るしUI人間や通信相手から発動ルーチンでの削除も有り得る
(C) データを挿入して作られたノードの(一般的な)スマートポインタを返す方式
これはshared_ptrなど安全とされているスマートポインタを返すためメモリ使用上は安全
しかしポインタ先がヒープへ戻されていないことしか保証がない
つまり(B)と同様にリンクリスト自体からの削除が起きている可能性がありそれを知る方法がない
(D) データを挿入して作られたノードを管理しているリンクリスト内部の何らかを返す方式
リスクの高い(B)や(C)と異なりこの方式は安全かつ整合性が維持される
もしノードがリンクリストから削除されていればそれに対して対応ができる
この返されたデータを用いて新たなデータをその位置に挿入する時に元ノードが削除されていた場合
(D)-1. 挿入はされず既に元ノードが削除されていると知らせる
(D)-2. 知らせずに削除された元ノードの次に有効なノードの位置に挿入する
などリンクリストの仕様や用意されたメソッドにより異なるようだ
以上まとめると現実的に安全に使える方式は(A)もしくは(D)となっている
例えばC++の標準リンクリストstd::listでもこの(D)方式を採用しており
insert()はリンクリスト上をその位置から順に辿っていくイテレータを返す
- 606 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 12:52:17.03 ID:qK4xTYr2.net]
- >>585みたいなことできる連結リストって、
Rustでも作れると思うんですけど
Unsafe全振りにはなると思うけど
- 607 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 13:00:24.04 ID:27e/xIh/.net]
- >>593
rustだけはsafeじゃないとだめらしいですよ
- 608 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 15:16:40.92 ID:LzdsKRCS.net]
- > 2. リンクリスト + リンクリスト
それだとさあ
最初から主張してるO(1)ランダムアクセスできないけどいいのｗ
配列だからこそi番目が定数時間でa[i]でアクセスできるんでしょ
- 609 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 15:56:54.32 ID:tPktcSTu.net]
- >>592
やはりポインタを直接返さないんだな
ポインタだけもらって保持していてもそのノードがリンクリスト上でアクティブかどうかすらわからないもんな
- 610 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 16:56:11.45 ID:KFZ7/agt.net]
- C++ の std::list はポインタではなくイテレータで扱うけど、実質ポインタと同じだぞ。
Debug ビルドだと二重 erase は検出してくれるけど、Release ビルドだとセグフォで落ちる。
- 611 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 17:12:06.45 ID:tPktcSTu.net]
- そもそも途中ノードのポインタを保持していても普通の使い方だとそこへ挿入することないよな
リンクリストの先頭挿入か最後挿入かあるいは何らかのデータ順になっていてその位置に挿入だよな
可能性があるのはエディターくらいだけどそれならばカレントポジションをエディター用リンクリストの中で保持した方が便利
- 612 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 17:31:01.57 ID:uM27l7Qv.net]
- ポインタだらけのデータ構造ってそれをファイルに保存するとかネットで繋がった別のマシンに送るのって大変じゃない？
ポインタの代わりにインデックス使ってればそのままシリアライズできるけど
- 613 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 17:39:15.23 ID:KFZ7/agt.net]
- というか std::list はメモリも速度もコスト高いし、普通は std::vector を使う。
途中への挿入・削除が頻繁に発生するようなら std::list の使用も検討するべき。
ノードが既に分かっているとして、当該ノードの保持する値へのアクセスが O(1) で
行えるのは当たり前の話で、これが出来ないコンテナって存在するのか？
リンクリストは（既に分かっている）ノードの削除、
（既に分かっているノードの前後への）挿入が O(1) で行えることに意味がある。
- 614 名前：ハノン mailto:sage [2021/11/29(月) 19:03:52.90 ID:NTguHH8l.net]
- >>585
C でも rust でもいいから動くソースを出してもらえませんか？ここ、確かプログラム板でしょ？
- 615 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 19:45:36.73 ID:27e/xIh/.net]
- >>599
多くのケースではシリアライザ手書きしないから気にならないのでは
例えばrustならserdeがLinkedList対応してるからVecと同じ手軽さでシリアライズ・デシリアライズできると思われる
- 616 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 19:59:41.83 ID:tPktcSTu.net]
- >>602
その中の切れ端へのポインタをもらってどうするの？って話だから話がずれてる
- 617 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 20:15:59.10 ID:FNlZ9i/O.net]
- リンクリストのノードをさらにリンクリストにいれてなにがしたいんだ
- 618 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 20:28:16.85 ID:4MgUQE5v.net]
- >>604
リンクリストはポインタだからO(1)で速い！とナゾ主張する勘違い君がさらに暴走した結果
- 619 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 21:15:38.25 ID:27e/xIh/.net]
- >>603
普通にVec相当の構造に変換された上でシリアライズされてデシリアライズ時にlistに変換されるよ
- 620 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 21:27:48.38 ID:4MgUQE5v.net]
- >>606
それ怪しいな
LinkedList型はser/de定義されていて先頭保持してるところから順にたどって全体を巡るとして
途中ノードのポインタを渡されてもまずそのノードだけ対象になるのかそれとも次をたどるのか曖昧
もし同じように順にたどるとしてもLinkedListの一部分が出来上がりそれに意味があるのか疑問
- 621 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 21:32:39.40 ID:2AI6LBe9.net]
- そりゃsafety売りにしてる言語が実はunsafeばっかとか言えませんよね。普通の感覚ならね。
- 622 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 22:50:59.13 ID:27e/xIh/.net]
- >>607
CursorではなくてLinkedListのシリアライズに対応してるから必ずリストの先頭からのシリアライズ
>>608
なぜ？
safeを売りにするという言葉をどのように解釈しているの？
|
 |
