C++ vs Rust

■ このスレッドは過去ログ倉庫に格納されています
2021/04/24(土) 08:04:49.48ID:nPKzA798
競え
2021/11/27(土) 22:07:53.33ID:kID5mUHa
オブジェクトのアドレスをハッシュテーブルで持たせて、双方向リストで実装。
2021/11/27(土) 22:11:02.52ID:bCVlBsXA
>>443
＞具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ

>>432
＞「一度取得したノードの再アクセスコスト」を特に取り上げて考える
という、他ではあまり聞いたことのない特殊な話ゆえに筋を深く追えていないのですが、

>>432
＞リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る
において
①
＞すでに取得している指定ノードの削除
でいいですか？
②
データ構造は一方向リストでいいですか？
2021/11/27(土) 22:20:41.20ID:g2vJAoph
>>445
一方向だと削除がO(1)じゃないから双方向が良いのでは
2021/11/27(土) 23:03:04.21ID:bCVlBsXA
>>446
それは末尾または冒頭ノードの削除の話ですね
何が与えられていて、何を削除するのか、きちんと定義していただきたいです
2021/11/27(土) 23:04:36.52ID:bCVlBsXA
>>446
失礼、あるいは特定ノードの上流ノードの探索の話もありますね
確かに双方向の方が楽チンですが、「ダブルポインタ」を使えば単方向でも処理できないわけではないです
2021/11/27(土) 23:42:34.01ID:+ONNbmgV
スマンが、余り言いたくないことだが、QZが出てくると話がとてもややこしくなる。
2021/11/28(日) 00:05:23.91ID:L/jojvYG
まだやってたのか
2021/11/28(日) 02:32:25.17ID:DhOI6JvL
>>449
当然でしょう

>>432
＞リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る場合には
＞ノードの追加
＞ノードの検索
＞すでに取得している指定ノードの削除
＞
＞あたりを考えるのが普通

なのに、

>>445
＞＞「一度取得したノードの再アクセスコスト」を特に取り上げて考える
＞という、他ではあまり聞いたことのない特殊な話

を延々とやっていることに噛み付いているのですから

さて実装実装…
2021/11/28(日) 02:39:16.73ID:Fw4ypgsa
それがこのスレの目的ですから
2021/11/28(日) 03:42:41.88ID:sDAG0wCq
ある特定のエントリーを持つ変数はプログラム中に複数存在しうると議論中にも出ていたから
リファレンスカウンタは必須になるな

重要な点としては
コンストラクタやデストラクタやスマートポインタに隠れて曖昧にならないように
それらを使わずに実装すべきだ
そもそもC言語でもO(1)という話なのだから
まずはC言語かつ標準ライブラリのみ使用が今回のコード条件
2021/11/28(日) 04:07:17.98ID:DhOI6JvL
>>453
ん？アンカーで示してください
今回はリファレンスカウンタは実装に含めないつもりです、まあ C で書くつもりですけど
2021/11/28(日) 10:45:19.29ID:tHJVymxJ
もうソース出せって意地悪言わないで、無視しときなよ
配列に格納し直すのが彼のアイデアの全てなんだから、つついても面白い話は出てこないよ

O(1)で追加・削除できる配列も作れる！って言い出したら、多分リンクリストを使うってことだよ
2021/11/28(日) 14:56:23.04ID:DhOI6JvL
>>443
https://mevius.5ch.net/test/read.cgi/tech/1434079972/105
これでいかがでしょうか？
2021/11/28(日) 17:32:59.07ID:4++rc1oJ
>>443
C/C++では、ダングリングが発生するのを防ぐのはプログラマーの仕事だ。
2021/11/28(日) 17:39:38.36ID:DhOI6JvL
>>443
引き続いて双方向リストの場合
https://mevius.5ch.net/test/read.cgi/tech/1434079972/106
これでいかがでしょうか？

>>444
＞オブジェクトのアドレスをハッシュテーブルで持たせて、双方向リストで実装。

では C で実装願いますね
私は宿題を片付けましたので 、ちゃんちゃん
2021/11/28(日) 17:42:46.59ID:4++rc1oJ
>>451
>>432では、あなた、そういうこと書いてなかったよね。
こういう議論でははっきり言わないと分からないよ。

でも、あなたの観点は間違ってる。
C/C++/Java/C# においては、リンクリストで、一度作成したノードのアドレスは
ずっと保存するのが基本で、「先頭からの通し番号」で「辿る」ということは効率
が悪すぎて特殊なケース以外ではしないから。
2021/11/28(日) 17:47:22.55ID:DhOI6JvL
>>459
もうリンクリストなんか不要で、最初からハッシュテーブル一本でやっていくべきなのでは？
なんでリンクリストとハッシュテーブルを両方使うのですか？
2021/11/28(日) 17:51:06.30ID:4++rc1oJ
>>460
ハッシュテーブルなんて全く使って無いぞ。
あなたはポインタの仕組みを理解して無いのか？
2021/11/28(日) 17:54:05.88ID:4++rc1oJ
QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
のではないか。
アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
基本的にハッシュ構造とは全く関係無い。
2021/11/28(日) 17:58:02.00ID:DhOI6JvL
>>461
失礼、>>444 とは別の方なんですね

でも、

＞C/C++/Java/C# においては、リンクリストで、一度作成したノードのアドレスは
＞ずっと保存するのが基本で、「先頭からの通し番号」で「辿る」ということは効率
＞が悪すぎて特殊なケース以外ではしないから。

それはそうです、リンクリストを頭から舐めるのは効率がイマイチなのはおっしゃるとおり、単純な構造だからそれはしかたがない
しかし、

＞リンクリストで、一度作成したノードのアドレスはずっと保存する

って、どこにどういう形で保存するのです？
2021/11/28(日) 17:59:56.44ID:DhOI6JvL
>>462
＞QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
＞のではないか。
>>456, >>458 で示した程度には理解しているつもりです

＞アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
で、そのアドレスをどのように管理するのですか？どのような形でどのようなデータ構造に格納するのですか？C/C++ で説明いただくと助かります
465デフォルトの名無しさん
垢版 |
2021/11/28(日) 18:32:54.89ID:Izo/gJUY
>>463
>＞リンクリストで、一度作成したノードのアドレスはずっと保存する
>って、どこにどういう形で保存するのです？

・リンクリスト全体のノードを辿ればいい場合には保存する必要が無い。
　なお、その場合、1ノード右側のノードのアドレスを取得するのは1～2クロック
　しかかからない。

・例えば、1000個のノードが入っている場合の、特定の 2 個のポインタを
　保存したい場合には、グローバル変数の2つのポインタにそれぞれの
　アドレスを代入しておけばよい。
　それは丁度、ArrayList(vector)の場合であれば、添え字番号を2つの整数
　変数に代入しておくのと全く同じこと。

・要は、ノードを識別するための数値が、配列では整数型の添え字番号であったところが、
　リンクリストでは、ポインタ型のアドレスになるというだけのこと。
　決して後者に置いては、通し番号を使ってはいけない。
　数学的には、次のような双対関係の様なものが存在していると考えられる:
　（配列, 添え字) <---> (リンクリスト, アドレス)
　QZを含めて、この双対関係を理解できておらず、
　（配列, 添え字) <---> (リンクリスト, 添え字)
　と間違って理解してしまっている人が多いことから、リンクリストでのランダムアクセス
　が O(N)などと謝った認識に至ってしまう人が多いと考えられる。
　しかし、正しく双対関係を理解すれば、O(1)であることが理解できよう。
2021/11/28(日) 18:40:36.55ID:DhOI6JvL
>>465
結論から申し上げれば、ここはプログラム板だから、適切なお題を設定してプログラムで例示いただけませんか？

＞リンクリストでのランダムアクセス　が O(N)などと謝った認識

