C++ vs Rust

[表示 : 全て最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 901- 1001- 2ch.scのread.cgiへ]
Update time : 02/27 03:27 / Filesize : 361 KB / Number-of Response : 1025
[このスレッドの書き込みを削除する]
[＋板最近立ったスレ＆熱いスレ一覧 : ＋板最近立ったスレ／記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

C++ vs Rust

1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]: 競え
449 名前：デフォルトの名無しさん [2021/11/27(土) 19:39:40.61 ID:SLaQ3CeJ.net]: あわしろ氏はC++は使わないほうが良いと言ってる。
450 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 20:00:10.09 ID:WDqbhltk.net]: C++をあまり使用してなさそうなよくわからないあわしろ氏でなく自分の意見出しなよ
451 名前：ハノン mailto:sage [2021/11/27(土) 20:25:46.13 ID:bCVlBsXA.net]: >>433
すみません

>>434-436
生まれてきてすみません…
452 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 21:09:50.54 ID:riEP2Tv6.net]: >>434 >>442
お二人方どちらでもいいから
具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ
それが示せない限り机上の空論
もしコードが示されれば対応するRustのコードを出します
453 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 22:07:53.33 ID:kID5mUHa.net]: オブジェクトのアドレスをハッシュテーブルで持たせて、双方向リストで実装。
454 名前：ハノン mailto:sage [2021/11/27(土) 22:11:02.52 ID:bCVlBsXA.net]: >>443
＞具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ

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

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

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

なのに、

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

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

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

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

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

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

では C で実装願いますね
私は宿題を片付けましたので、ちゃんちゃん
469 名前：デフォルトの名無しさん mailto:sage [2021/11/28(日) 17:42:46.59 ID:4++rc1oJ.net]: >>451
>>432では、あなた、そういうこと書いてなかったよね。
こういう議論でははっきり言わないと分からないよ。

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

でも、

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

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

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

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

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

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

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

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

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

いいえ、リンクリストの各ノードのアドレスは、リンクリスト内で調達するのならば、O(N) でしか取得できないものですよ
あなたはリンクリスト以外の何か別のデータ構造を使ってリンクリストのアドレスを管理しようとしているようですが、
ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
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))が無くなってしまう。

その配列に静的配列を使うならリンクドリストの最大サイズを予想してあらかじめ大きな配列を用意しないといけない。
動的配列を使うな要素を追加したときにときどきヒープの再確保がおきる。

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef