C++ vs Rust

**デフォルトの名無しさん** · 2021/04/24(土) 08:04:49.48

競え

**デフォルトの名無しさん** · 2021/11/26(金) 03:34:37.06

>>410
>>411を読め。
俺は正直に言っている。また、数学が昔から良くできるので、間違ってない。

**デフォルトの名無しさん** · 2021/11/26(金) 03:40:28.33

>>411
[補足]
実際、>>257 の独自実装は、Rustでも、任意の場所のノードをO(1)で
アクセスできるが、1アクセスあたりに一般的なノードサイズでは
20～50クロック掛かる。

悪いが、QZが出てくると話がややこしくなる。
かわいそうだが、単刀直入にいえば、QZは頭が良くないので、
レベルが全体に下がってしまう。
ようは、レベルが違う人は、教室を分けないとめちゃくちゃに成る。
レベルというのは熟練しているかどうかではなく、生まれつき決まっていて、
直すことが出来ない。
すまん。

**デフォルトの名無しさん** · 2021/11/26(金) 03:46:37.90

>>398
>・どの言語でもリンクリストでk番目を得るにはO(n)かかる
これは間違いである事は何でも説明した。例えば>>411。

>・そのk番目を配列で持てばO(1)だがそれはリンクリストではなく配列アクセスのコスト
これも間違いで、C、C++、Java、C#では、配列で持たずに、直接、ポインタや参照
で持っても、O(1)でアクセスできる。
Rustでは、借用規則が邪魔して、複数の読み書き参照を同時に永続的に保持できないので、
「k」のような番号でしか場所を維持できないため、そんな風になってしまうだけ。
だから、配列と番号を組み合わせてやっとO(1)にできる。
C、C++、Java、C#では、ポインタや参照を永続的にいつまでも保持できるので
配列を使わなくても O(1)でアクセスできる。
その際、「シーク」動作は必要ない。つまり、先頭から k 番目までを辿る必要が
なく、いきなり、k番目に 1 クロックでアクセスできる。
Rustでは、それが、一般的には出来ない。Rustでも、
局所的に1個のノードだけに限定すれば出来る。

**デフォルトの名無しさん** · 2021/11/26(金) 04:02:58.56

例えばこういうことだ。
リンクリストに、
ハンバーガー、りんご、みかん、ドーナツ、パイナップル
の5つを追加したとする。
C、C++、Java、C#では、追加した時に、どこかの5つの変数にこれらの
ポインタを残しておけば、あとから好きなタイミングで、どの
食べ物にも、一瞬でアクセスできる。C、C++では、1クロック。
1番目: ハンバーガー
2番目: りんご
3番目: みかん
4番目: ドーナツ
5番目: パイナップル

3番目のみかんにアクセスするのも、1クロック。
その後に、1番目のハンバーガーにアクセスするのも、1クロック。
その後に、4番目のドーナツにアクセスするのも、1クロック。

例えば、こうだ:
LinkedList ll;
p1 = ll.append("ハンバーガー");
p2 = ll.append("りんご");
p3 = ll.append("みかん");
p4 = ll.append("ドーナツ");
p5 = ll.append("パイナップル");

**デフォルトの名無しさん** · 2021/11/26(金) 04:03:19.69

>>415
[続き]

cout << p3->name; // 1 クロックで3番目のノードのみかんにアクセス。
p3->name="orange";　// 名前を英語に直す。アクセスには1クロックしかかからない。
cout << p1->name; // 1 クロックで1番目のノードのハンバーガーにアクセス。
p1->name="hamburger";　// 名前を英語に直す。アクセスには1クロックしかかからない。
cout << p4->name; // 1 クロックで4番目のノードのドーナツにアクセス。
p4->name="donuts";　// 名前を英語に直す。アクセスには1クロックしかかからない。