いいえ、リンクリストの各ノードのアドレスは、リンクリスト内で調達するのならば、O(N) でしか取得できないものですよ
あなたはリンクリスト以外の何か別のデータ構造を使ってリンクリストのアドレスを管理しようとしているようですが、
ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
2021/11/28(日) 18:50:25.63ID:Izo/gJUY
>>466
あなたはやはり馬鹿だな。
それをいうなら、配列も同じ。
配列の添え字番号を覚えておくのに、別の配列が必要になる。
お分かりかな？
あなたは、双対を全く理解出来て無い。
2021/11/28(日) 18:53:09.31ID:uSmUEadq
>>465
それってリンクリストの意味ある？
なんのためにリンクリストにするんだ？
2021/11/28(日) 18:57:11.39ID:pGvlrRKC
Linked Listを使っているのにLinkを辿りたくないらしい
2021/11/28(日) 18:58:57.15ID:uSmUEadq
アドレス保持してればなんでもランダムアクセスできるっていうなら
あらゆるデータ構造がランダムアクセス性を持つということになってしまうな
2021/11/28(日) 19:16:56.34ID:/zln3poJ
>>466
Qちゃんお疲れ

> あなたはリンクリスト以外の何か別のデータ構造を使って
> リンクリストのアドレスを管理しようとしているようですが、
> ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？

それは色んな人がわりと最初のころから既にツッコミ済みなのだよ…
ようやく議論に追いついたねキミは
2021/11/28(日) 19:42:21.78ID:1e4/tv+M
>>470
実際、C言語などから高級言語にポインタの概念が入ってからはそうなった。
ただ、Rustはそうなって無いから問題なんだよ。
2021/11/28(日) 19:42:59.18ID:ZOlCZyFx
>>462
ポインタの指す領域に1クロックでアクセスできるCPUなんてあるんですか？
ポインタの指す先がメモリにあるかキャッシュにあるかで異なりますがL1キャッシュにあっても数クロックかかるのではないかと思います

数クロックを争うような話をするなら実装がないと話にならないと思うので、まずは比較したい書く言語の実装を用意しましょうよ
既存のコードへのリンクで良いので
2021/11/28(日) 19:43:39.06ID:1e4/tv+M
やっぱり、数学が出来ない人は、双対の概念に脳が追いついてこないらしい。
双対という言葉の意味が分からなくても、生まれつき頭のいい人なら、
俺の言っている意味がわかるはずだ。
2021/11/28(日) 19:44:13.37ID:1e4/tv+M
>>473
キャッシュに載っていたらの話だ。
2021/11/28(日) 19:44:50.23ID:ZOlCZyFx
>>472
任意のアドレスへのアクセスは本質的にunsafeだと思うのですが、safe rustでそれができないことにどのような問題があるのですか
2021/11/28(日) 19:45:41.68ID:ZOlCZyFx
>>475
リンクリストは参照局所性が悪いのでキャッシュに載っていない確率が大きいのですが、本当に高速なのですか？
2021/11/28(日) 19:59:16.91ID:DhOI6JvL
>>474
双対性にもいろいろありますよね…論理学上の双対命題（∩と∪、∀と∃の入れ替え）ならばその否定が証明できますが、そういう意味ですか？
それとも正十二面体と正二十面体の双対性ですか？
適当にペアにして双対と呼んでいるだけなのでは？
2021/11/28(日) 20:01:48.12ID:DhOI6JvL
>>471
そうなんですね…
2021/11/28(日) 20:10:07.08ID:DhOI6JvL
>>473
いや、突っ込みどころはそこではなくて、
「あるときは O(f) ランダウのオミクロンで話をしたかと思うと、次の瞬間、クロック数を問題にする」というバラバラな論理展開でしょう
ランダウでやるんだったら最後までランダウで統一してほしいのですが…
2021/11/28(日) 20:33:56.21ID:tN4i8A7m
>>480
ランダウ記号は、大まかな分類しか示せない。例えば、
O(N)は、N→∞ の時に、
O(N)/N < α (alpha)
のように有る正の実数αによって、「抑えられる」という意味しか示せないし、
O(1) < α (alpha)
であることしか意味しない。
だから、O(1)であることよりも、1クロックであることの方がずっと意味が強い。
なので、ちゃんと1クロックであると分かっているなら1クロックと書いた方がいい。
2021/11/28(日) 20:51:47.55ID:DhOI6JvL
>>481
ある数量に対応する空間的・時間的コストの依存状況を滔々と語っていたかと思うと、次の瞬間は実時間に関する話に都合のいいように鞍替えするのは論理的でない、といっているのです
実時間なら実時間、依存関係なら依存関係できっちり話をわけてほしいですね
2021/11/28(日) 20:59:23.99ID:tN4i8A7m
>>482
悪いが、お前が馬鹿なだけだ。
数学的には、O(1)と書くこともあれば、実クロックで書くこともあり、
混ぜたらいけないなんてことは無い。
ちゃんと理解していれば、混ぜても問題ない。
2021/11/28(日) 21:06:52.79ID:DhOI6JvL
>>483
「数学的」の定義を伺いたいものですが、それはさておき、実クロックなんて「おま環」な話をしても仕方がない場合も多いのですよ
今はキャッシュのヒット率で処理速度も大きく変わるから、実クロックによる考察なんてほとんど無意味です

