21/04/24 08:04:49.48 nPKzA798.net
競え
2:デフォルトの名無しさん
21/04/24 09:03:31.43 CqGuC/ho.net
何で？
3:デフォルトの名無しさん
21/04/24 09:10:09.42 MAG7Rri7.net
どちらも変なプライド拗らせたアホしかいない印象
4:デフォルトの名無しさん
21/04/24 10:50:18.68 N1eYD/7j.net
C++: ｶﾐｿﾘ
Rust: 安全ｶﾐｿﾘ
5:デフォルトの名無しさん
21/04/24 11:18:00.79 gMqF1SGc.net
別に～
裏方一緒だし
6:デフォルトの名無しさん
21/04/25 11:37:52.88 vJWG11Gh.net
一概にどちらが優れているとは言えないことではあるが、
代入やコンストラクタが、moveとcopyのどちらになるかについて、Rustの
方が自動化が進んでいると思いがちだが、実際は、
C++は、関数の戻り値が構造体型/クラス型になっている場合に関しては
RVO(Return Value Optimization)が働き、右辺が
クラス名(実引数列)
の形式の一時オブジェクトである場合には、moveが選ばれるが、それ以外は、
概ねcopyになるので、ある意味では「自動選択」しているのに対し、
Rustでは、x = y と書いた場合、原則的には「デフォルトmove」の規則に
従い、copyしたい場合は、右辺をy.clone()と書くことになっていて、
「手動選択」を採用している。
C++は、どう書いた場合にmoveになり、どう書いた場合にcopyになるかを全て把握するのは
難しくて、C++の仕様が勉強不足だと勘違いや見落としが発生する可能性があるのに対し、
Rust方式は、moveとcopyのどちらになるかが明確なので混乱が少ないと言えるかも知れない。
つまり、このことに関しては、児童選択より手動選択の方が安心感があるかも知れない。
意見を求む。
7:デフォルトの名無しさん
21/04/25 11:57:11.84 Ef2Yns/P.net
Copy trait実装してたら暗黙的に実行されるわ。
とはいえc++のそれよりかは分かり易いけど。
8:デフォルトの名無しさん
21/04/25 13:18:15.15 rtrHqrCb.net
[C++]
xやfunc()の戻り値が CPerson というクラス型の場合、
10. x = y; // copy代入。yの中味はxにコピーされる。yのデータも保存。
11. x = std::move(y) // move代入。yのデータは破棄される。
12. x = func(a); // move代入または、RVOが働いてmove代入以上に速い動作になる。
関数の戻り値だけは特別に処理されている。
[Rust]
(CPerson がCopy traitを実装して無い場合に限定)
20. x = y; // move。以後、y は使用できなくなる。これが故にデフォルトmoveと呼ばれる。
21. x = y.clone(); // copy。以後もyは使用できる。
22. x = func(a); // move。20.と同じ規則に従っているだけで関数の戻り値だから特別では無い。
C++の場合、12.で関数だけは特別処理されているのに対し、Rustの22では
関数でも特別処理されているわけではなく、20.のデフォルトmoveの原則に従っているだけ
のように見える。
C++の場合、11. では、std::move()で修飾すると、なぜか、10. で修飾しなかった場合
より、実行されるCPUの処理が「減る」。ソースコードで関数の様なものを
追加した方が追加しなかったときよりCPUの処理が減ってしまうのは、どことなく直感に
反する。
一方、Rustの21と20を比較すると、.clone()を書いた方が書かなかったときより、
実行されるCPUの処理が増えるので、直感的である。
この場合、.clone()を書いたことで「コピーするためにCPUの処理が追加された」という
直感に沿った感じになるから。
C++の場合、std::move()と書くと「std::move()という関数の様なものを書いたのに、
なぜか、CPUの処理が減る」という違和感を感じるようになる。
9:デフォルトの名無しさん
21/04/25 17:13:07.94 In1fvQYU.net
要はRustの代入ってmemcpyで、単純なmemcpyされると困るデータ(!Copy)の場合右辺がinvalidate(move)され使えなくなる
って理解がシンプルなのかな
10:デフォルトの名無しさん
21/04/25 18:00:12.34 S2tV53BX.net
>>9
x = y の時、
結果的にはほとんどmemcpy(&x,&y,サイズ)に近い動作になっているかもしれないな。
ただ、右辺yの構造体メンバの中にRc<T>のような複雑なものが入っている場合、
結果は単純コピーのようになったとしても、コンパイラはもっと丁寧に処理
しているのではなかろうか。
11:デフォルトの名無しさん
21/04/26 01:44:08.26 +85I2LX6.net
>>10
move は memcpy だよ
Rc も実体はヒープへのポインタだから memcpy で問題ない
memcpy してはいけない例としては async fn みたいな自己参照構造体などがあるけど
Pin をうまく使うことで変な状態にならないようにしている
12:デフォルトの名無しさん
21/04/26 17:23:54.42 92SW7900.net
c++に批判的な姿勢で知られるlinusがなぜrustにはwelcomeな態度取ってるのかが理解できない
rustだってメモリ安全性がなければc++みたいなもんだろ
13:デフォルトの名無しさん
21/04/26 17:27:49.70 oHxAx7LN.net
言うほどwelcomeか？
14:デフォルトの名無しさん
21/04/26 17:29:26.57 92SW7900.net
>>13
貶すまではいってないじゃん
15:デフォルトの名無しさん
21/04/26 18:48:21.42 pZ6mft9e.net
あわしろ氏もRustは凄いって言ってましたね。
C++をあまり好きじゃないところも同じ。
16:デフォルトの名無しさん
21/04/26 20:08:40.47 cN+lbm0F.net
>>12
c++にもだいぶ甘くはなってるよ。
ただそれでもrustに対してもそこまで容認的ではない。
試しにドライバー書いてみれば？って言って試させてるが、まだまともには考えてないわ。
URLﾘﾝｸ(lkml.org)
17:デフォルトの名無しさん
21/04/26 20:27:04.95 92SW7900.net
>>16
むしをrust側に対して例外処理の方法をカーネル内での往来の方法に変更してくれって促しているように見えるんだけど
導入したがってるやんけ
18:デフォルトの名無しさん
21/04/26 20:51:20.12 cN+lbm0F.net
>>17
続きを読めば？どういう流れかわかるから。
19:デフォルトの名無しさん
21/04/26 21:27:22.23 92SW7900.net
>>18
続きで懐疑的な立場取ってんのlinusじゃなくね？
20:デフォルトの名無しさん
21/04/26 22:53:32.32 cN+lbm0F.net
>>19
話の流れは大体予想できてただろうなという受け答えだろ。
んでもって実際、発案者自らmoonshot言うとるわ。
少しは内容を読んでくれ、なんで一から十まで説明しなきゃならんのか。
21:デフォルトの名無しさん
21/04/26 23:32:00.78 92SW7900.net
>>20
じゃあレスすんなよカス
22:デフォルトの名無しさん
21/04/26 23:47:01.17 cN+lbm0F.net
だから読めって。。文盲なんか？
23:デフォルトの名無しさん
21/04/27 00:14:36.96 H90KgUtd.net
>>20
moonshotって言ってるの割り込みコンテキストでallocator呼び出すことをコンパイル時にチェックできるようにしたいという話では
現実的には関数ごとにどのコンテキストで呼び出せるものなのかタグ付けしてるとかなんとか
綺麗じゃないけど、まあ動くわなという解決策
つまみ食いしかしてないから読み違えてるかも知れないけど
これをもってlinuxカーネルにrust取り込むのを否定するような話ではないようにみえた
他にもmoonshotって言ってる箇所ある？
24:デフォルトの名無しさん
21/04/27 01:12:51.08 VJIOoOWO.net
一通り読んだけど他にmoonshotって言ってるとこはなかったような。
25:デフォルトの名無しさん
21/04/27 08:00:23.09 /+bIFNU8.net
>>23
あのね。。書けばそうなるってものじゃなくてそれを実装しなきゃならんのよ。。
コンパイラにそういったコンテクストを判断させるのがめちゃくちゃ難しいっていってるでしょ？
なんでそんなに読み取れないの？
26:デフォルトの名無しさん
21/04/27 15:37:12.22 Nn42Sot0.net
>>25
当面はdoc commentにannotation書いて済ませておくって言ってるやん
何はともあれ大局的にはrustをlinux kernelに取り込む方向へ進んでいくことには間違いない
27:デフォルトの名無しさん
21/04/27 16:10:45.63 /+bIFNU8.net
>>26
だからそのコードじゃpanic捉えきれねーからカーネルに入れるわけねーだろって
言ってんじゃん。。何読んでんだよ。
28:デフォルトの名無しさん
21/04/27 18:23:48.67 n/AWrch2.net
まあ半年後どうなるかで誰が正しかったかは分かるわな
29:デフォルトの名無しさん
21/04/27 20:32:29.92 /+bIFNU8.net
半年も経たなくてももうわかってるっつーの。。だからちゃんと英語の勉強しましょうね。
30:デフォルトの名無しさん
21/04/28 03:52:50.81 v8E9sca8.net
C++で、n要素のint型の生配列を確保するには、
int *pBuf = new int [n];
だけど、Rustの
let a:Box<i32> = Box::new<x>;
値が x である 32BIT 整数を Heap に 1 つ確保する、という意味だよね？
Heapに n 要素の i32 型の配列を確保したい場合、
let a:Vec<i32> = vec![0; n];
かな？
31:デフォルトの名無しさん
21/04/28 03:55:12.80 v8E9sca8.net
>>30
あ、
let a:Box<i32> = Box::new<x>;
ではなく、
let a:Box<i32> = Box::new(x);
let a:Box<i32> = Box<i32>::new(x);
let a = Box::new(x);
let a = Box<i32>::new(x);
かな。
か
32:デフォルトの名無しさん
21/04/28 04:01:18.27 v8E9sca8.net
>>31
確保した領域の中身を書き換えたい場合は「mut」を付ける必要があり、
値が x である 32BIT 整数を Heap に 1 つ確保するのは：
let mut a:Box<i32> = Box::new(x);
let mut a:Box<i32> = Box<i32>::new(x);
let mut a = Box::new(x);
let mut a = Box<i32>::new(x);
のどれかの書き方で、Heapに n 要素の i32 型の配列を確保するのが、
let mut a:Vec<i32> = vec![0; n];
let mut a = vec![0; n];
のどちらかの書き方かな？
33:デフォルトの名無しさん
21/04/28 10:37:51.57 6K8rF/jG.net
let mut a = Box::new([0,n]);
34:デフォルトの名無しさん
21/04/28 12:44:00.99 jQpDsyge.net
>>33
なるほど、そんな書き方があったとは。でも正しくは、
let mut a = Box::new([0; n]);
かな？
35:デフォルトの名無しさん
21/04/28 15:21:28.78 jQpDsyge.net
[0; n]
って、n 要素のi32配列を確保して0で初期化するという意味らしいけど、
nは実行時に決まらないような変数も指定できるの？
36:デフォルトの名無しさん
21/04/28 16:30:39.18 BfdKSrwu.net
>>35
できない
URLﾘﾝｸ(stackoverflow.com)
Vec<i32>に相当するのはstd::vector<int>だから、
>>33はstd::unique_ptr<int []>相当のBox<[i32]>型の例を出そうとしたのだろう
そういう値は作れるが、Box::newでは無理
37:デフォルトの名無しさん
21/08/31 15:22:27.39 8qO1h2Cp.net
246 デフォルトの名無しさん sage 2021/08/31(火) 14:25:42.76 ID:SlncBcTV
>>244
ポインタは適切に使えばデータ構造やアルゴリズム自体が根本的に変えることが
できるので使わない時と比べて計算オーダー自体が劇的に変化することがあり、
プラシーボではない。
Rustはその点でC/C++に勝てない事がある。
247 デフォルトの名無しさん sage 2021/08/31(火) 14:28:10.16 ID:SlncBcTV
例えば、動的配列であるところのVectorはポインタでアクセスしても余り
効率は良くならないが、LinkedListは構造的にポインタで連結されており、
首尾一貫して添え字アクセスを使わずに必ずポインタでノードを識別する
ようにすれば、Vectorに比べて劇的に効率アップできることがある。
それはRustではほぼ不可能。ベンチマークはこの点が反映されてない。
38:デフォルトの名無しさん
21/08/31 16:19:11.51 KWeLtswn.net
コード例と性能測定結果くれ
39:デフォルトの名無しさん
21/08/31 17:18:36.26 SlncBcTV.net
>>38
同じ動作をしてもVectorだとO(N)なのに、LinkedListだとO(1)になるものがある。
これだけでも実験してみなくてもNが大きくなった時に明らかに速度が
違うことはコンピュータ科学では常識。
例えば、コロナの感染者数は、O(exp(aN))になるので、どんだけ頑張っても、
Nが十分大きい時にはO(N^b)が上回ることは出来ない。
40:デフォルトの名無しさん
21/08/31 18:26:05.32 8qO1h2Cp.net
まだstable入りはしてないけどlinked_list::{Cursor, CursorMut}っていうのがあるね
その
41:ベンチマークでは使ってる？
42:デフォルトの名無しさん
21/08/31 19:03:52.76 WFW0JNLV.net
LinkedListとはなんぞや？std::list?
43:デフォルトの名無しさん
21/08/31 19:52:34.92 4dUmDNFP.net
>>39
Rust は stable で LinkedList も VecDeque (双方向キュー)もありますよ
URLﾘﾝｸ(doc.rust-lang.org)
ここにそれらのオーダーが O(1) や O(N) になる話もまとまっています
44:デフォルトの名無しさん
21/08/31 21:21:08.46 KWeLtswn.net
>>39
参照局所性の問題もあるから計算量の理論通りにはいかない場合もあるけど、ちゃんと性能測定してデータ構造選定した？
45:デフォルトの名無しさん
21/08/31 21:26:21.55 KWeLtswn.net
あとRustではほぼ不可能の意味が分からない
Rust にはポインタがあるから C や C++ のデータ構造はほぼ実現可能なのでは
46:ハノン
21/08/31 22:08:35.31 .net
>>44
では赤黒木をひとつやってみて
47:デフォルトの名無しさん
21/08/31 22:27:32.77 wvWDiazC.net
>>45
Rc<RefCell<Node>>のパターン
Safe Rustでも実現可能
48:デフォルトの名無しさん
21/08/31 23:58:27.88 SlncBcTV.net
>>42
ところが、Rustでは借用規則のせいで上手く行かない。
めんどくさいので自分で気づく人だけが理解してくれればいいので、
俺はこれ以上説明しない。
理解できない人は、親切な人が説明してくれるのを待て。
49:デフォルトの名無しさん
21/08/31 23:58:51.57 SlncBcTV.net
>>44
無理。
50:デフォルトの名無しさん
21/09/01 00:55:38.60 MtyAaHfZ.net
>>47
それはあなたが無知なだけだ
Rustはメモリ安全性を保証する
一方でRustの標準ライブラリではunsafeが多数使われているがこれはメモリ安全性を保証できる操作を効率よく実装するためにある
つまり論理的にメモリ安全性を保証できるならばunsafeを用いてもそれをライブラリやモジュールに閉じ込めることができる
もちろん自作でもこれは同様である
新たな型も当然作ることが可能
標準ライブラリで提供されているリンクドリスト型や双方向リスト型はそのようにして作られている
つまり効率をも落とさない
51:デフォルトの名無しさん
21/09/01 01:25:17.04 +dwouIiT.net
>>49
お前は何も分かってない。
馬鹿は黙ってろ。
52:デフォルトの名無しさん
21/09/01 01:27:41.34 FA803rPU.net
>>40にも答えてくれよ
その「問題」とやらはCursorじゃ解決されてないのかい
53:デフォルトの名無しさん
21/09/03 08:12:39.26 t+NhPRD1.net
>>49
ガイジ
54:デフォルトの名無しさん
21/09/07 20:33:21.38 ezLxFpG4.net
結局unsafe多用するとか意味ないジャンw
55:デフォルトの名無しさん
21/09/07 23:30:30.79 W5eU3b0C.net
>>53 裏方のunsafeなコード(≠危険なコード)を安全に利用してプログラムを書けるのがRustだと思う
また､その裏方のunsafeなコードをRustで書く意味はRustから扱いやすいこと､Rustプログラマーが慣れたRustの文法で書けることがあると思う
56:デフォルトの名無しさん
21/09/08 01:30:18.74 c9lCkxrV.net
>>54
お前の理解は浅くて、間違っている。
お前の様な数学の出来ない人には何を言っても無駄。
57:デフォルトの名無しさん
21/09/08 01:30:55.64 c9lCkxrV.net
unsafeを閉じ込め切れるならRustはパーフェクトだが、そうはなってないのだ。
58:デフォルトの名無しさん
21/09/08 09:53:24.22 8gtworgR.net
>>55 そうか､まぁ一個人の感想ぐらいに受け取ってくれ
59:デフォルトの名無しさん
21/09/09 16:53:30.53 lJRSMQ7p.net
なんだかんだ言ってまだまだC++だな
60:デフォルトの名無しさん
21/09/09 17:22:38.75 fa/WJTRs.net
unsafe を閉じこめられるかどうかはAPI設計力が問われるよな
61:デフォルトの名無しさん
21/09/09 18:17:29.61 18O2MBOf.net
>>56
Rustはunsafeを局所的に安全に閉じ込めることができます
例えばVec<T>型はその各メソッド実装においてunsafeを用いています
これも『Rustがunsafeを局所的に安全に閉じ込めることができる』具体的な実例です
>>58
C++よりもRustの方が優れています
62:デフォルトの名無しさん
21/09/10 08:39:25.32 w07MHOd0.net
>>60
前半、数学的には間違い。
お前には数学の才能が無い。
63:デフォルトの名無しさん
21/09/10 09:06:15.40 Ga+Uz44a.net
数学関係ないし
お前には数学の才能が無い
64:デフォルトの名無しさん
21/09/10 09:26:50.69 XIGB6bHM.net
数学的に間違いの意味がようわからんが、
unsafeブロック内あるいは関数内でSAFETYが守られるようにしないと安全に閉じ込めることができないって意味？？
65:デフォルトの名無しさん
21/09/10 09:28:15.95 KDfyX1FH.net
Vec<T> が unsafe を使って安全なインターフェースを提供してることへの反論を示してくれ
66:デフォルトの名無しさん
21/09/10 11:00:27.70 4cVpX4oe.net
>>63
そうでなくて、unsafeブロックで閉じ込めようとしても、閉じ込め切れなくて、
O(x)で表される計算時間が、C言語とは同じでは絶対に不可能な場合があるんだ。
Rustのsafeモードでは、コンテナの中のノードに対して書き込み参照と読み込み参照
を持つことが借用規則によって禁じられていることが原因。
C言語ではそれが当たり前に出来るからとても効率の良いプログラムが可能だが
Rustでは、unsafeの外側ではそれが出来ないから不可能だ。
アプリレベルでそれが出来ないから。
これで納得できない人は数学の才能が無い。
俺は数学の天才。
67:デフォルトの名無しさん
21/09/10 11:05:19.78 4cVpX4oe.net
>>65
数学の才能が無い人のためにもう少し詳しく書いてやろう。
・Rustのsafeモードでは、LinkedListの中の複数のノードに対して、
読み込み参照と書き込み参照を一度自動時には持てない。
持つと borrow cheker がコンパイル時にエラーを出してしまう。
・C言語ではそれが当たり前に出来る。
・アプリレベルで1つのLinkedListに対して複数の読み込み参照と
書き込み参照を同時に記録し続けることで、やっと、挿入や削除が
O(1)になる。index 値で保持すると O(N)になってしまうから、
vector と同じ速度オーダーしか出ない(つまり、LinkedList本来の性能
が全く出せない。)
・結果、Rustは、Cより遅いプログラムしか出来ない。その遅さは、データが
多いとき、C言語に比べて1万倍でも100万倍でも遅くなる。
68:デフォルトの名無しさん
21/09/10 11:27:11.50 2Djs9W2b.net
>>66
コードで書いて
69:デフォルトの名無しさん
21/09/10 11:30:01.67 4cVpX4oe.net
>>67
RustとCの知識と、東大数学が簡単に解けるような数学の才能をすべてもっている人
に聴いてみろ。
70:デフォルトの名無しさん
21/09/10 11:36:42.07 4cVpX4oe.net
>>68
本当は次のような知識も必要：
・リンクドリストの構造。
・リンクドリストの挿入、削除などの計算オーダーO(x)。
・計算オーダーの記号O(x)の意味。ビッグオー。ランダウの記号。
東大、京大の学部レベルの解析学(微分積分学)の本を見よ。
・index 値 = 基本は配列の添え字。0から割り振られた連番。
リンクドリストでは本来使わないが、Rustではノードの場所を覚えておくために
使わざると得ない。その場合、リンクドリストの先頭のノードを 0 番とし、
次のノードを 1, その次のノードを 2 のように表す。
しかしそうすると、リンクドリスとの M 番目の場所の参照を取得するのに
O(M)の時間が掛かってしまい、リンクドリストの効率の良さが台無しになってしまう。
・このことから、リンクドリストが遅いという誤解を生む状況になってしまっている。
71:デフォルトの名無しさん
21/09/10 11:38:10.81 2Djs9W2b.net
>>68
東大数学って何？
72:デフォルトの名無しさん
21/09/10 11:39:59.60 4cVpX4oe.net
>>70
高校生が灯台に入学するときに受ける東大の数学の試験のことだよ。
それが簡単に解けるくらいのやつに聞いてみろって事だ。
しかし、受験テクニックやパターン学習によって解ける様になったやつはダメだ。
73:デフォルトの名無しさん
21/09/10 11:49:52.37 2Djs9W2b.net
>>69
O(1) で i 番目の要素にアクセスできる safe な LinkedList 実装はある
URLﾘﾝｸ(docs.rs)
74:デフォルトの名無しさん
21/09/10 11:52:48.63 2Djs9W2b.net
>>72
i 番目の要素というと不正確か
ポインタの代わりに Arena 内での index を使うことで LinkedList のノードを O(1) で参照することができる
75:デフォルトの名無しさん
21/09/10 11:53:08.66 FsmeH+FF.net
URLﾘﾝｸ(play.rust-lang.org)
Repeated 1 time(s), duration = 2.531µs
Repeated 10 time(s), duration = 4.661µs
Repeated 100 time(s), duration = 29.449µs
Repeated 1000 time(s), duration = 256.555µs
Repeated 10000 time(s), duration = 1.800129ms
Repeated 20000 time(s), duration = 3.273489ms
Repeated 50000 time(s), duration = 8.345219ms
Repeated 100000 time(s), duration = 16.454731ms
Repeated 200000 time(s), duration = 32.911471ms
Repeated 500000 time(s), duration = 83.993118ms
Repeated 1000000 time(s), duration = 166.193956ms
結構実行毎にゆれる感じはあるけど、おおむねO(1)じゃないですかね
76:デフォルトの名無しさん
21/09/10 12:09:20.46 4cVpX4oe.net
>>74
アホですか？
>>73
Arenaを使った時点で裸のリンクリストじゃ無いし、時間は、O(x)が同じでも
オーバーヘッドが発生する。また、無駄なメモリー領域も食う。
77:デフォルトの名無しさん
21/09/10 12:12:17.45 Ga+Uz44a.net
>>68
呼んだ？
78:デフォルトの名無しさん
21/09/10 12:14:53.57 Ga+Uz44a.net
>>71
えっ？
高校数学？
レベル低くないか？
79:デフォルトの名無しさん
21/09/10 12:18:15.36 Ga+Uz44a.net
少なくとも>>65が書いてることは数学的でも何でもない
80:デフォルトの名無しさん
21/09/10 12:18:20.87 FsmeH+FF.net
>>75
はい、私はアホで数学の才能が無いので数学の天才様の問題意識が分かりません
VecならO(n)になる先頭への挿入がO(1)でできることを示したつもりでしたが見当違いでしたでしょうか
81:デフォルトの名無しさん
21/09/10 12:27:50.85 4cVpX4oe.net
>>79
push_front()使ってるから先頭へ挿入してるだけじゃないか。
Cのリンクリストは、どんな非負整数 M に対して、M番目に挿入しても
MにもNにも依存しない定数時間で挿入できる。
それがRustに欠けている。
82:デフォルトの名無しさん
21/09/10 12:28:54.60 2Djs9W2b.net
>>75
そのオーバーヘッドは実用上問題になりますか？
例えばmallocの実装もarenaを使っていますが問題はないのですか？
そもそも計算量の議論をしていたのはあなたなのになぜ論点をずらすのですか？
83:デフォルトの名無しさん
21/09/10 12:30:48.00 Ga+Uz44a.net
>>80
挿入自体が定数時間でも
M番目を探すのが定数じゃない
84:デフォルトの名無しさん
21/09/10 12:41:50.91 4cVpX4oe.net
>>82
「M番目」のMをそのまま「通し番号」で表しているならその通りだ、たとえC
であっても。
しかし、Cでは、通し番号ではなくポインタで表現することで1クロックで
辿り付けるので O(1)。
85:デフォルトの名無しさん
21/09/10 12:42:38.21 XIGB6bHM.net
>>65が何言ってるのか1行たりとも理解できなくて日本語の見た目した何かにしか見えないんだけど、
なんで話が進んでるの・・・
86:デフォルトの名無しさん
21/09/10 13:08:34.28 Ga+Uz44a.net
>>83
自分でM番目に挿入って書いてるわけだが
87:デフォルトの名無しさん
21/09/10 13:34:07.88 4cVpX4oe.net
>>85
「M番目に挿入」するが、それをMという数値で識別するとは書いてない。
数学とはそういうものだ。
ポインタ p で表現する場合でも、p が M 番目のノードを指していることがある。
その場合は、M番目に挿入と表現される。
そう表現しないと、O(x)記号で表現しにくいからだ。
88:デフォルトの名無しさん
21/09/10 13:35:00.70 FsmeH+FF.net
>>83
それと同じことをRustではポインタの代わりにCursorMutを使って実現できる、という認識ですが
CursorMutには何が欠けていますか？
89:デフォルトの名無しさん
21/09/10 13:35:29.31 4cVpX4oe.net
数学での言葉の表現と日常の言葉の表現は異なる。
「M番目に挿入」することと、そのノードを、index = M - 1 で表すこととは
別の話だ。
90:デフォルトの名無しさん
21/09/10 13:47:35.86 4cVpX4oe.net
>>87
同じノードを複数のCursor/CursorMutが参照している場合、1つの参照経由
でノードを削除した場合、別の参照がダングリング参照になるのを0コストで
防ぐ方法は無いはずだ。
静的解析が不可能で、時間や記憶域に何らかのオーバヘッドが必要となるはず。
91:デフォルトの名無しさん
21/09/10 14:16:45.03 4cVpX4oe.net
さらに、1つの LinkedListに対して、同時に2個以上の CursorMut を作ることは
出来ないはず。
92:デフォルトの名無しさん
21/09/10 14:18:55.00 iOAXb/4V.net
Cでリンクドリストの途中を直接ポインタで持っていると速いが
その途中が削除された場合にそのポインタは危険なポインタとなる
つまりCで記述しても何らかのコストをかけなければ安全に出来ない
つまりこの問題はどの言語であろうがコストゼロにすることは不可能
93:デフォルトの名無しさん
21/09/10 15:27:02.65 I2sJLr90.net
>>91
いや、数学が得意な人は頭がいいので、それでも至って安全なプログラムが書けるし、
今ままでも書いてきた。
Rustは数学の得意な人間には遥かに及ばない。
94:デフォルトの名無しさん
21/09/10 15:44:47.65 EyQ85oMr.net
すげぇバカ
95:デフォルトの名無しさん
21/09/10 15:45:34.73 XIGB6bHM.net
よくわからないけどこんなスレよりqiitaとかzennとかで記事書いたほうがいいと思う
96:デフォルトの名無しさん
21/09/10 17:06:16.82 lpjuAWj9.net
>>86
屁理屈
97:デフォルトの名無しさん
21/09/10 17:11:54.58 lpjuAWj9.net
どんな非負整数Mに対して
と自分で書いている
当然与える情報はMである
各Mに対応するポインタを保持するなら
挿入時にそのテーブルを更新しなきゃならないから
O(1)では出来ない
98:デフォルトの名無しさん
21/09/10 17:38:39.28 dS7angqs.net
>>96
Mを与える情報とは書いてない。
Mというものを使わないと、LinkedListとVectorで共通した議論が出来なく
なるから書いてるだけ。数学では良く使う論法。
つまり、Mは、議論の中で場所を特定するために用いているだけで、
プログラム中で用いているとは言ってない。
99:デフォルトの名無しさん
21/09/10 17:41:20.99 dS7angqs.net
例えば、コンテナに100個のノードが入っていたとする。
コンテナは、LinkedListやVectorなどどんなアルゴリズムを使っているかは何でも良い。
で、「5番目の場所にノードを追加する」という言葉は、LinkedListにも使えるが、
その場合、プログラム中では5という数値で識別せず使わず、ポインタで識別する
のが C言語での常識。
でも、「5番目の場所に追加する」という言葉は使ってよい事になっている。
100:デフォルトの名無しさん
21/09/10 17:43:19.62 iOAXb/4V.net
>>96
その人は数学が得意と言いながらそこすら理解できていない人だからね
Cでもプログラミングしたことあるならすぐわかることだからプログラミング経験も乏しいと推測される
つまりRustを叩きたいだけの人が暴れているだけの構図
101:デフォルトの名無しさん
21/09/10 17:48:47.41 dS7angqs.net
>>99
理解してる。
お前らが、M番目のノードを数値Mでプログラムでも辿ると勘違いしている
抽象化が理解できない馬鹿だからそう思ってるだけ。
俺は抽象化が得意だから、M番目のノードをポインタで識別すると
考える。お前らは、Mとpを脳内で橋渡しできないだけ。
102:デフォルトの名無しさん
21/09/10 17:49:37.61 dS7angqs.net
数学的才能の無い人とは話が合わない。
知能に差が大きすぎる人達とは話が合わない。
103:デフォルトの名無しさん
21/09/10 17:58:29.87 9JzLMDXF.net
もっと知能レベルが合った人が集う場所にいきな
104:デフォルトの名無しさん
21/09/10 18:15:44.49 ae9TKcqK.net
>>100
君は数学が不得意だな
入力Mに対してM番目を得る関数のコスト(リソースコストなど含む)を考えればいいだけなのにそれができない
抽象的に考えるのが苦手なら具体的な関数のプログラムを考えてもよい
Rustを叩きたいだけだとしてもC言語のプログラミングくらいはできるんだろ？
君の主張が間違っていて実現不可能なことがすぐわかる
そして示せなければ君の完全敗北確定だ
105:デフォルトの名無しさん
21/09/10 18:22:19.32 uQqwzIiF.net
>>98
完全に屁理屈
それならわざわざ「どんな非負整数Mに対しても」なんて言う必要は全く無い
任意のノード、任意の箇所
ならまだそういう可能性もある
たまたまMに対応するポインタがキャッシュされてた場合の計算量を言っても何の意味も無い
ちなみに数学的能力はお前よりあると思うよ
実績で勝負するなら付き合う
106:デフォルトの名無しさん
21/09/10 18:33:25.73 HO5HNd+Q.net
>>65
> 俺は数学の天才。
これみて釣りと判断してるけどマジに受け取ってる人もいるのかな？
議論を続けるなら数学うんぬんの要素を抜きつつアクセス効率だけ語ってほすい
107:デフォルトの名無しさん
21/09/10 20:54:06.22 2Djs9W2b.net
まあここ隔離スレなんで
108:デフォルトの名無しさん
21/09/10 22:29:30.98 S72cPfGI.net
自分は数学できないからできる人の相場感覚は分からないが、数学の天才って◯◯予想を証明したとか、定理に自分の名前が付いているとか、そういうレベルの人のことじゃない？ 東大数学程度で数学の天才を名乗られても……。
109:デフォルトの名無しさん
21/09/10 23:03:29.47 G/i8H+xj.net
> 高校生が灯台に入学するときに受ける東大の数学の試験のことだよ。
高校数学でここまでイキれるのはもはや才能だと思うわ
数学の天才っていうのは数学の研究してて教科書書いてるような
著名な人をまわりの人が「他称」するときの話で
高校数学の成績で「自称」しちゃうってのは別の才能ｗ
110:デフォルトの名無しさん
21/09/10 23:04:20.56 uQqwzIiF.net
東大でやる数学じゃなくて入試でしょ？
つまり高校レベル
こんなのを東大の数学と言うな
111:デフォルトの名無しさん
21/09/11 01:22:42.58 Q/hQI3Xf.net
知ってる一番難しい数学がそれだったんでしょ
つっこんであげないのが優しさでは
112:デフォルトの名無しさん
21/09/11 01:40:01.24 PRM8i6LA.net
>>80
C言語でも他の言語でもそのようなことは実現不可能です
いくらRustを叩きたいとはいえ主張が滅茶苦茶になっていますよ
113:デフォルトの名無しさん
21/09/11 10:36:57.99 kQXQH3+b.net
馬鹿ばっか。
114:デフォルトの名無しさん
21/09/11 11:20:17.45 PFLibieQ.net
実際連結リストのノードに対する参照を保持しておくってどういうユースケースで現れるんだろうか
115:デフォルトの名無しさん
21/09/11 11:40:09.41 tSun79KI.net
掲示板で算数自慢するときに使う
116:デフォルトの名無しさん
21/09/11 11:42:49.15 kQXQH3+b.net
>>113
例:
1. テキストエディタで、10万行のファイルを読み込み、その先頭に
1000行のテキストを挿入するときの速度向上。
2. 言語を自作する時、マクロ展開の時のトークン列へのトークンの挿入
117:デフォルトの名無しさん
21/09/11 16:43:18.56 zUj2TAiQ.net
>>115
それはどちらの使用例なのかハッキリしてほしいです。
配列にN番目への参照を格納する例として挙げているのか、
そうではなくリンクリストを用いる例として挙げているのか、
どちらですか？
118:デフォルトの名無しさん
21/09/11 23:33:36.29 EO9owr6G.net
>>112
119:デフォルトの名無しさん
21/09/12 00:21:25.00 CFIv5O+a.net
相手をバカと貶めることで何もしなくても自分わ相対的に高めることができるという高等な議論テクだ
さすが高学歴
120:デフォルトの名無しさん
21/09/12 02:54:54.78 x/1IPUIX.net
>>115
1.ってバッファを1個のLinkedListとして持っておいて、カーソルの位置をノードへの&mutで持っておきたいって発想だよね
それよか2個のLinkedListに「カーソル以前の内容」「カーソル以降の内容」を最初から分けて持っておいて、
必要に応じて前者の末尾または後者の先頭を操作するという風にすれば、常に&mut LinkedListつかまれることもなくて都合良いのでは？
workaroundでしかないという批判は認めよう
121:デフォルトの名無しさん
21/09/17 13:36:25.88 9sB/yeOV.net
任意のM番目に要素を挿入する時間計算量がO(1)の線形リストができないと入院中の妹が苦しむんだわ…
122:デフォルトの名無しさん
21/09/18 16:11:40.95 bNqoSBDr.net
どーでも良いですよ
byだいたひかる
123:デフォルトの名無しさん
21/10/05 15:44:11.57 +1Hntkr6.net
素人だからよく分からんけど、実務やってる人からCppだとvoid**とか出てきて難しすぎて狂うって話は聞いたことあるけどラッパークラスを作って分かりやすいメソッドつくればいいんじゃないの
124:デフォルトの名無しさん
21/10/05 18:47:14.74 JbR3YU6O.net
void**のどこが難しいのかさっぱり
125:デフォルトの名無しさん
21/10/17 09:40:31.27 6Bvliwnf.net
void**は許さない派
126:デフォルトの名無しさん
21/10/24 13:55:43.29 eQqSgpa/.net
任意の言語ができる操作が任意の言語ではできないとほざくやつが数学ができるとかネタか糖質だろう...
チューニングマシンの存在を真っ向から否定したいならここではなく学会で論文を出そうね
127:デフォルトの名無しさん
21/10/24 14:24:43.42 eQqSgpa/.net
プロレスごっこを期待して覗いたら、キチガイが占拠していたのは笑う
128:デフォルトの名無しさん
21/10/24 14:57:26.55 dxF2sYGf.net
ここ隔離スレなので
129:デフォルトの名無しさん
21/10/24 18:05:52.35 NLtlOSxj.net
チューニングマシンて
130:デフォルトの名無しさん
21/10/24 20:19:43.90 IF6Ria+p.net
c++とrustってチューニング完全なんですよね。意外にこれ知られてない
131:デフォルトの名無しさん
21/10/24 20:55:50.68 IF6Ria+p.net
rustの所有権は所謂、線形型
普通に理論として確立している
数学できるくんの主張は線形型によってチューニングマシンの計算複雑性が変化するってことだろう
証明できたらチューニング賞ものだろう
何十年ぶりじゃないか?記述計算量に新しい概念が導入されるのは
132:デフォルトの名無しさん
21/10/24 22:07:03.33 +peTc5KU.net
rustの所有権や借用や、コンパイルが通らずにいらいらきますが、慣れればスラスラというか、ストレスなく書けるようになるのかな
133:デフォルトの名無しさん
21/10/24 22:10:42.59 +peTc5KU.net
日本語がおかしいですが、
所有権や借用が、やりたいことをストレスなく書けるようになる気がしなくて…
134:デフォルトの名無しさん
21/10/24 22:29:10.11 HVo+cqVA.net
慣れみたいなものはあると思う
コンパイル通るようコード直すことを繰り返す内に最初からコンパイル通すことができるようになるかと
135:デフォルトの名無しさん
21/10/24 22:41:32.45 +peTc5KU.net
>>133
ありがとうございます
やはり繰り返しと慣れですね…
もう少し分かるまで粘ってみます
取り急ぎお礼まで
136:デフォルトの名無しさん
21/10/25 17:58:05.73 a6PpXdhO.net
>>131
細かいことにいちいち煩い姑のようだからね。
別に大したご利益
137:もないし。
138:デフォルトの名無しさん
21/10/25 20:25:16.68 cubP7NbG.net
>>135
ご利益の大小はソフトウェアの種類によって変わるだろうね
OSやブラウザのようなメモリアクセス違反が即致命的な脆弱性に繋がり得る、かつ、巨大でバグを取り除ききるのが難しいソフトではご利益大きい
逆に多少バギーでも困らないソフトならただ煩わしいだけというのは正しいかも
とはいえ慣れればコンパイルが通るようにコードを書くのは多くの場合難しくないので、個人的にはカジュアルユースでもコストよりメリットが多いように感じる
139:デフォルトの名無しさん
21/10/26 18:03:05.91 KgmW7hJW.net
>>136
め早口
140:デフォルトの名無しさん
21/10/26 20:06:45.12 OracOvFU.net
>>131
「最後に消費するのは誰か？」を明確にするだけでよくて
その人以外に渡す時は借用してもらうだけだよね
あとはmut借用だけ一時的独占でルールおしまい
141:デフォルトの名無しさん
21/10/26 22:54:07.10 XkR6Nv6d.net
>>138
コメントありがとうございます
いまはまだおっしゃることにピンとこないのですが、「最終消費者は誰か」は常にこころに留めて進めてみます
まだサンプルコードを写経している段階なので、具体的なテーマを見つけて苦労してみます
>>135 さんもありがとうございます
ホント、小煩い姑状態です
親父の小言は後に効く、といいますが…
haskellでいう型クラスや、代数データ型、パターンマッチなど魅力的な機能があり、はやく馴染みたいです…
142:デフォルトの名無しさん
21/10/26 23:17:46.13 zVG+0sad.net
>>29
まさに半年経ってようやくカーネルにアロケーター導入されたわけだが
完璧に君の負けだよね
お疲れ様です
143:デフォルトの名無しさん
21/10/27 08:20:39.13 qg2SY4Q5.net
こんな実装するならrust使う意味ないけどねw
URLﾘﾝｸ(doc.rust-lang.org)
頭悪いからさらに時間使っちゃいそうでかわいそう。
144:デフォルトの名無しさん
21/10/27 09:20:32.30 2iZWGrmg.net
ゴールをずらせば負けたことにならないまで読んだ
145:デフォルトの名無しさん
21/10/27 09:23:36.95 q+lzbSiO.net
あちゃちゃｗそれ別のapiじゃんｗ
お馬鹿さんだからメーリス追えないんだねｗｗ
146:デフォルトの名無しさん
21/10/27 09:29:13.91 zfYVqfDQ.net
話追えるようになってから来てくださいね🤗
147:デフォルトの名無しさん
21/10/27 09:30:10.86 zfYVqfDQ.net
頭悪いのどっちかな
148:デフォルトの名無しさん
21/10/27 14:57:34.79 qg2SY4Q5.net
は？linuxの方ならここから話全く進んでないんだが。。誤魔化せると思ったのかな。。
URLﾘﾝｸ(lkml.org)
149:デフォルトの名無しさん
21/10/27 15:49:20.46 G9Y5/nKM.net
だからそれだけ貼られても経緯とかなんもわからんし読む気もおきんって
150:デフォルトの名無しさん
21/10/27 16:58:29.94 Ru0zcXw7.net
顔真っ赤っかで草ｗ
悔しいねえｗ
151:デフォルトの名無しさん
21/10/27 16:59:43.91 3BkIbLo2.net
>>146
頭悪いの君だよね？
152:デフォルトの名無しさん
21/10/27 18:36:52.66 zwnES/cK.net
あわしろ氏がLinuxをRustで書き直すプロジェクト始めなかったっけ。
153:デフォルトの名無しさん
21/11/21 11:28:03.98 aXP4f2By.net
どんなに簡単でも、できることに制限がある言語は流行らない、という経験法則がある。
Rustも使えるアルゴリズムに制限があるのだが。
例えば、C言語で使えていたアルゴリズムは、C++/Java/C#ではそのまま使える。
特に
154:C++とC#には、Cから移行するときの制限が少ない。 ところがRustでは、これらのコードからはシンプルには移植できないものが存在 してしまう。 C#やJavaは速度を遅くする代わりに安全性と自由性の両方を確保できているが、 Rustは、速度は余り遅くならないが、自由性を犠牲にしている。 これは大問題となるだろう。
155:デフォルトの名無しさん
21/11/21 11:54:39.30 7O4ablWw.net
C++に勝てるワケねぇだろ
156:デフォルトの名無しさん
21/11/21 13:31:58.91 kZvTUakz.net
unsafeあるくせにできないことあるのか
157:デフォルトの名無しさん
21/11/21 13:33:18.01 vno614JY.net
いつもの奴だ
158:デフォルトの名無しさん
21/11/21 14:23:27.74 qwOTZsAN.net
>>153
unsafeの中だけに閉じ込めきれないのが問題。
例えば、C言語の場合、アセンブラにしか掛けないことは、アセンブラでコードを書いた
ものをCの関数にして、Cから呼び出すことが出来たので問題なかった。
ところがRustの場合、リンクリストをポインタや参照を使って高速に扱うことが
unsafeの中だけでは完結できないので無理。
結論的には、リンクリストをO(1)でアクセスすることがRustのsafeモードでは
完全に不可能といえる。たとえ unsafe モードを使っても、safeモードに
「しみ出してきて」駄目になる。
159:デフォルトの名無しさん
21/11/21 14:25:17.13 qwOTZsAN.net
Rustを使うなら、次のデータ構造をCのように「効率よく扱う」のは諦めるしかない:
・リンクリスト
・ツリー構造(バイナリツリーなども含む)
なんどもいうが、unsafeモードをいくら使っても言語の構造上、
無理なものは無理。
俺は数学の天才。最初から結論が分かる。
160:デフォルトの名無しさん
21/11/21 14:27:35.80 qwOTZsAN.net
何度も言おう。
Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセス
できないことは数学的に完全に証明できる。
そしてそれは、unsafeモードをいかに工夫して使っても無理。
無理なものは無理。これは絶対。
俺は数学の天才。
161:デフォルトの名無しさん
21/11/21 14:30:47.72 qwOTZsAN.net
[補足]
それが出来るんだったらもっと普及してるし、もっと真似されてる。
Rustのやり方では不可能だから普及できない。
162:デフォルトの名無しさん
21/11/21 14:37:38.26 ekMm5ue5.net
>>155
つまりunsafe使えばできるのね
163:デフォルトの名無しさん
21/11/21 14:54:12.46 uAxr+NUo.net
>>159
アプリのあらゆる場所を unsafe にすれば出来る。
unsafeの閉じ込めが出来ない。
164:デフォルトの名無しさん
21/11/21 19:24:03.14 a8amZ/lG.net
>>157
また嘘つきがRust叩きをしているのか
＞リンクリストやツリー構造をO(1)でランダムアクセスできない
これは全てのプログラミング言語で不可能
もちろんC言語でも不可能
以前も皆に論破されて逃走したのにまた戻ってきたのか
165:デフォルトの名無しさん
21/11/21 19:46:49.29 /ddxrWFf.net
>>161
馬鹿は黙っとれ。
お前は全くリンクリストを理解できてない。
166:デフォルトの名無しさん
21/11/21 19:47:48.85 /ddxrWFf.net
ここはレベルが低すぎる。
丁寧に説明したのに全く理解を示さないやつばかり。
167:デフォルトの名無しさん
21/11/21 19:49:09.49 /ddxrWFf.net
C/C++が速いのは、リンクリストのおかげだ。
Stroustrapも馬鹿だからリンクリストを理解できてない。
vectorだけでは人気アプリの速度は達成できてない。
168:デフォルトの名無しさん
21/11/21 20:11:47.26 ru7ojY1Q.net
よく知らんけど、ツリーとかリンクリストうまく扱えないの？
169:デフォルトの名無しさん
21/11/21 20:18:26.10 ekMm5ue5.net
>>163
コード例頂けないでしょうか
Cでうまく書けるものがRustでうまく書けない例
170:デフォルトの名無しさん
21/11/21 20:23:22.75 a8amZ/lG.net
std::collections::LinkedList
URLﾘﾝｸ(doc.rust-lang.org)
std::collections::BTreeMap
URLﾘﾝｸ(doc.rust-lang.org)
171:デフォルトの名無しさん
21/11/21 20:53:48.92 ZPin+mWW.net
算数得意おじちゃんが生えてきたな
172:デフォルトの名無しさん
21/11/22 00:48:17.10 saDsX792.net
>>165
本来の速度性能が出ない。
CではO(1)で済むところが、O(N)必要になってしまう。
173:デフォルトの名無しさん
21/11/22 00:50:22.67 saDsX792.net
>>168
余りにも馬鹿すぎるから、発言者の背景を示すしかなかった。
IQの違いが大きすぎると話が通じないと言われるが、まさに
このスレがそうで、ちゃんと言わないと、正しいことを言ってる
人が馬鹿にされるから。
174:デフォルトの名無しさん
21/11/22 01:02:53.27 saDsX792.net
>>166
・Cだとリンクリストやツリーの中のノードを識別するのに、通し番号ではなく
ポインタが使われる。そのポインタは、関数内部にとどまらず、
アプリ全体で大規模に保持され続け、ノードが必要になった場合、それを
介してノードにアクセスする。だから、読み込みも書き込みも自由自在に
行える。一つのツリーの中の有るノードを削除し、あるノードに子ノード
を追加し、あるノードの直後に弟ノードを追加し、あるノードを読み取り、
あるノードに書き込む、などを全く任意のタイミングで行える。
繰り返しになるが、これらのポインタはある関数の内部だけで完結
せずに、関数の外のグローバル変数にアプリの起動時から終了時まで
恒久的に保持され、必要なタイミングで使用される。
・Rustではこのようなことが不可能。ツリーのノードを指す参照を、
グローバル変数に複数保持して、書き込みと読み込みを自由自在に
行うことが不可能だかっら。
175:デフォルトの名無しさん
21/11/22 01:07:59.95 saDsX792.net
>>171
[補足]
Cの方で説明したやり方は、C++/C/Javaでも可能。
JSやRuby、Pythonでも可能。
Rustだけが不可能。
つまり、多くの言語が出来る中でRustだけが出来ない。
その結果、数学的な意味での「一般的」には、TreeやLinkedListでまともな性能が出ない。
もちろん、特定のケースでは同等性能が出ることはあるが。
176:デフォルトの名無しさん
21/11/22 01:08:41.45 saDsX792.net
なお、今言ったことは、未踏や研究テーマで扱うことは禁止する。
177:デフォルトの名無しさん
21/11/22 01:32:04.72 saDsX792.net
>>172
[補足2]
通し番号ではなく、ポインタでノードを識別することで、末尾以外のノードを
削除した時でも、識別番号の書き換えが不要であるメリットもある。
ポインタとはアドレスを保持する変数のことであるが、リンクリストや
ツリー構造の場合、途中のノードを削除しても、別のノードのアドレス
は全く変化しないので、削除したノード以外のポインタ値は全く変更されないので
書き換えも必要ないからである。
一方、初心者がやりがちなのは、リンクリストでも先頭のノードを0番にして、
それ以後のノードを1、2、3 という通し番号で識別しようとする方法。
これだと、5番のノードを削除した時、6番以後のノードは番号の付け替えが
必要になるのでものすごく効率が下がる。
また、k 番のノードをアクセスする際には、O(k)の時間が掛かってしまう。
本来、Cではノードを識別するのは、このような通し番号ではなく、
ポインタ(アドレス)で行うのが伝統であって、アルゴリズムの教科書でも
それが前提になっている。
それがいつからか、リンクリストでも通し番号で識別する流儀を誰かが持ち込み
初めて混乱が生じるようになった。
178:デフォルトの名無しさん
21/11/22 01:46:12.87 4Q+A1yLL.net
>>171
日本語読めます？
ソースコードをくれって言っている
179:165
21/11/22 02:04:09.01 43z4eYfr.net
>>169,172
なるほど、そうなんだ
でも正直、なにを言ってるのかまだよくわからんから、ちょっとベンチマークを投稿して遅さを示してみてくれん？
Linked Listの実装なんてその投稿よりも圧倒的に短く書けるとおもうし、ちょっとやってみせておくれ
180:デフォルトの名無しさん
21/11/22 10:14:51.86 ejqG4gpN.net
pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>
This is a nightly-only experimental API. (linked_list_cursors #58533)
CursorMutのStabilisedがまだ来てないことへの批判ってこと？
181:デフォルトの名無しさん
21/11/22 10:24:02.08 EEj8G+es.net
>>157
> Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセスできない
どんな言語で書いてもO(1)でランダムアクセスできないのでRustでも同様にO(1)でできないのは当たり前
一般的にランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
C言語でもO(n)でありO(1)では不可能
182:デフォルトの名無しさん
21/11/22 11:08:38.58 0RwULqeG.net
>>178
リンクリストとポインタを学び直してから出直せ。
183:デフォルトの名無しさん
21/11/22 11:37:54.58 0LbM6y2O.net
あと何回Cursorって言えばいいんですか？
184:デフォルトの名無しさん
21/11/22 11:50:19.99 EEj8G+es.net
>>179
君はプログラムを書いたことがないのかね？
どんな言語でもランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
O(1)でできると主張するならば実行可能なソースコードを出しなさい
185:デフォルトの名無しさん
21/11/22 12:28:55.95 8vjqlXjx.net
説明足りてないな。
「過去に一度対象となるコンテンツのポインタを確認&記録している場合」じゃなきゃO(1)は無理だろ。
186:デフォルトの名無しさん
21/11/22 13:01:13.80 ejqG4gpN.net
あ、CursorMutの指摘は既にされてんのねｗ
187:デフォルトの名無しさん
21/11/22 13:15:10.95 EEj8G+es.net
>>182
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)の移動が発生する
つまりどんな言語でもO(1)は絶対に不可能
188:デフォルトの名無しさん
21/11/22 17:14:17.10 HWCOZSD4.net
>>181
そう思うのは、ランダムアクセスの定義をあなたが誤解してるからだ。
確かに、リンクリストに置いて、何の情報も無く「k番目」のノードに
アクセスするにはO(k)の時間が掛かる。
しかし、そのアクセス方法は、ランダムアクセスする場合に必須ではない。
p1, p2, ..., p_a
というa個のポインタがあって、それをランダムに選び取ってアクセスする場合の
1つあたりに掛かる時間が、O(1)であれば、ランダムアクセスの時間はO(1)
だと言えるから。
連続アクセス以外は、全てランダムアクセスなんだ。
具体的には、最初から100個のノードのアドレスを、100個のポインタに記録していたとしよう。
そのポインタは、リンクリストの中の位置で見ると、連続して並んでいるわけではないとする。
そのポインタを順番に参照してリンクリストのノードをアクセスすれば、連続アクセスでは無いから、
ランダムアクセスに分類される。
もう一度言おう、連続的な位置では無いノードを複数個アクセスすればランダムアクセスだ。
IQが低い人は、こういうトンチのようなものに弱い。
だから、IQの高い人とIQの低い人では誤解が生じ、大変な結果となる。
189:デフォルトの名無しさん
21/11/22 17:17:59.19 HWCOZSD4.net
>>184
どうしてあなたは、2つの概念を切り分けられないんだ。
kを任意に与えられてk番目のノードをアクセスするには、確かにO(k)の
時間が掛かるが、ランダムアクセスは、最初からアドレスが分かっている
ノードをa個アクセスした場合の1つ当りのアクセスに掛かる時間でも
いいんだから、必ずしもO(k)ではなく、O(1)になる場合がある。
数学は精密な学問だから、場所をランダムにアクセスすることと、
毎回kという通し番号が与えられて毎回前から順番に辿ることとは
全く別の事象である。
ちなみに俺は、数学は毎回100点とっていたような数学マンだ。
190:デフォルトの名無しさん
21/11/22 17:18:11.48 EEj8G+es.net
>>185
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)を必要とする移動が発生する
つまりどんな言語でどんな手法でもO(1)は絶対に不可能
191:デフォルトの名無しさん
21/11/22 17:26:17.83 HWCOZSD4.net
IQが低い人向けに書いておこう。どうせ書いても理解できないかも知れないが。
リンクリストの中にx0～x_{N-1}のN個のノードがあったとしよう。
ランダムアクセスの定義は、「連続アクセス以外の全てのアクセス方法」であるので、
以下のようになっている:
[連続アクセス]
x0,x1,x2,x3,x4,...
[ランダムクセス]
x10,x1,x8,x5,x3,x7,x100,x6,x200,...
ここで、馬鹿をさらしている人達は、ランダムアクセスは、毎回
通し番号kを乱数で発生させてからアクセスするものだと誤解している。
それは数学的には0点である。
ランダムアクセスとはそのような定義ではないからだ。
とにかく、「連続アクセスでなければなんでもいい」というのが正しい定義。
だから、キメウチで最初から、
&x10,&x1,&x8,&x5,&x3,&x7,&x100,&x6,&x200,...
というアドレスの列が分かっていて、それを順番にアクセスすれば、
ランダムアクセスの定義にあてはまる。
そしてそのようにしたとき、1回当たりに掛かる時間がO(1)である、
というのが、数学的に正しい見方。
何度も言うが、俺は、数学はほとんど満点だった。
繰り返し言うが、リンクリストに置いて、ノードへのランダムアクセスに
必要な時間は、O(1)が正しい。O(N)と思ってるのは、ランダムアクセスの定義
を誤解している。
O(N)かかるのは、リンクリストに置いて「通し番号からノードのアドレスを求めるのに掛かる時間」
である。リンクリストに置いて、通し番号からノードのアドレスを求めることは、
ランダムアクセスには一般的には不要である。だから、O(1)で正しい。
192:デフォルトの名無しさん
21/11/22 17:29:51.54 HWCOZSD4.net
>>187
だから、それはランダムアクセスの定義では無いんだと何度入ったら分かるんだよ。
どうして、k番目を乱数で与えると思ってるんだ。
ランダムアクセス度は、「ランダム数で与えられたノードでアクセスする」
ことではなく「ランダムな位置のノードをアクセスするためこと」だぞ。
数学的には全く別概念だ。
何でも言うが俺は、数学はほぼ満点だった。
193:デフォルトの名無しさん
21/11/22 17:33:29.42 ejqG4gpN.net
URLﾘﾝｸ(play.rust-lang.org)
#![feature(linked_list_cursors)]
fn main() {
use std::collections::LinkedList;
let mut list = LinkedList::from([1, 2, 3]);
let mut cursor = list.cursor_front_mut();
cursor.move_next();
println!("{:?}", cursor.current()); // Some(2)
cursor.insert_after(20); // O(1) insertion
println!("{:?}", list); // [1, 2, 20, 3]
}
194:デフォルトの名無しさん
21/11/22 17:33:38.88 HWCOZSD4.net
例えば、位置が最初から分かっていても、どうやってもランダムアクセスが
遅くなる例としては、テープレコーダーがあげられる。
これは、どう頑張っても、長さNに対して、O(N)の時間がかかってしまう。
繰り返しになるのが、リンクリストの場合は、O(1)だ。
ただし、先頭からの通し番号 k を与えられた時に、データが有るアドレスを計算するのに
掛かる時間は、O(k)だ。
しかし、ランダムアクセスに掛かる時間はO(1)だ。
この違いが分からない人は数学が出来なかったことであろう。
195:165
21/11/22 17:35:33.12 43z4eYfr.net
理屈はもういいので、プログラミングできるならベンチマークを出して、他の言語より遅いことを示してくれませんか？
196:デフォルトの名無しさん
21/11/22 17:38:53.52 43z4eYfr.net
ってあれ、 ID:saDsX792 と別人かな
197:デフォルトの名無しさん
21/11/22 17:38:58.35 HWCOZSD4.net
何故これが重要となるかといえば、実際にこの性質を利用して、
C言語では古くから、リンクリストをO(1)の時間でランダムアクセスして
きたからだ。O(k)ではなく、O(1)だ。
この例としては、リンククリストの中の不連続な100個のノードのアドレスを
どこかの配列にいてれておいて順番にアクセスする例がある。
この場合、一個当りの平均アクセス時間はO(1)、全体に掛かる時間はその100倍で済む。
しかし、アドレスではなく、ノードを通し番号で識別した場合、
一個当りの平均アクセス時間は、O(N)、全体に掛かる時間はその100倍になってしまう。
この意味に置いて、アドレス(ポインタ)でノードを識別することに徹すれば、
リンクリストにランダムアクセスする時間は、O(1)である。
しかし、このようなアクセス法は、Rustは一般的には無理。
198:デフォルトの名無しさん
21/11/22 17:39:58.88 HWCOZSD4.net
>>192
プログラミングは理屈が重要。
O(1)の記法も実験せずに思考実験で結論を得るためにある。
199:デフォルトの名無しさん
21/11/22 17:41:09.75 43z4eYfr.net
ああ、 ID:HWCOZSD4 が書いてるのは当然のことだ
200:デフォルトの名無しさん
21/11/22 17:48:40.73 43z4eYfr.net
「Rustだとできない」っていうのはよくわからないし、そこだけ気になってるんだけど、
Rustって参照を持ち回すことがそんなにできないんだ
201:デフォルトの名無しさん
21/11/22 17:49:16.27 EEj8G+es.net
C言語であろうがなかろうが言語に関係なくO(1)は無理
わからない人はコーディングすればすぐわかる
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別の配列で保持管理しないといけない
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理する配列で毎回O(n)を必要とする移動が発生
どんな言語でどんな手法を用いてもO(1)は絶対に不可能
202:デフォルトの名無しさん
21/11/22 17:53:40.47 ejqG4gpN.net
>>198
俺もそう思う
彼の主張にはポインタの配列をケアする時間を含んで無さそうに聞こえたけどｗ
せっかくのリクリストとは別にアクセス用のポインタ配列をケアするってことも
ふしぎなコーディングだけど
そこまでするなら最初から配列だけでやれって思うけどｗ
203:デフォルトの名無しさん
21/11/22 17:55:47.65 HWCOZSD4.net
>>198
その別の配列に用意したアドレスに基いてアクセスすれば、立派なランダム
アクセスなんだ。
ランダムアクセスとは、毎回デタラメにアクセスすることでは無いぞ。
テープレコーダーの場合、キメウチで、100, 1, 200, 10, 30, 2, 1000
の位置の7個のデータを取得するには、シーク時間が必要だから、
100+99+199+190+20+28+998 の時間が掛かる。
そしてこの読み取りを2回行ってもまた同じだけの時間が掛かる。
その意味で、ランダムアクセス時間は、テープの長さがNの時、O(N)とされている。
ところが、リンクリストの場合、アドレスが毎回決まっている 7 個のデータ
をアクセスするには、一個当りのノードに掛かる平均時間は O(1)だ。
これを2回行っても同じ。
あなたがおもっているような、シーク時間はリンクリストの場合には不要だから。
204:デフォルトの名無しさん
21/11/22 17:56:50.13 HWCOZSD4.net
>>199
そうでなくて、その配列が既に決まっている場合もあるんだということだ。
それを上手く用意することが出来るケースが現実にかなり有る。
205:デフォルトの名無しさん
21/11/22 17:57:28.92 ejqG4gpN.net
いや配列ケアのほうは時間はそれほどでもないか
挿入削除場所以降のコピーする必要が出るだけで
206:デフォルトの名無しさん
21/11/22 17:59:39.65 ejqG4gpN.net
>>201
へー
207:デフォルトの名無しさん
21/11/22 17:59:44.70 HWCOZSD4.net
なぜかというと、アドレスは、ノードを追加した時に分かるから、それをどこかに
記録しておけば「シーク時間」が不要だから。
例えば、100個のノードを任意の位置に追加したとしよう。そのアドレスは、
100個分は既知である。そのアドレスをまたどこかのリンクリストの末尾に
でも順番に追加して全て記録しておいたとしよう。
そうすると、元のリンクリストは、立派にO(1)でランダムアクセスできるんだ。
208:デフォルトの名無しさん
21/11/22 18:00:15.83 43z4eYfr.net
> リンクリストの場合、アドレスが毎回決まっている 7 個のデータをアクセスするには、
> シーク時間はリンクリストの場合には不要だから。
そら、あらかじめアドレスがわかってればできるだけで、別にLinked Listの性質ではないよね
209:デフォルトの名無しさん
21/11/22 18:01:09.38 EEj8G+es.net
>>200
そこでO(1)とは配列のアクセスのみ
つまりリンクリストは全く関係なく配列のアクセスがO(1)だと主張していることに気付こう
そしてリンクリストで削除や挿入が行われるたびにその配列でO(n)の大移動が行われる
結論: O(1)ではどんな言語でもプログラミングできない
210:デフォルトの名無しさん
21/11/22 18:02:14.47 HWCOZSD4.net
>>206
そんなことない。
あなたは、ポインタを使ったプログラミング経験が浅い。
211:デフォルトの名無しさん
21/11/22 18:04:00.68 HWCOZSD4.net
>>205
そうでない。
テープレコーダーとリンクリストでは、明らかにランダムアクセスに掛かる時間の
性質が違う。
「アドレスが既知」であるのは、ポインタを全面的に使ったプログラミング法
では当たり前の事だから、リンクリストに置いてシーク時間は不要。
212:デフォルトの名無しさん
21/11/22 18:05:44.36 HWCOZSD4.net
>>206
違う。
ツリーの場合でも、番号ではなく、ノードをポインタで識別することで、
0の時間でシークできる。
リンクリストでも同じ。
通し番号を使おうとするから遅くなってるだけ。
ノードの識別をポインタで統一してしまうと、本当に O(1)でいける。
213:デフォルトの名無しさん
21/11/22 18:07:52.10 EEj8G+es.net
>>204
あなたの主張を整理すると
「k番目をO(1)でアクセスできる配列」は「k番目をO(n)でアクセスできるリンクリスト」よりも優れている、となる
O(1)の部分はリンクリストと全く無関係であることに気付かないとね
ここまで壮大な勘違いをしてるのはおそらくプログラミングをしたことがないのだろうけど
214:デフォルトの名無しさん
21/11/22 18:09:34.28 43z4eYfr.net
アドレスへのランダムアクセスは定数オーダー。そりゃメモリはそういう設計で作られてるんだから当然
テープレコーダーはランダムアクセスできない。これも当然
なんでテープレコーダーと、メモリ上に実装したLinked Listを比較しているのか意味がわからない
何を説明しようとしてるんだろう
215:デフォルトの名無しさん
21/11/22 18:10:17.50 ejqG4gpN.net
>>206
なんか話途中から首突っ込んだけど
結局はそういうしょうもないオチっぽいなこれｗ
ポインタの指す先のデータ構造に一切関わらず
アクセス用のポインタを回収して配列にするんならそりゃO(1)だもんな
そしてわざわざそれをしたいという動機もよーわからんかった
216:デフォルトの名無しさん
21/11/22 18:12:45.44 HWCOZSD4.net
例えば、データベースの様なものが有ったとしよう。
個人情報がリンクリストに入っているが、ID番号と個人情報は別に配列の中に
入っていて、ID番号の構造体には、リンクリストのノードのアドレスも
入っているとする。
これだと、ID番号を全て巡って、それぞれの個人情報を巡る時、
個人情報の1個当りのアクセスに掛かる平均時間はO(1)だ。
しかし、ノードのアドレスの変わりに、ノードの通し番号を入れてしまって
いたとすると、ノードをシークするためにO(N)の時間が掛かってしまう。
なので、ノードの識別をポインタにしてしまえば、O(1)で、通し番号に
してしまえばO(N)の時間が掛かる。
だから、リンクリストを使う場合には、通し番号ではなく、ポインタを
使うことが推奨されている。ところが、Rustではそれがほぼ不可能。
217:デフォルトの名無しさん
21/11/22 18:14:22.43 43z4eYfr.net
へー、Rustってそんなこともできないんだ
218:デフォルトの名無しさん
21/11/22 18:15:23.83 HWCOZSD4.net
>>210
いや、ノードの識別をアドレスで行いさいすれば、
リンクリストと配列のランダムアクセスに掛かる時間はどちらもO(1)だから
リンクリストが劣っていることは無い。
なぜなら、乱数で与えられた位置のノードをアクセスする必要は無いから。
ランダムアクセスする場合でも、アクセスすべき位置は、アドレスで決まっている。
シークの時間は不要。
219:デフォルトの名無しさん
21/11/22 18:16:52.13 HWCOZSD4.net
>>214
次の借用規則に引っかかる。
・1個でも書き込みの参照が有る場合、読み込み参照は1つも持てない。
書き込み参照も1個しか持てない。
220:デフォルトの名無しさん
21/11/22 18:26:59.33 5egSOJea.net
>>214
Rustが次々とC/C++の領域を置き換えていってるように
両者で実現できることは同じ
彼はアルゴリズムとオーダーについてもよく理解できていないだけでなく
Rustについても全く理解していない
221:デフォルトの名無しさん
21/11/22 18:28:27.85 43z4eYfr.net
なるほど。もうちょっとRust覚えたらそういうデータ構造も自分で実装して試してみるよ
222:デフォルトの名無しさん
21/11/22 18:31:34.64 HWCOZSD4.net
>>217
計算時間のオーダーが全く違ってくる。
データベースなどは速度やメモリー効率を高めるために、さまざまな構造を
駆使して作られていることが有り、Rustでは自由に作ることが難しいことが
有り得る。
100万行のテキストエディタの先頭に1000行のデータをペーストするような
時にもリンクリストが大活躍する。単純な配列では遅すぎて駄目。
223:デフォルトの名無しさん
21/11/22 18:34:23.79 HWCOZSD4.net
>>217
あなたは、データ構造やポインタを深く理解して無いか、
高度な実践的プログラミング経験が浅いかのどちらか。
224:デフォルトの名無しさん
21/11/22 18:41:12.00 EEj8G+es.net
>>219
やはりプログラミングしたことがないようだな
そこで50万行目に行く場合に配列併用なし実装だとリンクを50万回たどるO(n)
配列併用あり実装だと50万行目へ一気に行けるO(1)が挿入削除時のたびに配列内で大移動O(n)
つまりO(1)になっているのは配列アクセスのみ
225:デフォルトの名無しさん
21/11/22 18:45:29.95 HWCOZSD4.net
>>221
リンクリストAの中のランダムな位置のノードのアドレスを、
別のリンクリストBに入れておいて、Bの先頭から順番にループすれば、
リンクリストAのノードをランダムアクセスできるが、その時の
一個のノードあたりの平均アクセス時間はO(1)だ。
ここに配列は一個も出てこない。
226:デフォルトの名無しさん
21/11/22 18:51:10.61 5egSOJea.net
>>222
それ、あるkが与えられたときにk番目のアクセスがO(n)になってる
それがリンクリストの性質
ランダムアクセスすなわちk番目のアクセスはO(1)の配列が圧倒的に有利
227:デフォルトの名無しさん
21/11/22 18:54:15.44 HWCOZSD4.net
>>221
それはテキストエディタでは結構問題になる部分だが、
実際的には、ページ単位の大きな移動は文字挿入や文字削除などの編集操作に比べて時々しか
行わないことと、現在位置から相対的な移動距離は大きくないことが多いことから、
行の記憶は配列ではなくリンクリストにしておく手法を取ると良い。
実際に行の記憶を何も配慮せずに配列でやると、ペーストした時にとても遅くなる。
一方、行の記憶をリンクリストにすると、実際問題はかなり快適になる。
スクロールなども速い。
一気に決め打ちの行番号に移動するのはO(N)の時間が掛かることはかかるが、
決め打ちの番号に移動することは、たまにしか行わないので遅くは感じない。
228:デフォルトの名無しさん
21/11/22 18:55:48.2
229:9 ID:HWCOZSD4.net
230:デフォルトの名無しさん
21/11/22 18:59:38.49 HWCOZSD4.net
>>223
ランダムアクセスとランダムに生成した通し番号 k のノードにアクセスする
ことは別の概念だぞ。
231:デフォルトの名無しさん
21/11/22 19:03:37.90 kGsgeZzB.net
結局Rustで実装できないテキストエディタ向けのデータ構造って具体的にはなんなんだ…
ropeもgap bufferもpiece tableも普通にRust実装あるが
232:デフォルトの名無しさん
21/11/22 19:07:47.11 HWCOZSD4.net
>>227
それは、人の知らないものを出してきて、根本問題から目を背けさせる手法。
どんなcrateがあろうと、根本的に出来無い事がRustには有るという話をしてる。
233:デフォルトの名無しさん
21/11/22 19:18:39.97 4Q+A1yLL.net
>>228
だからそのデータ構造をCでもC++でもなんでみいからはよソースコードで示せ
234:デフォルトの名無しさん
21/11/22 19:19:12.02 5egSOJea.net
>>225
まずCプログラマーには常識だけど
インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
いずれにせよポインタを使うことでオーダーOが変わることはない
>>228
そんなウソをついて何がしたいのかさっぱりわからない
235:デフォルトの名無しさん
21/11/22 19:21:02.53 HWCOZSD4.net
>>230
>インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
>次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
>いずれにせよポインタを使うことでオーダーOが変わることはない
なんで、このスレはこんなにレベルが低いの。
236:デフォルトの名無しさん
21/11/22 19:21:28.08 HWCOZSD4.net
>>230
>そんなウソをついて何がしたいのかさっぱりわからない
真実だから。
237:デフォルトの名無しさん
21/11/22 19:27:10.84 DZQ1+JmR.net
>>232
数学の専門家であってプログラミング経験がないからソースコード出せとの指摘には一切答えられないということかな
238:デフォルトの名無しさん
21/11/22 19:32:17.29 fRCpO7Rh.net
>>194
ここであなたがおっしゃっているのは、以下のような実装のことでしょうか？
Element *array[] = {l0, l1, l2, l3, ...};
lnはリストのn番目の要素
239:デフォルトの名無しさん
21/11/22 19:43:59.25 HWCOZSD4.net
>>234
近いが、初期値が、{ &l5, &l1, &l123, &l25, ... };
のようになっているイメージ。
ただし、実際には、
・初期化子リストには書かず、プログラムの途中でリンクリストに挿入した直後に記録するような
ことが多い。
・ノードの識別を常にポインタで扱うので、& で書くことは無い。
・固定配列ではなく、それもまたリンクリストにすることが多い。
なぜなら、リンクリストは効率が良いことが多いから。
240:デフォルトの名無しさん
21/11/22 19:46:52.11 HWCOZSD4.net
>>233
そうではなく、
・大規模すぎて、こういうところには抽出して書ききれない。
・言葉で書いたほうが理解し易いはずだと思った。
抽象概念を理解しにくい人がこんなに多いスレだとは思わなかったから。
・しかし、これだけ書いても理解できないと言うことは、具体的に書いても
ますますそのコードの本質的な意味が理解できないと思われる。
241:デフォルトの名無しさん
21/11/22 19:57:10.45 43z4eYfr.net
中国共産党のお偉いさんって本当に偉いんですね
242:デフォルトの名無しさん
21/11/22 19:57:37.97 43z4eYfr.net
スレ間違えた まいいか
243:デフォルトの名無しさん
21/11/22 20:02:20.61 fRCpO7Rh.net
>>235
ある要素が複数のリストに所属するイメージでしょうか
例えば全要素が連なっているリストのn番目、特定の要素だけが抽出された別のリストのm番目に属すといったような
要素の削除に当たっては属するすべてのリストについて前後の要素からの参照を外す
244:デフォルトの名無しさん
21/11/22 20:03:50.15 5egSOJea.net
配列でもリンクリストでも他のコレクションでも全てに言えること
「格納要素が『データ本体でも、ポインタでも、何らかのid番号でも、他のインデックス番号でも、』そこは一切関係なく、様々な操作のオーダーOが変わることはない」
まずこの大原則をID:HWCOZSD4は理解できていないのたろう
だからポインタを使うと魔法のようにオーダーがO(1)になる
245:と勘違いしている
246:デフォルトの名無しさん
21/11/22 20:04:15.63 HWCOZSD4.net
>>239
今回例としてあげたのはそういうケース。
ただそれは一例であってさまざまなケースがある。
247:デフォルトの名無しさん
21/11/22 20:04:48.66 HWCOZSD4.net
>>240
アホか。
俺は現実世界では天才と言われてるのに。
248:デフォルトの名無しさん
21/11/22 20:05:43.93 fRCpO7Rh.net
>>241
この一例もやはりRustでは実装できないのでしょうか
249:デフォルトの名無しさん
21/11/22 20:07:17.81 HWCOZSD4.net
>>243
読み込みオンリーに限定して、一切削除もしないという条件なら可能。
ノードの中に書き込んだり、ノードを削除するなら、不可能。
250:デフォルトの名無しさん
21/11/22 20:08:42.39 HWCOZSD4.net
>>244
[補足]
C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能。
なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。
251:デフォルトの名無しさん
21/11/22 20:10:06.74 5egSOJea.net
>>243
C言語で可能なことはRustでも可能
>>244
嘘つき
252:デフォルトの名無しさん
21/11/22 20:11:54.24 4Q+A1yLL.net
>>236
gistでもどこでもいいからコード貼り付けてリンクここに貼ってください
日本語でうだうだ話すより議論が早く終わるでしょうあなたの言うことが正しければ
253:デフォルトの名無しさん
21/11/22 20:14:36.47 EEj8G+es.net
>>245
Rustでプログラミングをしたこともない人がデタラメな妄想を撒き散らしてるなｗ
254:デフォルトの名無しさん
21/11/22 20:14:53.48 HWCOZSD4.net
>>246
デタラメ一言ってんじゃないぞ!!
>>247
具体例を書いても、それはレアケースだの、本質的にはリンクリストの速度では
間違った評価が下るだけ。
そもそも、極簡単な話を書いてるのに理解できないのにコードを書いても理解できる
とは思えない。
そもそも、ランダムアクセスの意味すら理解出来て無い、ここの人達は。
255:デフォルトの名無しさん
21/11/22 20:15:30.95 HWCOZSD4.net
>>248
うそつきは黙れ。
256:デフォルトの名無しさん
21/11/22 20:18:44.14 HWCOZSD4.net
>>246
>>244 は、Rustの借用規則からそうなってる。
257:デフォルトの名無しさん
21/11/22 20:21:30.15 4Q+A1yLL.net
そもそもRustだって最悪UnsafeCell使えば1変数への多数読み書き参照は保持できるのだが
258:デフォルトの名無しさん
21/11/22 20:27:13.86 4Q+A1yLL.net
>>249
僕はリンクリストの速度がどうこう評価するつもりはあんまりなくて、
他言語で書かれたソースコードが本当にRustでは無理なのかを確認したいだけ
だから、その「Rustでは無理なコード」を見てみたい、と言っている
最悪ソースコードの中身は理解不能なものでもよい
259:デフォルトの名無しさん
21/11/22 20:27:43.67 43z4eYfr.net
>>249
説明するつもりもないのに、お前らはどうせ理解もできないバカだ、俺はいつも数学100点の天才だ、俺を信じろ
とか言ってても狂人扱いされるだけに決まってるじゃん・・・
260:デフォルトの名無しさん
21/11/22 20:29:18.57 0LbM6y2O.net
Cursorを使えと何回言っても聞かない
テキストエディタの例では>>119のアイデアを完全無視
261:デフォルトの名無しさん
21/11/22 20:50:09.64 MtEs+7mt.net
おれも興味があるな
C++では書けてRustでは書けないコード
リソースを無視すればチューリング完全だろうから
書けないなんて事はないはずで
何かしら制限を付けた上での「書けない」なんだろうけど
262:デフォルトの名無しさん
21/11/22 20:55:11.07 fRCpO7Rh.net
>>245
Rust でも書けるように思えてしまったのですが、以下のコードはどこが間違っているのでしょうか
URLﾘﾝｸ(play.rust-lang.org)
263:デフォルトの名無しさん
21/11/22 21:10:18.70 ejqG4gpN.net
>>216
プログラマを守るためそれをさせないのがRustっていう言語ではｗ
Rc<RefCell>ではいかんの？
URLﾘﾝｸ(play.rust-lang.org)
fn main() {
use std::collections::LinkedList;
use std::rc::Rc;
use std::cell::RefCell;
let mut list: LinkedList<Rc<RefCell<i32>>> = LinkedList::new();
list.push_back(Rc::new(RefCell::new(1)));
list.push_back(Rc::new(RefCell::new(2)));
list.push_back(Rc::new(RefCell::new(3)));
println!("{:?}", list); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
let mut vec: Vec<Rc<RefCell<i32>>> = Vec::new();
let mut it = list.iter();
vec.push(Rc::clone(it.next().unwrap()));
vec.push(Rc::clone(it.next().unwrap()));
vec.push(Rc::clone(it.next().unwrap()));
println!("{:?}", vec); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
println!("{:?}", vec[1]); // RefCell { value: 2 }
*vec[1].borrow_mut() = 22;
println!("{:?}", vec[1]); // RefCell { value: 22 }
println!("{:?}", list); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
println!("{:?}", vec); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
}
264:デフォルトの名無しさん
21/11/22 21:13:26.74 7gi7NmEv.net
>>255
Cursorでも無理だ。
265:デフォルトの名無しさん
21/11/22 21:14:06.15 ejqG4gpN.net
あっコメントはミスってる
実行結果はこちら
[RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
[RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
RefCell { value: 2 }
RefCell { value: 22 }
[RefCell { value: 1 }, RefCell { value: 22 }, RefCell { value: 3 }]
[RefCell { value: 1 }, RefCell { value: 22 }, RefCell { value: 3 }]
266:デフォルトの名無しさん
21/11/22 21:17:24.64 DZQ1+JmR.net
Rustの実装 (>>257) はポインタでの直接アクセスではなく配列への添え字アクセスだからオーバーヘッドが大きいとか言い出したらみんなで笑ってあげましょう
267:デフォルトの名無しさん
21/11/22 21:26:20.75 7gi7NmEv.net
>>257
独自のLinkedListで、実装としては配列を持っていて、
ノード間が参照でリンクされておらず、添え字番号でリンクしており、
get(), set()が添え字番号を返して配列要素を返しているので
ゼロコストではないね。
struct LinkedList<T> {
first_idx_a: Option<usize>,
first_idx_b: Option<usize>,
elems: Vec<Elem<T>>,
}
struct Cursor {
a_idx: usize,
}
fn get(&self, elem: Cursor) -> &T {
&self.elems[elem.a_idx].data
}
fn set(&mut self, elem: Cursor, data: T) {
self.elems[elem.a_idx].data = data;
}
268:デフォルトの名無しさん
21/11/22 21:27:13.68 7gi7NmEv.net
>>261
ゼロコストが謳いなのに、ゼロコストで無い。
269:デフォルトの名無しさん
21/11/22 21:27:14.40 5egSOJea.net
>>257
それで実装も動作も良いけど
_bはどちらも不要
_a.0と_a.1はそれぞれprevとnextと書いたほうが読みやすい
270:デフォルトの名無しさん
21/11/22 21:33:11.94 fRCpO7Rh.net
>>264
_b は単一の要素が複数のリストに属するという要件に対する実装ですね
面倒だったのでメンバーだけ用意して実装はしてないですが
タプル使ってるのも構造体定義が面倒だったため
というかできるできないを実証するための例なので細かいところは適当です
お好きなように修正してください
>>263
>>245 の
> C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能
> なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。
というのはほかの言語ではゼロコストで実装できることを意味していますか？
それともRustでも実装できることを認めた上でのただの負け惜しみですか？
はたまたこれを書いたのは自分とは別の人と主張されるのでしょうか