書き込みも変更も、アクセスには1クロックずつしか掛からない。
これが、Rustでは借用規則に引っかかるために出来ない。
その結果、標準実装では、k番目のノードに「シーク」する必要があるため、
O(k)や、O(N)の時間が掛かってしまう。
例えば:
cout << seek(ll, 3)->name; // O(N)の時間が掛かる!!
seek(ll, 3)->name="orange";　// O(N)の時間が掛かる!!

**デフォルトの名無しさん** · 2021/11/26(金) 04:10:09.81

>>411
＞2. 既に追加したノードを、もう一度アクセスする。
これカーソルでO(1)でできるって何度も言われてるやんけ
書き換え可能なカーソルを複数持つコードを書くのがめんどくさいってならわかるが

**デフォルトの名無しさん** · 2021/11/26(金) 04:12:10.51

>>416
[補足]
cout << aaa;
は、分かりにくいが、aaa の内容を表示する、という意味だと思って欲しい。
他の言語だと、print aaa; と書くことが多い。この点 C++ は異質であることは
認める。

**デフォルトの名無しさん** · 2021/11/26(金) 04:15:36.11

>>417
Rustでは、標準 Cursorでは、読み、書き、削除を出来る参照を同時に持つことは出来ない。
C、C++、Java、C#では、
ll.RemoveAt(p2);　// p2 のノードを削除。
もアクセス自体は1クロックで出来るし、今示したコードの好きな場所に
追加しても何の問題も無い。
p2は削除されているからアクセスできなくなるだけで、
他のポインタの値は変更されないので、それ以外は何もしなくても
そのままで良い。

**デフォルトの名無しさん** · 2021/11/26(金) 04:16:36.76

>>417
良く確認してくれ。
RustのCursorは、順番に辿ることはできるが、読み込みと書き込みと削除が
出来るタイプの参照を同時に複数記憶することは出来ない。

**デフォルトの名無しさん** · 2021/11/26(金) 04:18:59.29

>>419
標準(std)のLinkedListならそれはそう

前にも言ったような気がするが、
自前で作って内部構造にunsafecellを使えば、
不変参照を複数持っている状態でも書き換えが可能になる
例えば要素の追加時にそういうことをするカーソルを返せばよい
実装がめんどくさすぎるのは認める

**デフォルトの名無しさん** · 2021/11/26(金) 04:19:23.54

>>420
もっと言えば、C、C++、Java、C#の LinkedListは、
p2 の直後に「じゃがいも」ノードを追加した後、
p4 の直前に「トマト」ノードを追加するなどと言ったことも、
O(1)で出来る。しかも、O(1)と言っても、極限的に速くて、
C、C++の場合は、アクセスには1クロック。

こういうことが、Rustでは、Cursorを使っても出来ない。

**デフォルトの名無しさん** · 2021/11/26(金) 04:23:10.27

>>421
>>257のように、遅くするつもりなのか。
1ノードのアクセスに20～50クロックくらい掛かるが。
しかも、ダングリングポインタ、つまり、削除後にアクセスしてしまう
減少を防ぐことが出来なくなってるぞ。

**デフォルトの名無しさん** · 2021/11/26(金) 04:25:26.12

>>423
アンセーフ前提だから>>257とは全然違う
ダングリングも当然防げない（でもそれは他言語でもそう

**デフォルトの名無しさん** · 2021/11/26(金) 04:29:37.41

>>424
>>257 の実装でもそうだが、まだノードAに対する参照がどこかに残っている状態で、
ノードAの中身を削除できて、ノードAが使っていた要素を新規作成ノードのために
使用されてしまうね。

**デフォルトの名無しさん** · 2021/11/26(金) 04:42:30.98

>>420
[RustのCursorの補足]
・書き込み用のCursorを1個でも作ると、読み込み用のCursorは作れない。

はずだ。難しすぎてちゃんと理解して無いことは認める。

**デフォルトの名無しさん** · 2021/11/26(金) 04:49:17.40

>>421
std::cell::UnsafeCell なるものがあるのか。
Rustの参照は種類が多すぎ。
学んでも学んでもキリが無い。
しかも、1つずつをちゃんと理解するのが難しい。