しかしデータ数等の「ある数量」に対する時間的・空間的コストの評価ならば、それは、どの環境にもっていっても通用する、すなわち適用範囲が広いのです
何か評価をしたいのなら、広い環境で通用する評価方法の方が有用でしょう

あなたは、その二つの評価方法の意義の違い（「どちらが有意義か」）を知らないから「混ぜたらいけないなんてことはない」などとシレっといえるのですよ
2021/11/28(日) 21:14:34.22ID:tN4i8A7m
>>484
そうじゃないんだ。実際のクロック数の事ではなくて、マシン語で書いたときに
1命令だということなんだ。
2021/11/28(日) 21:17:54.80ID:tN4i8A7m
キャッシュの話なんかは状況が複雑すぎて議論を複雑にするだけで、本質を理解する
邪魔になる。
まず、それは横に置いておいて、基本を理解しないといけない。
キャッシュの影響についてはその次。

また、なら、最初から「1命令」と書いておけば良かったのに、という突っ込み
が予想されるが、1命令でも乗算命令なんかは13クロック(レイテンシ)以上かかるから
それとは区別するために1クロックと書いた。
キャッシュは複雑すぎて話が混乱するだけ。
ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
依存せず必ず言えることだから、そう書いた。
2021/11/28(日) 21:20:07.26ID:DhOI6JvL
>>485
命令数なんてもっと当てにならないですよ、内部で別形態に変換され並列に実行されたりするわけで、人手で最適化することは不可能なしろもの
そんな制御できないものを評価対象にしてもしかたがないのでは？
2021/11/28(日) 21:25:24.33ID:DhOI6JvL
>>486
＞ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
＞依存せず必ず言えることだから、そう書いた。

残念ですがキャッシュにヒットするかしないかで大きく実行時間は変わりますね、キャッシュにヒットせず、RAM 空間上から引っ張ってくる場合は数十クロックは必要でしょうね…
そんな「お前の環境でしか通用しない話だろう」的な曖昧な評価方法よりも、どの環境でも通用するランダウのO記号による評価の方が有意義でしょう

どちらの方が有効範囲が広い有意義な評価法なのかを知らないから、ちゃんぽんにして話をしても不自然さを感じないじゃないですか、あなたは？
2021/11/28(日) 21:26:27.36ID:tN4i8A7m
>>487
そうでなくて、Rustでも、O(1)というものだけなら、作ろうと思えば作れるから
1クロックと書かざるを得なくなったんだよ。
Rustの場合は、O(1)でも、単なるポインタでは無く、配列を介すので、
乗算、足し算、境界チェックが入ってしまうのでトータルで20～50クロック
くらい掛かる。このうち、境界チェックだけは外せるかも知れないが。
2021/11/28(日) 21:27:53.03ID:tN4i8A7m
>>488
>>489 を見ろ。
「なぜあなたは文脈を考えて書かないんだ」
と はちみつ餃子にも指摘されてただろ。
2021/11/28(日) 21:30:30.36ID:DhOI6JvL
>>489
＞乗算、足し算、境界チェックが入ってしまう

