- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 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を売りにするという言葉をどのように解釈しているの？
- 623 名前：デフォルトの名無しさん [2021/11/29(月) 22:59:12.77 ID:qFPvT22S.net]
- あわしろ氏はC++の危険性を見過ごせないと言ってた。
ダングリングポインタは諸悪の根源と言える。
- 624 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 00:01:14.91 ID:LDqTXpbe.net]
- 他の言語なら危険でないとでも？
- 625 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 00:58:11.71 ID:oK3YB4Sq.net]
- >>595
ll2にllの検索条件に合うノードのポインタを順に入れて言った場合、
llのノードが順序がバラバラで入っていることになり、
ll2を先頭から順にシーケンシャルアクセスすると
llはランダムアクセスされることになる。
なお、ランダムアクセスとはシーケンシャルアクセス以外のアクセスを全て指す
言葉。
- 626 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 00:58:48.79 ID:oK3YB4Sq.net]
- >>612
もちろん、O(1)だ。
- 627 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 02:01:49.64 ID:Y6JwF3m3.net]
- >>612
> ll2にllの検索条件に合うノードのポインタを順に入れて言った場合
なぜポインタを辿って遅くて不便なリンクリストを使うの？
順に入れるならベクタを使えば速くてメモリも食わないのに
- 628 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 02:45:59.65 ID:oK3YB4Sq.net]
- >>614
そこをベクタにしてしまうと、せっかくのリンクリストの特性であるところの
O(1)性が完全な意味では維持できなくなるからだよ。
- 629 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 03:29:37.11 ID:oK3YB4Sq.net]
- リンクリストは、損して得取れの考え方だからね。
配列は、ちょっとしたことで使うには良いが、
一見得してるようだが、複雑なことをやる場合には損することが多い。
- 630 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 03:32:42.38 ID:Y6JwF3m3.net]
- >>615
リンクリストはランダムアクセスO(n)で遅いから特殊な用途でしか使われていない
ほとんどのケースではランダムアクセスO(1)のベクタが使われている
シーケンシャルアクセスだけならどちらも同じだけどポインタをたどるリンクリストは遅くてメモリも余分に使って結果不利
- 631 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 03:45:18.10 ID:oK3YB4Sq.net]
- >>617
アホは黙っててくれないかな。
俺は数学100点マンなんだぞ。
お前は完全に間違ってる。
- 632 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 03:56:01.94 ID:oK3YB4Sq.net]
- 今後、秀才か天才しか書込み禁止。
そうでないと、まともな議論にならない。
IQ130以上限定。
- 633 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 05:23:13.37 ID:Z1GOh4zf.net]
- 数学100点マンがなんだ俺はセンター数学2科目200点マンだぞ
- 634 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 07:52:52.15 ID:OSju058V.net]
- 東大入試数学満点、数オリ経験者のオレ登場
- 635 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 09:09:56.43 ID:9yDJj/SR.net]
- >>621
今までの論争？についてどうですか？
- 636 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 12:21:03.90 ID:M/ykbWDe.net]
- >>622
細かくは読んで無いけど
限定がなければ当然同じ計算オーダーの構造は作れるはず
いずれもリソースを限定しなければチューリング完全な言語であるわけだから
あとは限定次第
特定のコンテナを使う場合とか安全性とか
各言語での流儀とか
- 637 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 12:22:32.67 ID:M/ykbWDe.net]
- 計算可能性と計算オーダーは関係無かったか
2文目は取り消しでお願い
- 638 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 17:35:34.91 ID:BH845EGe.net]
- >>623
>限定がなければ当然同じ計算オーダーの構造は作れるはず
>いずれもリソースを限定しなければチューリング完全な言語であるわけだから
確かに同じ計算オーダーの構造は作れるが、制限を回避するためにかなり遅くなる。
例として、参照もポインタも無いBASIC言語で、配列だけを使ってポインタを
模倣することも可能ではあり、実際にポインタと同じような計算オーダーを
持つものをそれでも実現可能ではあるが、「速度係数」が大きくなる。
Rustの場合、safeモードでは、1つのリンクリストに対して、読み書きが出来る
参照を複数同時にはマシン語レベルの生アドレスとしては持つことが出来ない。
その制約を回避するため、別の配列をわざわざよういして、アドレスの代わりに
配列の添え字番号を持つ整数型を参照型の代替として用いるやり方が、
提示されていた。
- 639 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:12:13.96 ID:Y6JwF3m3.net]
- >>625
Rustでも生ポインタを使えば制約は一切ない
ソースコード>>542
さらにリンクリストで生ポインタを返すのは危険なので一般的にもっと安全な形が取られている
リンクリスト分類まとめ>>592
- 640 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:13:44.06 ID:BH845EGe.net]
- >>626
あなたは、秀才じゃないでしょ。
分かるから。
言ってること的外してるし。
- 641 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:15:08.99 ID:rIKeeiBO.net]
- safe Rustが要求するレベルの安全性（特に共有参照が存在する間はそれを変更できない）を実現するには、
C言語だろうとC++だろうと排他機構が必要になって、実行時コストを払わずに行うことは不可能
- 642 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:16:39.59 ID:BH845EGe.net]
- >>628
C++は、プログラマが自分の頭で考えて、安全性を確保する思想だから、
あなたの言ってるコストは元々必要ないという思想。
- 643 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:25:09.74 ID:rIKeeiBO.net]
- >>629
聞いたことないが誰の言葉？
- 644 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:26:13.61 ID:BH845EGe.net]
- >>629
[補足]
なお、マルチスレッドにおける、排他制御はCやC++では必ず必要。
それはプログラマが頭で考えても省略できない。
なお、シングルスレッドにおける Rustの借用規則のような仕組みを
に「排他制御」という言葉は通常は使わない。
- 645 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:27:12.73 ID:BH845EGe.net]
- >>630
あなたも秀才じゃないでしょ。
書いてあることで分かる。
- 646 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:35:01.07 ID:rIKeeiBO.net]
- イテレータをポインタだと思ってやっぱ複雑なC++じゃなくてC言語で話そうとか言っちゃう人が自分の頭で考えて安全性確保できる秀才ってマジですか
- 647 名前：デフォルトの名無しさん [2021/11/30(火) 18:39:16.69 ID:TJjyIr2u.net]
- Rustで書かれたFirefoxはC++で書かれたChromeより三倍以上の安全性を持つ。
- 648 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:41:46.86 ID:BH845EGe.net]
- >>633
なぜC++で説明しないのかといえば、std::listは、std::vectorなどの
他のコンテナと同じ使い勝手にするために、リンクトリスト本来の
アルゴリズムとは異なって実装されてしまっている可能性があるから。
- 649 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:42:00.53 ID:Y6JwF3m3.net]
- >>631
シングルスレッド内のマルチタスク(いわゆるグリーンスレッド)でも競合は起きます
例えばポインタを得た後にファイルや通信の読み書きを行えばシングルスレッド内の別タスクに切り替わります
その別タスクが人間UIから指示でリンクリストの一部削除も起き得ます
元のタスクに切り替わった時に保持してるポインタの先は既に削除されて存在しないかもしれません
したがってシングルスレッドでも競合対策は必要です
- 650 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:43:00.57 ID:BH845EGe.net]
- >>634
そもそも Chromeが根本的にバグったりダウンした経験が無いので
そういわれても分からない。
- 651 名前：デフォルトの名無しさん mailto:sage [2021/11/30(火) 18:44:23.35 ID:BH845EGe.net]
- >>636
でもそのことを通常、「排他機構」とは言わないハズ。
独自定義の言葉は混乱するので使うべきでない。
- 652 名前：デフォルトの名無しさん [2021/11/30(火) 18:46:28.71 ID:TJjyIr2u.net]
- >>637
クレジットカードやパスワードが既に。
|
 |