**デフォルトの名無しさん** · 2021/11/26(金) 09:55:21.11

>>404
Pathといってもこちらから使うだけならAsRef<Path>だからStringと&strでも全く問題なくOsStringの存在すら知らなくていい
したがって出てくるのはDirEntryのみとなる
それも周り全てUTF8環境ばかりなのでinto_string()で全てSome(String)になるため結局OsStringを扱ったことは一度もない

**デフォルトの名無しさん** · 2021/11/26(金) 10:08:20.18

ミスったｗ
ResultのOk(String)ね

**デフォルトの名無しさん** · 2021/11/26(金) 12:12:39.51

>>428
いやいやせっかく標準ライブラリがWindowsでも動くよう苦労してくれてるのにそれを台無しにするなよ
個々のアプリで雑に対処するならともかくRust擁護派がRustの強みを否定してどうする

あと Path::file_name も Option<&OsStr> 返すしこれは利用頻度高い

**デフォルトの名無しさん** · 2021/11/26(金) 20:45:27.01

>>430
Rustはちゃんと考えられてるね
ただし自分はWindowsを使うことは100%ないから path.file_name().unwrap().to_str().unwrap() 等でいいし
他にも use std::os::unix::fs::MetadataExt して metadata.uid() 等することもある

**ハノン** ◆QZaw55cn4c · 2021/11/26(金) 21:02:52.31

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

あたりを考えるのが普通ですが、

「一度取得したノードの再アクセスコスト」を特に取り上げて考えるというのは、確かに rust の特殊性を示しているものといえそうですね…

>>413
生まれてきてすみません…

**デフォルトの名無しさん** · 2021/11/27(土) 13:14:46.65

>>432
また、話を混乱させている。
指摘していることが、全く的を外しているから。

**デフォルトの名無しさん** · 2021/11/27(土) 13:16:38.57

ちゃんと正確に議論されているのに、最後の最後でQZがめちゃくちゃな
ことを言い出す。それが最後に書かれたことによって、このスレに
後から来た人には「まとめ」の様に見えてしまうから、大迷惑。
全くまとめになってない、でたらめなことを書くから。

**デフォルトの名無しさん** · 2021/11/27(土) 13:19:47.46

ようは、秀才達が集まっているクラスで、一人だけレベルの低い人がいて、
秀才達が大体理解したのに、「まとめ」として、レベルの人が全く
デタラメなことを話す。それがQZ。
クラスの場合、みんなの雰囲気でQZがレベルが低いことが分かるので呆れられ、
無視され、せせら笑いが聞こえるが、ネットだとそれが分からないから困る。
現実世界では言葉にしなくても、ひそひそ場なしや、せせら笑いなどで分かるが
ねっとではそのような言外のコミュニケーションが出来ないから。

**デフォルトの名無しさん** · 2021/11/27(土) 13:22:32.48

>>435
どうせ、QZは、この文書の誤字脱字を発見して馬鹿にするんだろう。

誤字訂正:
誤:レベルの人が全く
正:レベルの低い人が全く

誤:ひそひそ場なしや
正:ひそひそ話や

誤:ねっとでは
正:ネットでは

**デフォルトの名無しさん** · 2021/11/27(土) 17:31:40.13

4レスも使って成果物も作れない評論家様はそびえ立つクソだからなぁ。

>>432のまとめが嫌なら、中身のない4レスのうち1レスを使ってご立派なまとめぐらい書き込んだら？

**デフォルトの名無しさん** · 2021/11/27(土) 17:48:27.29

たしかに4レスも使って人格批判しかしてね～

**デフォルトの名無しさん** · 2021/11/27(土) 19:00:17.29

ID:Y9o/DNQu
こいつがまとめを書けば話は終わりだな

**デフォルトの名無しさん** · 2021/11/27(土) 19:39:40.61

あわしろ氏はC++は使わないほうが良いと言ってる。

**デフォルトの名無しさん** · 2021/11/27(土) 20:00:10.09

C++をあまり使用してなさそうなよくわからないあわしろ氏でなく自分の意見出しなよ

**ハノン** ◆QZaw55cn4c · 2021/11/27(土) 20:25:46.13

>>433
すみません

>>434-436
生まれてきてすみません…

**デフォルトの名無しさん** · 2021/11/27(土) 21:09:50.54

>>434 >>442
お二人方どちらでもいいから
具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ
それが示せない限り机上の空論
もしコードが示されれば対応するRustのコードを出します

**デフォルトの名無しさん** · 2021/11/27(土) 22:07:53.33

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

**ハノン** ◆QZaw55cn4c · 2021/11/27(土) 22:11:02.52

>>443
＞具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ

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

>>432
＞リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る
において
①
＞すでに取得している指定ノードの削除
でいいですか？
②
データ構造は一方向リストでいいですか？

**デフォルトの名無しさん** · 2021/11/27(土) 22:20:41.20

>>445
一方向だと削除がO(1)じゃないから双方向が良いのでは

**ハノン** ◆QZaw55cn4c · 2021/11/27(土) 23:03:04.21

>>446
それは末尾または冒頭ノードの削除の話ですね
何が与えられていて、何を削除するのか、きちんと定義していただきたいです

**ハノン** ◆QZaw55cn4c · 2021/11/27(土) 23:04:36.52

>>446
失礼、あるいは特定ノードの上流ノードの探索の話もありますね
確かに双方向の方が楽チンですが、「ダブルポインタ」を使えば単方向でも処理できないわけではないです

**デフォルトの名無しさん** · 2021/11/27(土) 23:42:34.01

スマンが、余り言いたくないことだが、QZが出てくると話がとてもややこしくなる。

**デフォルトの名無しさん** · 2021/11/28(日) 00:05:23.91

まだやってたのか

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 02:32:25.17

>>449
当然でしょう

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

なのに、

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

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

さて実装実装…

**デフォルトの名無しさん** · 2021/11/28(日) 02:39:16.73

それがこのスレの目的ですから

**デフォルトの名無しさん** · 2021/11/28(日) 03:42:41.88

ある特定のエントリーを持つ変数はプログラム中に複数存在しうると議論中にも出ていたから
リファレンスカウンタは必須になるな

重要な点としては
コンストラクタやデストラクタやスマートポインタに隠れて曖昧にならないように
それらを使わずに実装すべきだ
そもそもC言語でもO(1)という話なのだから
まずはC言語かつ標準ライブラリのみ使用が今回のコード条件

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 04:07:17.98

>>453
ん？アンカーで示してください
今回はリファレンスカウンタは実装に含めないつもりです、まあ C で書くつもりですけど

**デフォルトの名無しさん** · 2021/11/28(日) 10:45:19.29

もうソース出せって意地悪言わないで、無視しときなよ
配列に格納し直すのが彼のアイデアの全てなんだから、つついても面白い話は出てこないよ

O(1)で追加・削除できる配列も作れる！って言い出したら、多分リンクリストを使うってことだよ

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 14:56:23.04

>>443
https://mevius.5ch.net/test/read.cgi/tech/1434079972/105
これでいかがでしょうか？

**デフォルトの名無しさん** · 2021/11/28(日) 17:32:59.07

>>443
C/C++では、ダングリングが発生するのを防ぐのはプログラマーの仕事だ。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 17:39:38.36

>>443
引き続いて双方向リストの場合
https://mevius.5ch.net/test/read.cgi/tech/1434079972/106
これでいかがでしょうか？

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

では C で実装願いますね
私は宿題を片付けましたので、ちゃんちゃん

**デフォルトの名無しさん** · 2021/11/28(日) 17:42:46.59

>>451
>>432では、あなた、そういうこと書いてなかったよね。
こういう議論でははっきり言わないと分からないよ。

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

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 17:47:22.55