C/C++ の配列とても乗算・足し算は入りますよ…
そんな瑣末な話とO(1), O(N) の話をちゃんぽんにしても不自然さを感じない感性に私は大いに疑問を感じます
2021/11/28(日) 21:34:48.65ID:DhOI6JvL
>>490
よくご存知ですね…
まあ、今日は基本的なデータ構造を基本的な言語を使用して白紙からコーディングする機会を下さったあなたには感謝してますよ、久々に脳細胞を使ったのでちょっといい気分です
2021/11/28(日) 21:40:43.94ID:tN4i8A7m
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の場合とは
雲泥の差である。
494デフォルトの名無しさん
垢版 |
2021/11/28(日) 21:42:26.92ID:8j2GjV45
俺は 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;
}
2021/11/28(日) 21:43:21.57ID:tN4i8A7m
>>491
お前はアホか。
リンクリストの場合は、乗算が入らないんだよ。

>>493
ミス訂正:
配列の場合は、
mov ebx,index　;添え字番号
imul ebx,配列のバイト数
mov eax,[ebp+ebx+32]　　　;32はスタックの中での位置

従って、リンクリストの方が一般的にはアクセスが速い。
リンクリストは、1クロック位、配列の場合は、要素が一般のバイト数の場合は、
14～36クロック位。
496デフォルトの名無しさん
垢版 |
2021/11/28(日) 21:47:47.53ID:tN4i8A7m
>>494
>Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
そうじゃない。
Rustでも、insert, remove 自体は、標準実装でも O(1)で行える。
ところが、アクセスが、標準実装では、借用規則のために複数の
読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
辿る必要があるため、O(N)かかる。

特殊な独自実装をすると、アクセスがオーダー的にはO(1)で出来るが、
特殊実装な故に、>>493 の後半のようになってしまい、
20～50クロック位かかる。
2021/11/28(日) 21:49:24.66ID:DhOI6JvL
>>494
読みました
私の場合は双方向リストを循環させ、始点のみをポイントすることとしましたが、結果として記述はあまり簡単にはならなかったですね、うーむ
2021/11/28(日) 21:56:03.25ID:tN4i8A7m
すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
2021/11/28(日) 21:56:11.42ID:tN4i8A7m
すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
2021/11/28(日) 21:56:13.54ID:tN4i8A7m
すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
501デフォルトの名無しさん
垢版 |
2021/11/28(日) 21:57:51.47ID:8j2GjV45
remove メソッドにバグがあった (head, tail を更新していなかった) ので一応修正。
https://wandbox.org/permlink/GlDCsezlcix3aJvi

>>496
なるほど。アクセス時に通し番号的な物が必要になるのであれば
insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。

>>497
双方向リンクリストは始点と終了をペアで持つという固定観念があったので、その発想はなかったです。
2021/11/28(日) 22:02:54.87ID:tN4i8A7m
>>501
>なるほど。アクセス時に通し番号的な物が必要になるのであれば
>insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
先頭や末尾では無い途中のinsert、removeであれば、あなたの言うとおり。
追加する直前のノードにたどり付くまでに一般的にはO(N)の時間が掛かる。
ただまあ、末尾追加や先頭追加と、末尾削除、先頭削除なら、RustでもO(1)で
出来るだろう。
なお、Cursorを使えば、よくあるケースだけは高速に行えるようになっているかも知れないが。
あくまでも良くあるケースだけは、unsafeを使って特別対応しているだけ。
複雑な一般的なケースでは、やはり、O(N)かかってしまう。
その意味で、あなたの言っていることは正しい。
2021/11/28(日) 22:13:58.18ID:uBLcCIA8
いつまで例のVecを使った謎LinkedList実装にこだわっているのだろう
2021/11/28(日) 22:17:12.75ID:tN4i8A7m
>>503
こだわっているというか、あれは、オーダー的にはCと同じく、ほとんど全ての
動作をO(1)で出来てしまうリンクトリストをRustでも出来ているから、
注目に値する。
ただし、O(1)と言っても、実際には遅い。
また、Read After Delete、ダングリングポインタに相当するものがRustでも
生じる。たとえ、safeモードで書いても。
2021/11/28(日) 22:20:39.78ID:qezuw3R9
なんでRustだけsafe前提なんすか？
2021/11/28(日) 22:21:32.31ID:uBLcCIA8
>>504
要素追加でバッファ超えると配列全体をコピーするけどO(1)なんだ？
いいのかそれで？
2021/11/28(日) 22:26:36.40ID:tN4i8A7m
>>505
Rustはそれを売りにしてるからだよ。
C/C++は最初から諦めてる。

