- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 396 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 16:04:22.18 ID:S6TYxgmH.net]
- >>386
嘘を書くな。
- 397 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 16:33:56.78 ID:sK32tKJd.net]
- >>389
特に嘘はないと思うけど
stdのLinkedListがちょっと融通利かないところはあるけど
- 398 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 16:34:58.88 ID:ug4Dh0aR.net]
- >>386
様々な言語の中でRustだけ linked list の任意の要素にO(1)でアクセスできないというのは嘘だった
も追加で
- 399 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 20:15:57.40 ID:SwFLZgNz.net]
- macro記述と言語がまるで別言語、いちいちウザいアトリビュート。letは固定を意味するのではなく式展開
何種類もある「文字列」、それに生えている似たようで意味が違ういっぱいのfn（これはトレイトのせい）
わざと敷居を高くしてるとしか思えん
- 400 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 20:31:51.42 ID:6PNOZvLH.net]
- >>392
> letは固定を意味するのではなく式展開
letは常に成功する構造パターンマッチングにすぎないよ
if letは成功か失敗か不明な構造パターンマッチング
今どきの言語ならば左辺値にパターンが書けるのが普通
> 何種類もある「文字列」
文字列はヒープにあり伸縮可能なStringとそうでないstrの2種類しかないよ
ヒープを意識する言語なら2種類ある
あとは文字列の参照として&strがあってその本体はヒープにあろうがなかろうが同じ扱いできるだけ
- 401 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 20:38:50.41 ID:pEcDGUra.net]
- CString
CStr
OsString
OsStr
- 402 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 20:58:33.97 ID:88pS2ZzI.net]
- >>394
それはRustの文字列ではなく単なるFFI
通常のプログラミングでは登場しない
- 403 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 21:05:41.06 ID:NJM+Y62L.net]
- >>391
「任意の」
の定義をしないと無意味な主張
- 404 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 21:16:25.34 ID:vljrMlfk.net]
- じゃあ何種類もあるじゃない、全部が汚いことへの言い訳にしか聞こえない
- 405 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 21:25:33.18 ID:88pS2ZzI.net]
- まとめ
・どの言語でもリンクリストでk番目を得るにはO(n)かかる
・そのk番目を配列で持てばO(1)だがそれはリンクリストではなく配列アクセスのコスト
・リンクリストのk番目を保持する配列を維持するには削除挿入のたびにO(n)の移動が生じる
・これらは言語に依存しない
- 406 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 21:33:37.11 ID:/vPuyV+m.net]
- >>397
言語の汚さというよりもOSなどの環境が抱える複雑さをそのまま見せたらそうなったのでは
- 407 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 21:38:29.78 ID:beDf3C1p.net]
- それが低いレイヤーをやるってことだわな。
それを他の言語のせいにするrust野郎はクソってことだよ。
- 408 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 22:13:10.27 ID:88pS2ZzI.net]
- 誤解している人が居るようなので正しい情報
・Rustの通常のプログラミングでCStrやOsStrが出てくることはない
・そこでファイルやディレクトリやソケットを操作してもCStrやOsStrは出てこない
・つまりRustで使う文字列はstrとヒープのStringの2種類しかない
・CStrやOsStrはFFIを書く人のみが用いるのでほとんどの人には無縁
- 409 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 22:18:29.72 ID:3Rcu7yrD.net]
- 「通常」の定義は？
- 410 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 22:30:32.62 ID:6PNOZvLH.net]
- >>402
Rustで未だ対応していない未知のものが出現した時にその対応する人だけがCStrやOsStrを用いる
その時のその人を除き、全ての人はCStrやOsStrなんか知らなくてもRustでプログラミング可能
- 411 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 23:14:44.56 ID:/vPuyV+m.net]
- >>401
Pathの操作してるとOsStrは普通に出てくるのでFFIでしか出てこないというのは嘘
- 412 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 23:16:52.42 ID:/vPuyV+m.net]
- 他の言語がごまかしている箇所を正確に扱えるのがrustの強みでもありめんどくさいところでもある
- 413 名前：デフォルトの名無しさん mailto:sage [2021/11/25(木) 23:45:28.39 ID:sK32tKJd.net]
- Rust擁護マンでも標準の文字列（String/str）以外がFFIのみというのはさすがに筋悪に見える
Rustで標準の文字列をUTF8のバイト配列（ヌル文字終端不採用）としたことによる弊害って側面が割と強い
でも他言語みたいにそこしっかりしないとなるとそれはそれでめんどくさいから結局のところトレードオフ
でもOsStrめんどいわ
- 414 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 00:54:57.87 ID:Ye0bskEh.net]
- 文字列エンコードを規定しないとそれはそれで移植性に問題あるし難しいところ
WTF-8なる概念必要になったりとにかくWindowsが悪いという気はする
- 415 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 03:23:02.14 ID:FqYYA0QW.net]
- >>391
嘘を書くな。
正しくは、Rustは配列を使って独自実装しないとO(1)には出来無い事が明らかに成った。
参照だと借用規則で出来なくて、配列の添え字番号だと単なる整数なので借用規則の
適用範囲外だからできる。添え字番号をポインタの代わりに使って、独自に
リンクトリストを実装することで初めて、O(1)になる。
しかし、O(1)になっても、「係数」が大きくなり、1アクセスに20クロックくらいかかる。
配列の範囲チェックと、配列アクセスのための乗算と加算が追加で必要になるため。
一方、C、C++、C#、Javaではそんなことしなくても最初からO(1)。
- 416 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 03:24:19.18 ID:FqYYA0QW.net]
- >>398
お前みたいなやつは、一度殴ってやりたい。
匿名掲示板だからと言って、でたらめを書くな！！
ばか者！
- 417 名前：ハノン mailto:sage [2021/11/26(金) 03:25:10.11 ID:xSrpn+m5.net]
- >>408
C/C++ のリンクリストがどうして O(1) なんですか？
- 418 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 03:33:50.05 ID:FqYYA0QW.net]
- >>398は、数学できない。
細かい点が全然分かって無い。
リンクリストでは、「k番目にアクセスする」と言っても、次の二種類ある。
1. (乱数などで)整数 k
- 419 名前：を与えられて、ノードを探す。
この場合、どうしても、O(N)、O(k)の時間がかかる。
2. 既に追加したノードを、もう一度アクセスする。
これには、C、C++、C#、Javは、O(1)しかかからない。
しかも、C、C++だと 1 クロック。
Rustだと配列と添え字番号を使って独自実装しなければ、
基本的にO(N)、O(k)かかる。独自実装した場合、
O(1)ではあるが、20～50クロックくくらいかかる。
[] - [ここ壊れてます]
- 420 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 03:34:37.06 ID:FqYYA0QW.net]
- >>410
>>411を読め。
俺は正直に言っている。また、数学が昔から良くできるので、間違ってない。
- 421 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 03:40:28.33 ID:FqYYA0QW.net]
- >>411
[補足]
実際、>>257 の独自実装は、Rustでも、任意の場所のノードをO(1)で
アクセスできるが、1アクセスあたりに一般的なノードサイズでは
20～50クロック掛かる。
悪いが、QZが出てくると話がややこしくなる。
かわいそうだが、単刀直入にいえば、QZは頭が良くないので、
レベルが全体に下がってしまう。
ようは、レベルが違う人は、教室を分けないとめちゃくちゃに成る。
レベルというのは熟練しているかどうかではなく、生まれつき決まっていて、
直すことが出来ない。
すまん。
- 422 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 03:46:37.90 ID:FqYYA0QW.net]
- >>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個のノードだけに限定すれば出来る。
- 423 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:02:58.56 ID:FqYYA0QW.net]
- 例えばこういうことだ。
リンクリストに、
ハンバーガー、りんご、みかん、ドーナツ、パイナップル
の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("パイナップル");
- 424 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:03:19.69 ID:FqYYA0QW.net]
- >>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)の時間が掛かる!!
- 425 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:10:09.81 ID:r6ugNRE0.net]
- >>411
＞2. 既に追加したノードを、もう一度アクセスする。
これカーソルでO(1)でできるって何度も言われてるやんけ
書き換え可能なカーソルを複数持つコードを書くのがめんどくさいってならわかるが
- 426 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:12:10.51 ID:FqYYA0QW.net]
- >>
- 427 名前：416
[補足]
cout << aaa;
は、分かりにくいが、aaa の内容を表示する、という意味だと思って欲しい。
他の言語だと、print aaa; と書くことが多い。この点 C++ は異質であることは
認める。 []- [ここ壊れてます]
- 428 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:15:36.11 ID:FqYYA0QW.net]
- >>417
Rustでは、標準 Cursorでは、読み、書き、削除を出来る参照を同時に持つことは出来ない。
C、C++、Java、C#では、
ll.RemoveAt(p2); // p2 のノードを削除。
もアクセス自体は1クロックで出来るし、今示したコードの好きな場所に
追加しても何の問題も無い。
p2は削除されているからアクセスできなくなるだけで、
他のポインタの値は変更されないので、それ以外は何もしなくても
そのままで良い。
- 429 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:16:36.76 ID:FqYYA0QW.net]
- >>417
良く確認してくれ。
RustのCursorは、順番に辿ることはできるが、読み込みと書き込みと削除が
出来るタイプの参照を同時に複数記憶することは出来ない。
- 430 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:18:59.29 ID:r6ugNRE0.net]
- >>419
標準(std)のLinkedListならそれはそう
前にも言ったような気がするが、
自前で作って内部構造にunsafecellを使えば、
不変参照を複数持っている状態でも書き換えが可能になる
例えば要素の追加時にそういうことをするカーソルを返せばよい
実装がめんどくさすぎるのは認める
- 431 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:19:23.54 ID:FqYYA0QW.net]
- >>420
もっと言えば、C、C++、Java、C#の LinkedListは、
p2 の直後に「じゃがいも」ノードを追加した後、
p4 の直前に「トマト」ノードを追加するなどと言ったことも、
O(1)で出来る。しかも、O(1)と言っても、極限的に速くて、
C、C++の場合は、アクセスには1クロック。
こういうことが、Rustでは、Cursorを使っても出来ない。
- 432 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:23:10.27 ID:FqYYA0QW.net]
- >>421
>>257のように、遅くするつもりなのか。
1ノードのアクセスに20～50クロックくらい掛かるが。
しかも、ダングリングポインタ、つまり、削除後にアクセスしてしまう
減少を防ぐことが出来なくなってるぞ。
- 433 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:25:26.12 ID:r6ugNRE0.net]
- >>423
アンセーフ前提だから>>257とは全然違う
ダングリングも当然防げない（でもそれは他言語でもそう
- 434 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:29:37.41 ID:FqYYA0QW.net]
- >>424
>>257 の実装でもそうだが、まだノードAに対する参照がどこかに残っている状態で、
ノードAの中身を削除できて、ノードAが使っていた要素を新規作成ノードのために
使用されてしまうね。
- 435 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:42:30.98 ID:FqYYA0QW.net]
- >>420
[RustのCursorの補足]
・書き込み用のCursorを1個でも作ると、読み込み用のCursorは作れない。
はずだ。難しすぎてちゃんと理解して無いことは認める。
- 436 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 04:49:17.40 ID:FqYYA0QW.net]
- >>421
std::cell::UnsafeCell なるものがあるのか。
Rustの参照は種類が多すぎ。
学んでも学んでもキリが無い。
しかも、1つずつをちゃんと理解するのが難しい。
- 437 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 09:55:21.11 ID:5+U4u14D.net]
- >>404
Pathといってもこちらから使うだけならAsRef<Path>だからStringと&strでも全く問題なくOsStringの存在すら知らなくていい
したがって出てくるのはDirEntryのみとなる
それも周り全てUTF8環境ばかりなのでinto_string()で全てSome(String)になるため結局OsStringを扱ったことは一度もない
- 438 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 10:08:20.18 ID:5+U4u14D.net]
- ミスったｗ
ResultのOk(String)ね
- 439 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 12:12:39.51 ID:Ye0bskEh.net]
- >>428
いやいやせっかく標準ライブラリがWindowsでも動くよう苦労してくれてるのにそれを台無しにするなよ
個々のアプリで雑に対処するならともかくRust擁護派がRustの強みを否定してどうする
あと Path::file_name も Option<&OsStr> 返すしこれは利用頻度高い
- 440 名前：デフォルトの名無しさん mailto:sage [2021/11/26(金) 20:45:27.01 ID:MbvsChzk.net]
- >>430
Rustはちゃんと考えられてるね
ただし自分はWindowsを使うことは100%ないから path.file_name().unwrap().to_str().unwrap() 等でいいし
他にも use std::os::unix::fs::MetadataExt して metadata.uid() 等することもある
- 441 名前：ハノン mailto:sage [2021/11/26(金) 21:02:52.31 ID:xSrpn+m5.net]
- >>411
リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る場合には
ノードの追加
ノードの検索
すでに取得している指定ノードの削除
あたりを考えるのが普通ですが、
「一度取得したノードの再アクセスコスト」を特に取り上げて考えるというのは、確かに rust の特殊性を示しているものといえそうですね…
>>413
生まれてきてすみません…
- 442 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 13:14:46.65 ID:Y9o/DNQu.net]
- >>432
また、話を混乱させている。
指摘していることが、全く的を外しているから。
- 443 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 13:16:38.57 ID:Y9o/DNQu.net]
- ちゃんと正確に議論されているのに、最後の最後でQZがめちゃくちゃな
ことを言い出す。それが最後に書かれたことによって、このスレに
後から来た人には「まとめ」の様に見えてしまうから、大迷惑。
全くまとめになってない、でたらめなことを書くから。
- 444 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 13:19:47.46 ID:Y9o/DNQu.net]
- ようは、秀才達が集まっているクラスで、一人だけレベルの低い人がいて、
秀才達が大体理解したのに、「まとめ」として、レベルの人が全く
デタラメなことを話す。それがQZ。
クラスの場合、みんなの雰囲気でQZがレベルが低いことが分かるので呆れられ、
無視され、せせら笑いが聞こえるが、ネットだとそれが分からないから困る。
現実世界では言葉にしなくても、ひそひそ場なしや、せせら笑いなどで分かるが
ねっとではそのような言外のコミュニケーションが出来ないから。
- 445 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 13:22:32.48 ID:Y9o/DNQu.net]
- >>435
どうせ、QZは、この文書の誤字脱字を発見して馬鹿にするんだろう。
誤字訂正:
誤:レベルの人が全く
正:レベルの低い人が全く
誤:ひそひそ場なしや
正:ひそひそ話や
誤:ねっとでは
正:ネットでは
- 446 名前：デフォルトの名無しさん [2021/11/27(土) 17:31:40.13 ID:v9cw8FEl.net]
- 4レスも使って成果物も作れない評論家様はそびえ立つクソだからなぁ。
>>432のまとめが嫌なら、中身のない4レスのうち1レスを使ってご立派なまとめぐらい書き込んだら？
- 447 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 17:48:27.29 ID:d/xEnnZB.net]
- たしかに4レスも使って人格批判しかしてね～
- 448 名前：デフォルトの名無しさん mailto:sage [2021/11/27(土) 19:00:17.29 ID:tDXnKU/S.net]
- ID:Y9o/DNQu
こいつがまとめを書けば話は終わりだな
- 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系だとアーキテクチャに
依存せず必ず言えることだから、そう書いた。
|
 |