>>459
もうリンクリストなんか不要で、最初からハッシュテーブル一本でやっていくべきなのでは？
なんでリンクリストとハッシュテーブルを両方使うのですか？

**デフォルトの名無しさん** · 2021/11/28(日) 17:51:06.30

>>460
ハッシュテーブルなんて全く使って無いぞ。
あなたはポインタの仕組みを理解して無いのか？

**デフォルトの名無しさん** · 2021/11/28(日) 17:54:05.88

QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
のではないか。
アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
基本的にハッシュ構造とは全く関係無い。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 17:58:02.00

>>461
失礼、>>444 とは別の方なんですね

でも、

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

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

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

って、どこにどういう形で保存するのです？

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 17:59:56.44

>>462
＞QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
＞のではないか。
>>456, >>458 で示した程度には理解しているつもりです

＞アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
で、そのアドレスをどのように管理するのですか？どのような形でどのようなデータ構造に格納するのですか？C/C++ で説明いただくと助かります

**デフォルトの名無しさん** · 2021/11/28(日) 18:32:54.89

>>463
>＞リンクリストで、一度作成したノードのアドレスはずっと保存する
>って、どこにどういう形で保存するのです？

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

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

・要は、ノードを識別するための数値が、配列では整数型の添え字番号であったところが、
　リンクリストでは、ポインタ型のアドレスになるというだけのこと。
　決して後者に置いては、通し番号を使ってはいけない。
　数学的には、次のような双対関係の様なものが存在していると考えられる:
　（配列, 添え字) <---> (リンクリスト, アドレス)
　QZを含めて、この双対関係を理解できておらず、
　（配列, 添え字) <---> (リンクリスト, 添え字)
　と間違って理解してしまっている人が多いことから、リンクリストでのランダムアクセス
　が O(N)などと謝った認識に至ってしまう人が多いと考えられる。
　しかし、正しく双対関係を理解すれば、O(1)であることが理解できよう。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 18:40:36.55

>>465
結論から申し上げれば、ここはプログラム板だから、適切なお題を設定してプログラムで例示いただけませんか？

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

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

**デフォルトの名無しさん** · 2021/11/28(日) 18:50:25.63

>>466
あなたはやはり馬鹿だな。
それをいうなら、配列も同じ。
配列の添え字番号を覚えておくのに、別の配列が必要になる。
お分かりかな？
あなたは、双対を全く理解出来て無い。

**デフォルトの名無しさん** · 2021/11/28(日) 18:53:09.31

>>465
それってリンクリストの意味ある？
なんのためにリンクリストにするんだ？

**デフォルトの名無しさん** · 2021/11/28(日) 18:57:11.39

Linked Listを使っているのにLinkを辿りたくないらしい

**デフォルトの名無しさん** · 2021/11/28(日) 18:58:57.15

アドレス保持してればなんでもランダムアクセスできるっていうなら
あらゆるデータ構造がランダムアクセス性を持つということになってしまうな

**デフォルトの名無しさん** · 2021/11/28(日) 19:16:56.34

>>466
Qちゃんお疲れ

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

それは色んな人がわりと最初のころから既にツッコミ済みなのだよ…
ようやく議論に追いついたねキミは

**デフォルトの名無しさん** · 2021/11/28(日) 19:42:21.78

>>470
実際、C言語などから高級言語にポインタの概念が入ってからはそうなった。
ただ、Rustはそうなって無いから問題なんだよ。

**デフォルトの名無しさん** · 2021/11/28(日) 19:42:59.18

>>462
ポインタの指す領域に1クロックでアクセスできるCPUなんてあるんですか？
ポインタの指す先がメモリにあるかキャッシュにあるかで異なりますがL1キャッシュにあっても数クロックかかるのではないかと思います

数クロックを争うような話をするなら実装がないと話にならないと思うので、まずは比較したい書く言語の実装を用意しましょうよ
既存のコードへのリンクで良いので

**デフォルトの名無しさん** · 2021/11/28(日) 19:43:39.06

やっぱり、数学が出来ない人は、双対の概念に脳が追いついてこないらしい。
双対という言葉の意味が分からなくても、生まれつき頭のいい人なら、
俺の言っている意味がわかるはずだ。

**デフォルトの名無しさん** · 2021/11/28(日) 19:44:13.37

>>473
キャッシュに載っていたらの話だ。

**デフォルトの名無しさん** · 2021/11/28(日) 19:44:50.23

>>472
任意のアドレスへのアクセスは本質的にunsafeだと思うのですが、safe rustでそれができないことにどのような問題があるのですか

**デフォルトの名無しさん** · 2021/11/28(日) 19:45:41.68

>>475
リンクリストは参照局所性が悪いのでキャッシュに載っていない確率が大きいのですが、本当に高速なのですか？

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 19:59:16.91

>>474
双対性にもいろいろありますよね…論理学上の双対命題（∩と∪、∀と∃の入れ替え）ならばその否定が証明できますが、そういう意味ですか？
それとも正十二面体と正二十面体の双対性ですか？
適当にペアにして双対と呼んでいるだけなのでは？

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 20:01:48.12

>>471
そうなんですね…

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 20:10:07.08

>>473
いや、突っ込みどころはそこではなくて、
「あるときは O(f) ランダウのオミクロンで話をしたかと思うと、次の瞬間、クロック数を問題にする」というバラバラな論理展開でしょう
ランダウでやるんだったら最後までランダウで統一してほしいのですが…

**デフォルトの名無しさん** · 2021/11/28(日) 20:33:56.21

>>480
ランダウ記号は、大まかな分類しか示せない。例えば、
O(N)は、N→∞ の時に、
O(N)/N < α (alpha)
のように有る正の実数αによって、「抑えられる」という意味しか示せないし、
O(1) < α (alpha)
であることしか意味しない。
だから、O(1)であることよりも、1クロックであることの方がずっと意味が強い。
なので、ちゃんと1クロックであると分かっているなら1クロックと書いた方がいい。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 20:51:47.55

>>481
ある数量に対応する空間的・時間的コストの依存状況を滔々と語っていたかと思うと、次の瞬間は実時間に関する話に都合のいいように鞍替えするのは論理的でない、といっているのです
実時間なら実時間、依存関係なら依存関係できっちり話をわけてほしいですね

**デフォルトの名無しさん** · 2021/11/28(日) 20:59:23.99

>>482
悪いが、お前が馬鹿なだけだ。
数学的には、O(1)と書くこともあれば、実クロックで書くこともあり、
混ぜたらいけないなんてことは無い。
ちゃんと理解していれば、混ぜても問題ない。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 21:06:52.79

>>483
「数学的」の定義を伺いたいものですが、それはさておき、実クロックなんて「おま環」な話をしても仕方がない場合も多いのですよ
今はキャッシュのヒット率で処理速度も大きく変わるから、実クロックによる考察なんてほとんど無意味です

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

あなたは、その二つの評価方法の意義の違い（「どちらが有意義か」）を知らないから「混ぜたらいけないなんてことはない」などとシレっといえるのですよ

**デフォルトの名無しさん** · 2021/11/28(日) 21:14:34.22

>>484
そうじゃないんだ。実際のクロック数の事ではなくて、マシン語で書いたときに
1命令だということなんだ。

**デフォルトの名無しさん** · 2021/11/28(日) 21:17:54.80

キャッシュの話なんかは状況が複雑すぎて議論を複雑にするだけで、本質を理解する
邪魔になる。
まず、それは横に置いておいて、基本を理解しないといけない。
キャッシュの影響についてはその次。

また、なら、最初から「1命令」と書いておけば良かったのに、という突っ込み
が予想されるが、1命令でも乗算命令なんかは13クロック(レイテンシ)以上かかるから
それとは区別するために1クロックと書いた。
キャッシュは複雑すぎて話が混乱するだけ。
ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
依存せず必ず言えることだから、そう書いた。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 21:20:07.26