>>506
その指摘は正しい。
平均的にはO(1)だが、スパイク状に(不定期に)O(N)のコピー動作が入ってしまう。
2021/11/28(日) 22:29:15.25ID:DhOI6JvL
>>501
私のやり方でよかったことは、prev/next の無矛盾性のチェックが簡単に書けることくらいでした、他は複雑になってしまった…
2021/11/28(日) 22:50:50.98ID:qezuw3R9
>>507
売りにしてるいうても結構厳しい制限だからデータ構造に直結するようなコードはsafeのみじゃ無茶だぞ
連結リストのようにユーザ側もダングリングとか多重参照とか気をつけなきゃいけないタイプのものは、
safeの範囲じゃ回りくどいことやるハメになるか、そもそも本当に無理になるかだ
2021/11/28(日) 22:53:17.54ID:Z9Xk/5kf
>>496
>ところが、アクセスが、標準実装では、借用規則のために複数の
>読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
>先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
>辿る必要があるため、O(N)かかる。

そうなんだ
でもこれってC/C++でもメモリ安全で、スレッドセーフとかにしたら同じにならん？
2021/11/28(日) 22:59:54.62ID:hrke4Ba5
自分はがんばって数学の勉強をしてきたので自分の考えは絶対に正しい、間違うはずがないと思いこむ。
そうなると一度間違った考え(リンクドリストの任意の要素にO(1)でアクセスできる)を持ってもそれを間違った考えとは気づかずにその間違いを補強するようなチグハグな考え方をするようになる。
反ワクチンのようなトンデモ科学にはまっちゃう人に周囲の人がいくら正しい科学知識で説得しても自分の考えに疑問を持つどころか、自分の考えは絶対に正しい、周りのやつらは頭がおかしいと思いこんでしまう。

自分の考えが間違うこともあるのではないかと謙虚になることも重要だということだね。
2021/11/28(日) 23:00:17.08ID:j8Nrs0jp
まずポインタで持てば1クロックは明らかに嘘
今後はクロックという言葉を使うのはやめなさい

次にポインタで持てばリンクリストはO(1)も明らかにおかしい
例えばハッシュテーブルもバイナリツリーもO(1)になってしまう
2021/11/28(日) 23:03:08.30ID:tN4i8A7m
>>510
Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
すっきり分かり易いので安全になる。動作が素直だし。

むしろ、途中削除、途中挿入した場合、配列の方が扱いが難しい。
リンクリストは他のノードのアドレスが変わらないのでポインタの値は
変化させなくて良いが、配列の場合は操作をしたノードより後ろに
有るノードの添え字番号がずれてしまうため、そのたびに
管理番号を付け替えるようなことが必要になってしまい、
データ構造が複雑な時に管理がとても大変になる。
リンクリストだとそのような手間が要らないので便利。

ただし、(配列, 添え字) <--> (リンクリスト, アドレス) の双対関係
は常に念頭に置いておく必要がある。後者は基本的には決して
添え字(通し番号)を使ってはいけない。なぜなら、それは後者においては、
ID値としては使えないから。

ただそもそも配列は、添え字はID値としては不十分というか、配列には絶対不変の
ID値が存在しない。リンクリストはアドレスが絶対不変のID値として使える。
2021/11/28(日) 23:04:35.17ID:tN4i8A7m
>>511 >>512
まずは、
(配列, 添え字) <--> (リンクリスト, アドレス)
の双対関係を理解しよう。

これが理解出来て無い人は、リンクリストの本来の性能も、本来の使い方も
出来ない。
2021/11/28(日) 23:05:48.98ID:tN4i8A7m
>>511
俺は頑張って勉強したから数学が得意だったのではない。
テキトーにやってただけで、出来た。
2021/11/28(日) 23:05:52.69ID:Fw4ypgsa
そういうの双対って言わないから……
2021/11/28(日) 23:08:15.36ID:j8Nrs0jp
じゃあハッシュテーブルもエントリーアドレスでアクセスできるからO(1)と言い出す気か？
2021/11/28(日) 23:11:15.41ID:tN4i8A7m
>>514
[補足]
要は、「配列の世界」と「リンクリストの世界」では、世界自体が別物なので、
要素/ノードを識別する手段も違い、前者は添え字番号、後者はアドレスが基本量となる。
従って、リンクリストでは、ノードを識別するには、必ずアドレスを使うことが基本。
それが最も自然であり、高速であるから。
いつまでも、添え字番号で識別する方法しか理解できない人には、言っている意味が理解できない
だろう。

電気と磁気にもさまざまな双対関係がある。世界がある種の対称になっているから、
その際に、正確に対応する量を入れ替えてやら無ければならない。リンクリストでは
通し番号ではなくアドレスを使う。
そうしないと公平ではない。
2021/11/28(日) 23:11:50.99ID:tN4i8A7m
>>516
双対の定義は、独自に決めてよい。
2021/11/28(日) 23:13:05.79ID:tN4i8A7m
>>517
はあ？
ハッシュテーブルは、実質的にO(1)にとても近い速度で検索できるから
使われているんだが。
2021/11/28(日) 23:16:38.50ID:sDAG0wCq
>>514
それは嘘だと誰でもわかる
リンクリストの個別要素のアドレスに対応するものは配列の個別要素のアドレスでありハッシュマップの個別要素のアドレスである
そしてアドレスを持てばO(1)とトンデモを言い出すならば全てのデータ構造がO(1)となる
つまりリンクリストのO(1)は嘘
2021/11/28(日) 23:18:09.73ID:Z9Xk/5kf
>>513
>Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
>すっきり分かり易いので安全になる。動作が素直だし。

そんなに簡単だとかいうなら、試しに実装を見せてほし・・・
2021/11/28(日) 23:25:05.70ID:tN4i8A7m
>>521
お前が生徒だったら0点つけてやる。

そもそも、動的配列は要素数が内部容量を超える時にアドレスが時々変わって
しまうから、ID番号として基本的にアドレスは使えない。
それをすると、末尾追加するだけでも、定期的にID番号が変わってしまうので
その際にID番号として使っているアドレスを全部修正しないといけなくなるから。
しかし、アプリ内のID番号を全部修正するのは、効率免で良くない。
だから、配列だと要素の一番ましなID番号は添え字番号。

一方、リンクリストで最も効率の良いID番号は、アドレス。
しかも、リンクリストの場合、任意の場所への挿入、任意のノードの削除を
行っても、他のノードのアドレスは変わらないので、アドレスをID番号
として用いている限り、どんな操作をしてもID番号の修正が不要となる。
こんなによいID番号はないわけで、敢えて添え字番号をID番号に使うのは
不適切。
2021/11/28(日) 23:26:21.97ID:tN4i8A7m
>>522
Cの入門書で、リンクリストについて書いてあるもの読んで理解して、
頭が悪くなければ、そう自然に解釈できる。
根本的に馬鹿な人には無理かも。
2021/11/28(日) 23:38:14.43ID:ZOlCZyFx
rust は safe じゃなきゃ意味がない論者の人かな
2021/11/28(日) 23:43:54.48ID:tN4i8A7m
>>525
Cでは生ポインタ一個に対して、Rustは参照関連だけでも、20種類は下らないほど
色々な複雑な仕組みがあるのは、全て safe のためであるのに、safeでなくなったら
それこそCの圧勝になるが。
2021/11/28(日) 23:48:12.68ID:qezuw3R9
>>526
コーディングはゲロのようにめんどくさくなるが、
速度面では別にCにそう負けるもんではない
多分最適化しきれなくてほんのちょっと遅くなる部分はありそうだが
2021/11/28(日) 23:48:45.22ID:tN4i8A7m
>>477
それは、実はリンクリストも十分に局所性が有る。
というのは、追加するときには、リンクリスト全体のごく一部にバースト的に
挿入することが多いからだ。
そしてその時、ノードのアドレスは等間隔に並ぶ傾向が有るから。
2021/11/28(日) 23:49:16.38ID:tN4i8A7m
>>527
いや、今回の例では劇的に遅くなるケースがあるといってるんだ。
2021/11/28(日) 23:51:28.85ID:qezuw3R9
>>529
今回の例が何のことか把握してないが（QZが絡んでいるレスは読みづらすぎる）、
配列がどうたらとかの話なら別に配列なんていらんよ
2021/11/28(日) 23:52:03.44ID:j8Nrs0jp
結局この全員の合意とは無関係な些末な話ばかりだな

＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
2021/11/28(日) 23:53:36.07ID:tN4i8A7m
>>531
デタラメを何度も書くな。
2021/11/28(日) 23:55:06.43ID:j8Nrs0jp
>>532
もし反論があるならしてみたら？
2021/11/28(日) 23:58:27.96ID:qezuw3R9
極論だけど各メンバをUnsafeCellにしてunsafe使いまくれば、
shared XOR mutableルールぶち破れるから、
C/C++でできることはコーディングめんどくさくなるし安全性が結構悲しいことになるけど（でもCとかと同程度）
Rustでも不可能ってことはない

なんならCコードをRustコードに自動変換するやつすらあったような
成熟度は知らんが
2021/11/28(日) 23:58:30.48ID:tN4i8A7m
>>533
全て書いてるのに理解力が無いから理解できないだけ。
Rust信者は馬鹿ばかり。
2021/11/29(月) 00:02:50.56ID:g6qk7DwE
>>507
>Rustはそれを売りにしてるからだよ。
>C/C++は最初から諦めてる。

自分で C/C++ は安全じゃないから、って書いてるじゃん
それが結論でしょ
同じ安全性にしたら、同じになるだろ
2021/11/29(月) 00:05:09.36ID:HgRvzIV4
>>536
同じ安全性にする必要がない。
2021/11/29(月) 00:15:16.20ID:uM27l7Qv
前から別の人が指摘しているけど、
リンクドリストとは別に配列を用意してリンクドリストの要素へのアドレスを保持するからリンクドリストの任意の要素にはO(1)でアクセスできる
と主張しているが
そのリンクドリストに追加または削除するたびに配列の要素も追加か削除しないといけなくなる。
リンクドリストの任意の位置に追加/削除するのはO(1)だけど、配列の任意の位置に要素を追加/削除するのはO(1)じゃない。
だからリンクドリストと配列を組み合わせて使うとリンクドリストのメリット(任意の位置への追加/削除がO(1))が無くなってしまう。

その配列に静的配列を使うならリンクドリストの最大サイズを予想してあらかじめ大きな配列を用意しないといけない。
動的配列を使うな要素を追加したときにときどきヒープの再確保がおきる。
2021/11/29(月) 00:21:59.31ID:uYqg1Oz6
>>528
実際のメモリレイアウトがどうなるかは言語処理系のランタイムやlibcに依存すると思うのですが
例えばどの言語のどの処理系のどのランタイムを使使えばそうなることが確認されているのですか
2021/11/29(月) 00:23:38.13ID:HgRvzIV4
>>538
配列 + リンクリストの代わりに、リンクリスト + リンクリストにすれば解決するぞ。
2021/11/29(月) 00:24:11.08ID:HgRvzIV4
>>539
malloc()の仕組みから言ってそう考えられる。
2021/11/29(月) 00:30:08.36ID:4MgUQE5v
>>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を用いている
2021/11/29(月) 00:39:59.63ID:zo5XubVi
>>541
最初の初期化時に（あまりフラグメンテーションが発生していない状態で）複数要素追加する以外に追加がほとんど発生しないっていう前提ならそうかもね
でも一般にそうじゃないから連結リスト使うんじゃないの？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況