>>485
命令数なんてもっと当てにならないですよ、内部で別形態に変換され並列に実行されたりするわけで、人手で最適化することは不可能なしろもの
そんな制御できないものを評価対象にしてもしかたがないのでは？

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 21:25:24.33

>>486
＞ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
＞依存せず必ず言えることだから、そう書いた。

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

どちらの方が有効範囲が広い有意義な評価法なのかを知らないから、ちゃんぽんにして話をしても不自然さを感じないじゃないですか、あなたは？

**デフォルトの名無しさん** · 2021/11/28(日) 21:26:27.36

>>487
そうでなくて、Rustでも、O(1)というものだけなら、作ろうと思えば作れるから
1クロックと書かざるを得なくなったんだよ。
Rustの場合は、O(1)でも、単なるポインタでは無く、配列を介すので、
乗算、足し算、境界チェックが入ってしまうのでトータルで20～50クロック
くらい掛かる。このうち、境界チェックだけは外せるかも知れないが。

**デフォルトの名無しさん** · 2021/11/28(日) 21:27:53.03

>>488
>>489 を見ろ。
「なぜあなたは文脈を考えて書かないんだ」
とはちみつ餃子にも指摘されてただろ。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 21:30:30.36

>>489
＞乗算、足し算、境界チェックが入ってしまう

C/C++ の配列とても乗算・足し算は入りますよ…
そんな瑣末な話とO(1), O(N) の話をちゃんぽんにしても不自然さを感じない感性に私は大いに疑問を感じます

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 21:34:48.65

>>490
よくご存知ですね…
まあ、今日は基本的なデータ構造を基本的な言語を使用して白紙からコーディングする機会を下さったあなたには感謝してますよ、久々に脳細胞を使ったのでちょっといい気分です

**デフォルトの名無しさん** · 2021/11/28(日) 21:40:43.94

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の場合とは
雲泥の差である。

**デフォルトの名無しさん** · 2021/11/28(日) 21:42:26.92

俺は 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.57

>>491
お前はアホか。
リンクリストの場合は、乗算が入らないんだよ。

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

従って、リンクリストの方が一般的にはアクセスが速い。
リンクリストは、1クロック位、配列の場合は、要素が一般のバイト数の場合は、
14～36クロック位。

**デフォルトの名無しさん** · 2021/11/28(日) 21:47:47.53

>>494
>Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
そうじゃない。
Rustでも、insert, remove 自体は、標準実装でも O(1)で行える。
ところが、アクセスが、標準実装では、借用規則のために複数の
読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
辿る必要があるため、O(N)かかる。

特殊な独自実装をすると、アクセスがオーダー的にはO(1)で出来るが、
特殊実装な故に、>>493 の後半のようになってしまい、
20～50クロック位かかる。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 21:49:24.66

>>494
読みました
私の場合は双方向リストを循環させ、始点のみをポイントすることとしましたが、結果として記述はあまり簡単にはならなかったですね、うーむ

**デフォルトの名無しさん** · 2021/11/28(日) 21:56:03.25

すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。

**デフォルトの名無しさん** · 2021/11/28(日) 21:56:11.42

すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。

**デフォルトの名無しさん** · 2021/11/28(日) 21:56:13.54

すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。

**デフォルトの名無しさん** · 2021/11/28(日) 21:57:51.47

remove メソッドにバグがあった (head, tail を更新していなかった) ので一応修正。
https://wandbox.org/permlink/GlDCsezlcix3aJvi

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

>>497
双方向リンクリストは始点と終了をペアで持つという固定観念があったので、その発想はなかったです。

**デフォルトの名無しさん** · 2021/11/28(日) 22:02:54.87

>>501
>なるほど。アクセス時に通し番号的な物が必要になるのであれば
>insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
先頭や末尾では無い途中のinsert、removeであれば、あなたの言うとおり。
追加する直前のノードにたどり付くまでに一般的にはO(N)の時間が掛かる。
ただまあ、末尾追加や先頭追加と、末尾削除、先頭削除なら、RustでもO(1)で
出来るだろう。
なお、Cursorを使えば、よくあるケースだけは高速に行えるようになっているかも知れないが。
あくまでも良くあるケースだけは、unsafeを使って特別対応しているだけ。
複雑な一般的なケースでは、やはり、O(N)かかってしまう。
その意味で、あなたの言っていることは正しい。

**デフォルトの名無しさん** · 2021/11/28(日) 22:13:58.18

いつまで例のVecを使った謎LinkedList実装にこだわっているのだろう

**デフォルトの名無しさん** · 2021/11/28(日) 22:17:12.75

>>503
こだわっているというか、あれは、オーダー的にはCと同じく、ほとんど全ての
動作をO(1)で出来てしまうリンクトリストをRustでも出来ているから、
注目に値する。
ただし、O(1)と言っても、実際には遅い。
また、Read After Delete、ダングリングポインタに相当するものがRustでも
生じる。たとえ、safeモードで書いても。

**デフォルトの名無しさん** · 2021/11/28(日) 22:20:39.78

なんでRustだけsafe前提なんすか？

**デフォルトの名無しさん** · 2021/11/28(日) 22:21:32.31

>>504
要素追加でバッファ超えると配列全体をコピーするけどO(1)なんだ？
いいのかそれで？

**デフォルトの名無しさん** · 2021/11/28(日) 22:26:36.40

>>505
Rustはそれを売りにしてるからだよ。
C/C++は最初から諦めてる。

>>506
その指摘は正しい。
平均的にはO(1)だが、スパイク状に(不定期に)O(N)のコピー動作が入ってしまう。

**ハノン** ◆QZaw55cn4c · 2021/11/28(日) 22:29:15.25

>>501
私のやり方でよかったことは、prev/next の無矛盾性のチェックが簡単に書けることくらいでした、他は複雑になってしまった…

**デフォルトの名無しさん** · 2021/11/28(日) 22:50:50.98

>>507
売りにしてるいうても結構厳しい制限だからデータ構造に直結するようなコードはsafeのみじゃ無茶だぞ
連結リストのようにユーザ側もダングリングとか多重参照とか気をつけなきゃいけないタイプのものは、
safeの範囲じゃ回りくどいことやるハメになるか、そもそも本当に無理になるかだ

**デフォルトの名無しさん** · 2021/11/28(日) 22:53:17.54

>>496
>ところが、アクセスが、標準実装では、借用規則のために複数の
>読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
>先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
>辿る必要があるため、O(N)かかる。

そうなんだ
でもこれってC/C++でもメモリ安全で、スレッドセーフとかにしたら同じにならん？

**デフォルトの名無しさん** · 2021/11/28(日) 22:59:54.62

自分はがんばって数学の勉強をしてきたので自分の考えは絶対に正しい、間違うはずがないと思いこむ。
そうなると一度間違った考え(リンクドリストの任意の要素にO(1)でアクセスできる)を持ってもそれを間違った考えとは気づかずにその間違いを補強するようなチグハグな考え方をするようになる。
反ワクチンのようなトンデモ科学にはまっちゃう人に周囲の人がいくら正しい科学知識で説得しても自分の考えに疑問を持つどころか、自分の考えは絶対に正しい、周りのやつらは頭がおかしいと思いこんでしまう。

自分の考えが間違うこともあるのではないかと謙虚になることも重要だということだね。

**デフォルトの名無しさん** · 2021/11/28(日) 23:00:17.08

まずポインタで持てば1クロックは明らかに嘘
今後はクロックという言葉を使うのはやめなさい

次にポインタで持てばリンクリストはO(1)も明らかにおかしい
例えばハッシュテーブルもバイナリツリーもO(1)になってしまう