C++ vs Rust

1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net] 競え 2 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 09:03:31.43 ID:CqGuC/ho.net] 何で？ 3 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 09:10:09.42 ID:MAG7Rri7.net] どちらも変なプライド拗らせたアホしかいない印象 4 名前：デフォルトの名無しさん [2021/04/24(土) 10:50:18.68 ID:N1eYD/7j.net] C++: ｶﾐｿﾘ Rust: 安全ｶﾐｿﾘ 5 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 11:18:00.79 ID:gMqF1SGc.net] 別に〜 裏方一緒だし 6 名前：デフォルトの名無しさん mailto:sage [2021/04/25(日) 11:37:52.88 ID: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 名前：デフォルトの名無しさん mailto:sage [2021/04/25(日) 11:57:11.84 ID:Ef2Yns/P.net] Copy trait実装してたら暗黙的に実行されるわ。 とはいえc++のそれよりかは分かり易いけど。 8 名前：デフォルトの名無しさん mailto:sage [2021/04/25(日) 13:18:15.15 ID: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 名前：デフォルトの名無しさん mailto:sage [2021/04/25(日) 17:13:07.94 ID:In1fvQYU.net] 要はRustの代入ってmemcpyで、単純なmemcpyされると困るデータ(!Copy)の場合右辺がinvalidate(move)され使えなくなる って理解がシンプルなのかな 10 名前：デフォルトの名無しさん mailto:sage [2021/04/25(日) 18:00:12.34 ID:S2tV53BX.net] >>9 x = y の時、 結果的にはほとんどmemcpy(&x,&y,サイズ)に近い動作になっているかもしれないな。 ただ、右辺yの構造体メンバの中にRc<T>のような複雑なものが入っている場合、 結果は単純コピーのようになったとしても、コンパイラはもっと丁寧に処理 しているのではなかろうか。 11 名前：デフォルトの名無しさん mailto:sage [2021/04/26(月) 01:44:08.26 ID:+85I2LX6.net] >>10 move は memcpy だよ Rc も実体はヒープへのポインタだから memcpy で問題ない memcpy してはいけない例としては async fn みたいな自己参照構造体などがあるけど Pin をうまく使うことで変な状態にならないようにしている 12 名前：デフォルトの名無しさん [2021/04/26(月) 17:23:54.42 ID:92SW7900.net] c++に批判的な姿勢で知られるlinusがなぜrustにはwelcomeな態度取ってるのかが理解できない rustだってメモリ安全性がなければc++みたいなもんだろ 13 名前：デフォルトの名無しさん mailto:sage [2021/04/26(月) 17:27:49.70 ID:oHxAx7LN.net] 言うほどwelcomeか？ 14 名前：デフォルトの名無しさん [2021/04/26(月) 17:29:26.57 ID:92SW7900.net] >>13 貶すまではいってないじゃん 15 名前：デフォルトの名無しさん [2021/04/26(月) 18:48:21.42 ID:pZ6mft9e.net] あわしろ氏もRustは凄いって言ってましたね。 C++をあまり好きじゃないところも同じ。 16 名前：デフォルトの名無しさん mailto:sage [2021/04/26(月) 20:08:40.47 ID:cN+lbm0F.net] >>12 c++にもだいぶ甘くはなってるよ。 ただそれでもrustに対してもそこまで容認的ではない。 試しにドライバー書いてみれば？って言って試させてるが、まだまともには考えてないわ。 https://lkml.org/lkml/2021/4/16/901 17 名前：デフォルトの名無しさん [2021/04/26(月) 20:27:04.95 ID:92SW7900.net] >>16 むしをrust側に対して例外処理の方法をカーネル内での往来の方法に変更してくれって促しているように見えるんだけど 導入したがってるやんけ 18 名前：デフォルトの名無しさん mailto:sage [2021/04/26(月) 20:51:20.12 ID:cN+lbm0F.net] >>17 続きを読めば？どういう流れかわかるから。 19 名前：デフォルトの名無しさん [2021/04/26(月) 21:27:22.23 ID:92SW7900.net] >>18 続きで懐疑的な立場取ってんのlinusじゃなくね？ 20 名前：デフォルトの名無しさん mailto:sage [2021/04/26(月) 22:53:32.32 ID:cN+lbm0F.net] >>19 話の流れは大体予想できてただろうなという受け答えだろ。 んでもって実際、発案者自らmoonshot言うとるわ。 少しは内容を読んでくれ、なんで一から十まで説明しなきゃならんのか。 21 名前：デフォルトの名無しさん [2021/04/26(月) 23:32:00.78 ID:92SW7900.net] >>20 じゃあレスすんなよカス 22 名前：デフォルトの名無しさん mailto:sage [2021/04/26(月) 23:47:01.17 ID:cN+lbm0F.net] だから読めって。。文盲なんか？ 23 名前：デフォルトの名無しさん mailto:sage [2021/04/27(火) 00:14:36.96 ID:H90KgUtd.net] >>20 moonshotって言ってるの割り込みコンテキストでallocator呼び出すことをコンパイル時にチェックできるようにしたいという話では 現実的には関数ごとにどのコンテキストで呼び出せるものなのかタグ付けしてるとかなんとか 綺麗じゃないけど、まあ動くわなという解決策 つまみ食いしかしてないから読み違えてるかも知れないけど これをもってlinuxカーネルにrust取り込むのを否定するような話ではないようにみえた 他にもmoonshotって言ってる箇所ある？ 24 名前：デフォルトの名無しさん mailto:sage [2021/04/27(火) 01:12:51.08 ID:VJIOoOWO.net] 一通り読んだけど他にmoonshotって言ってるとこはなかったような。 25 名前：デフォルトの名無しさん mailto:sage [2021/04/27(火) 08:00:23.09 ID:/+bIFNU8.net] >>23 あのね。。書けばそうなるってものじゃなくてそれを実装しなきゃならんのよ。。 コンパイラにそういったコンテクストを判断させるのがめちゃくちゃ難しいっていってるでしょ？ なんでそんなに読み取れないの？ 26 名前：デフォルトの名無しさん [2021/04/27(火) 15:37:12.22 ID:Nn42Sot0.net] >>25 当面はdoc commentにannotation書いて済ませておくって言ってるやん 何はともあれ大局的にはrustをlinux kernelに取り込む方向へ進んでいくことには間違いない 27 名前：デフォルトの名無しさん mailto:sage [2021/04/27(火) 16:10:45.63 ID:/+bIFNU8.net] >>26 だからそのコードじゃpanic捉えきれねーからカーネルに入れるわけねーだろって 言ってんじゃん。。何読んでんだよ。 28 名前：デフォルトの名無しさん mailto:sage [2021/04/27(火) 18:23:48.67 ID:n/AWrch2.net] まあ半年後どうなるかで誰が正しかったかは分かるわな 29 名前：デフォルトの名無しさん mailto:sage [2021/04/27(火) 20:32:29.92 ID:/+bIFNU8.net] 半年も経たなくてももうわかってるっつーの。。だからちゃんと英語の勉強しましょうね。 30 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 03:52:50.81 ID: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 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 03:55:12.80 ID: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 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 04:01:18.27 ID: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 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 10:37:51.57 ID:6K8rF/jG.net] let mut a = Box::new([0,n]); 34 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 12:44:00.99 ID:jQpDsyge.net] >>33 なるほど、そんな書き方があったとは。でも正しくは、 let mut a = Box::new([0; n]); かな？ 35 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 15:21:28.78 ID:jQpDsyge.net] [0; n] って、n 要素のi32配列を確保して0で初期化するという意味らしいけど、 nは実行時に決まらないような変数も指定できるの？ 36 名前：デフォルトの名無しさん mailto:sage [2021/04/28(水) 16:30:39.18 ID:BfdKSrwu.net] >>35 できない https://stackoverflow.com/questions/41710952/allocate-array-onto-heap-with-size-known-at-runtime Vec<i32>に相当するのはstd::vector<int>だから、 >>33はstd::unique_ptr<int []>相当のBox<[i32]>型の例を出そうとしたのだろう そういう値は作れるが、Box::newでは無理 37 名前：デフォルトの名無しさん [2021/08/31(火) 15:22:27.39 ID: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 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 16:19:11.51 ID:KWeLtswn.net] コード例と性能測定結果くれ 39 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 17:18:36.26 ID:SlncBcTV.net] >>38 同じ動作をしてもVectorだとO(N)なのに、LinkedListだとO(1)になるものがある。 これだけでも実験してみなくてもNが大きくなった時に明らかに速度が 違うことはコンピュータ科学では常識。 例えば、コロナの感染者数は、O(exp(aN))になるので、どんだけ頑張っても、 Nが十分大きい時にはO(N^b)が上回ることは出来ない。 40 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 18:26:05.32 ID:8qO1h2Cp.net] まだstable入りはしてないけどlinked_list::{Cursor, CursorMut}っていうのがあるね その 41 名前：ベンチマークでは使ってる？ [] [ここ壊れてます] 42 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 19:03:52.76 ID:WFW0JNLV.net] LinkedListとはなんぞや？std::list? 43 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 19:52:34.92 ID:4dUmDNFP.net] >>39 Rust は stable で LinkedList も VecDeque (双方向キュー)もありますよ https://doc.rust-lang.org/std/collections/index.html ここにそれらのオーダーが O(1) や O(N) になる話もまとまっています 44 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 21:21:08.46 ID:KWeLtswn.net] >>39 参照局所性の問題もあるから計算量の理論通りにはいかない場合もあるけど、ちゃんと性能測定してデータ構造選定した？ 45 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 21:26:21.55 ID:KWeLtswn.net] あとRustではほぼ不可能の意味が分からない Rust にはポインタがあるから C や C++ のデータ構造はほぼ実現可能なのでは 46 名前：ハノン mailto:sage [2021/08/31(火) 22:08:35.31 .net] >>44 では赤黒木をひとつやってみて 47 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 22:27:32.77 ID:wvWDiazC.net] >>45 Rc<RefCell<Node>>のパターン Safe Rustでも実現可能 48 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 23:58:27.88 ID:SlncBcTV.net] >>42 ところが、Rustでは借用規則のせいで上手く行かない。 めんどくさいので自分で気づく人だけが理解してくれればいいので、 俺はこれ以上説明しない。 理解できない人は、親切な人が説明してくれるのを待て。 49 名前：デフォルトの名無しさん mailto:sage [2021/08/31(火) 23:58:51.57 ID:SlncBcTV.net] >>44 無理。 50 名前：デフォルトの名無しさん mailto:sage [2021/09/01(水) 00:55:38.60 ID:MtyAaHfZ.net] >>47 それはあなたが無知なだけだ Rustはメモリ安全性を保証する 一方でRustの標準ライブラリではunsafeが多数使われているがこれはメモリ安全性を保証できる操作を効率よく実装するためにある つまり論理的にメモリ安全性を保証できるならばunsafeを用いてもそれをライブラリやモジュールに閉じ込めることができる もちろん自作でもこれは同様である 新たな型も当然作ることが可能 標準ライブラリで提供されているリンクドリスト型や双方向リスト型はそのようにして作られている つまり効率をも落とさない 51 名前：デフォルトの名無しさん mailto:sage [2021/09/01(水) 01:25:17.04 ID:+dwouIiT.net] >>49 お前は何も分かってない。 馬鹿は黙ってろ。 52 名前：デフォルトの名無しさん mailto:sage [2021/09/01(水) 01:27:41.34 ID:FA803rPU.net] >>40にも答えてくれよ その「問題」とやらはCursorじゃ解決されてないのかい 53 名前：デフォルトの名無しさん [2021/09/03(金) 08:12:39.26 ID:t+NhPRD1.net] >>49 ガイジ 54 名前：デフォルトの名無しさん mailto:sage [2021/09/07(火) 20:33:21.38 ID:ezLxFpG4.net] 結局unsafe多用するとか意味ないジャンw 55 名前：デフォルトの名無しさん [2021/09/07(火) 23:30:30.79 ID:W5eU3b0C.net] >>53 裏方のunsafeなコード(≠危険なコード)を安全に利用してプログラムを書けるのがRustだと思う また､その裏方のunsafeなコードをRustで書く意味はRustから扱いやすいこと､Rustプログラマーが慣れたRustの文法で書けることがあると思う 56 名前：デフォルトの名無しさん mailto:sage [2021/09/08(水) 01:30:18.74 ID:c9lCkxrV.net] >>54 お前の理解は浅くて、間違っている。 お前の様な数学の出来ない人には何を言っても無駄。 57 名前：デフォルトの名無しさん mailto:sage [2021/09/08(水) 01:30:55.64 ID:c9lCkxrV.net] unsafeを閉じ込め切れるならRustはパーフェクトだが、そうはなってないのだ。 58 名前：デフォルトの名無しさん [2021/09/08(水) 09:53:24.22 ID:8gtworgR.net] >>55 そうか､まぁ一個人の感想ぐらいに受け取ってくれ 59 名前：デフォルトの名無しさん [2021/09/09(木) 16:53:30.53 ID:lJRSMQ7p.net] なんだかんだ言ってまだまだC++だな 60 名前：デフォルトの名無しさん mailto:sage [2021/09/09(木) 17:22:38.75 ID:fa/WJTRs.net] unsafe を閉じこめられるかどうかはAPI設計力が問われるよな 61 名前：デフォルトの名無しさん mailto:sage [2021/09/09(木) 18:17:29.61 ID:18O2MBOf.net] >>56 Rustはunsafeを局所的に安全に閉じ込めることができます 例えばVec<T>型はその各メソッド実装においてunsafeを用いています これも『Rustがunsafeを局所的に安全に閉じ込めることができる』具体的な実例です >>58 C++よりもRustの方が優れています 62 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 08:39:25.32 ID:w07MHOd0.net] >>60 前半、数学的には間違い。 お前には数学の才能が無い。 63 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 09:06:15.40 ID:Ga+Uz44a.net] 数学関係ないし お前には数学の才能が無い 64 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 09:26:50.69 ID:XIGB6bHM.net] 数学的に間違いの意味がようわからんが、 unsafeブロック内あるいは関数内でSAFETYが守られるようにしないと安全に閉じ込めることができないって意味？？ 65 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 09:28:15.95 ID:KDfyX1FH.net] Vec<T> が unsafe を使って安全なインターフェースを提供してることへの反論を示してくれ 66 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:00:27.70 ID:4cVpX4oe.net] >>63 そうでなくて、unsafeブロックで閉じ込めようとしても、閉じ込め切れなくて、 O(x)で表される計算時間が、C言語とは同じでは絶対に不可能な場合があるんだ。 Rustのsafeモードでは、コンテナの中のノードに対して書き込み参照と読み込み参照 を持つことが借用規則によって禁じられていることが原因。 C言語ではそれが当たり前に出来るからとても効率の良いプログラムが可能だが Rustでは、unsafeの外側ではそれが出来ないから不可能だ。 アプリレベルでそれが出来ないから。 これで納得できない人は数学の才能が無い。 俺は数学の天才。 67 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:05:19.78 ID:4cVpX4oe.net] >>65 数学の才能が無い人のためにもう少し詳しく書いてやろう。 ・Rustのsafeモードでは、LinkedListの中の複数のノードに対して、 　読み込み参照と書き込み参照を一度自動時には持てない。 　持つと borrow cheker がコンパイル時にエラーを出してしまう。 ・C言語ではそれが当たり前に出来る。 ・アプリレベルで1つのLinkedListに対して複数の読み込み参照と 　書き込み参照を同時に記録し続けることで、やっと、挿入や削除が 　O(1)になる。index 値で保持すると O(N)になってしまうから、 　vector と同じ速度オーダーしか出ない(つまり、LinkedList本来の性能 　が全く出せない。) ・結果、Rustは、Cより遅いプログラムしか出来ない。その遅さは、データが 　多いとき、C言語に比べて1万倍でも100万倍でも遅くなる。 68 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:27:11.50 ID:2Djs9W2b.net] >>66 コードで書いて 69 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:30:01.67 ID:4cVpX4oe.net] >>67 RustとCの知識と、東大数学が簡単に解けるような数学の才能をすべてもっている人 に聴いてみろ。 70 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:36:42.07 ID:4cVpX4oe.net] >>68 本当は次のような知識も必要： ・リンクドリストの構造。 ・リンクドリストの挿入、削除などの計算オーダーO(x)。 ・計算オーダーの記号O(x)の意味。ビッグオー。ランダウの記号。 　東大、京大の学部レベルの解析学(微分積分学)の本を見よ。 ・index 値 = 基本は配列の添え字。0から割り振られた連番。 　リンクドリストでは本来使わないが、Rustではノードの場所を覚えておくために 　使わざると得ない。その場合、リンクドリストの先頭のノードを 0 番とし、 　次のノードを 1, その次のノードを 2 のように表す。 　しかしそうすると、リンクドリスとの M 番目の場所の参照を取得するのに 　O(M)の時間が掛かってしまい、リンクドリストの効率の良さが台無しになってしまう。 ・このことから、リンクドリストが遅いという誤解を生む状況になってしまっている。 71 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:38:10.81 ID:2Djs9W2b.net] >>68 東大数学って何？ 72 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:39:59.60 ID:4cVpX4oe.net] >>70 高校生が灯台に入学するときに受ける東大の数学の試験のことだよ。 それが簡単に解けるくらいのやつに聞いてみろって事だ。 しかし、受験テクニックやパターン学習によって解ける様になったやつはダメだ。 73 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:49:52.37 ID:2Djs9W2b.net] >>69 O(1) で i 番目の要素にアクセスできる safe な LinkedList 実装はある https://docs.rs/chainlink/0.1.0/chainlink/struct.LinkedList.html 74 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:52:48.63 ID:2Djs9W2b.net] >>72 i 番目の要素というと不正確か ポインタの代わりに Arena 内での index を使うことで LinkedList のノードを O(1) で参照することができる 75 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 11:53:08.66 ID:FsmeH+FF.net] https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=bc6e823f6a44e442aabd4d4882d3eb5a 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 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:09:20.46 ID:4cVpX4oe.net] >>74 アホですか？ >>73 Arenaを使った時点で裸のリンクリストじゃ無いし、時間は、O(x)が同じでも オーバーヘッドが発生する。また、無駄なメモリー領域も食う。 77 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:12:17.45 ID:Ga+Uz44a.net] >>68 呼んだ？ 78 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:14:53.57 ID:Ga+Uz44a.net] >>71 えっ？ 高校数学？ レベル低くないか？ 79 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:18:15.36 ID:Ga+Uz44a.net] 少なくとも>>65が書いてることは数学的でも何でもない 80 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:18:20.87 ID:FsmeH+FF.net] >>75 はい、私はアホで数学の才能が無いので数学の天才様の問題意識が分かりません VecならO(n)になる先頭への挿入がO(1)でできることを示したつもりでしたが見当違いでしたでしょうか 81 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:27:50.85 ID:4cVpX4oe.net] >>79 push_front()使ってるから先頭へ挿入してるだけじゃないか。 Cのリンクリストは、どんな非負整数 M に対して、M番目に挿入しても MにもNにも依存しない定数時間で挿入できる。 それがRustに欠けている。 82 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:28:54.60 ID:2Djs9W2b.net] >>75 そのオーバーヘッドは実用上問題になりますか？ 例えばmallocの実装もarenaを使っていますが問題はないのですか？ そもそも計算量の議論をしていたのはあなたなのになぜ論点をずらすのですか？ 83 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:30:48.00 ID:Ga+Uz44a.net] >>80 挿入自体が定数時間でも M番目を探すのが定数じゃない 84 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:41:50.91 ID:4cVpX4oe.net] >>82 「M番目」のMをそのまま「通し番号」で表しているならその通りだ、たとえC であっても。 しかし、Cでは、通し番号ではなくポインタで表現することで1クロックで 辿り付けるので O(1)。 85 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:42:38.21 ID:XIGB6bHM.net] >>65が何言ってるのか1行たりとも理解できなくて日本語の見た目した何かにしか見えないんだけど、 なんで話が進んでるの・・・ 86 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:08:34.28 ID:Ga+Uz44a.net] >>83 自分でM番目に挿入って書いてるわけだが 87 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:34:07.88 ID:4cVpX4oe.net] >>85 「M番目に挿入」するが、それをMという数値で識別するとは書いてない。 数学とはそういうものだ。 ポインタ p で表現する場合でも、p が M 番目のノードを指していることがある。 その場合は、M番目に挿入と表現される。 そう表現しないと、O(x)記号で表現しにくいからだ。 88 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:35:00.70 ID:FsmeH+FF.net] >>83 それと同じことをRustではポインタの代わりにCursorMutを使って実現できる、という認識ですが CursorMutには何が欠けていますか？ 89 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:35:29.31 ID:4cVpX4oe.net] 数学での言葉の表現と日常の言葉の表現は異なる。 「M番目に挿入」することと、そのノードを、index = M - 1 で表すこととは 別の話だ。 90 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:47:35.86 ID:4cVpX4oe.net] >>87 同じノードを複数のCursor/CursorMutが参照している場合、1つの参照経由 でノードを削除した場合、別の参照がダングリング参照になるのを0コストで 防ぐ方法は無いはずだ。 静的解析が不可能で、時間や記憶域に何らかのオーバヘッドが必要となるはず。 91 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 14:16:45.03 ID:4cVpX4oe.net] さらに、1つの LinkedListに対して、同時に2個以上の CursorMut を作ることは 出来ないはず。 92 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 14:18:55.00 ID:iOAXb/4V.net] Cでリンクドリストの途中を直接ポインタで持っていると速いが その途中が削除された場合にそのポインタは危険なポインタとなる つまりCで記述しても何らかのコストをかけなければ安全に出来ない つまりこの問題はどの言語であろうがコストゼロにすることは不可能 93 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 15:27:02.65 ID:I2sJLr90.net] >>91 いや、数学が得意な人は頭がいいので、それでも至って安全なプログラムが書けるし、 今ままでも書いてきた。 Rustは数学の得意な人間には遥かに及ばない。 94 名前：デフォルトの名無しさん [2021/09/10(金) 15:44:47.65 ID:EyQ85oMr.net] すげぇバカ 95 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 15:45:34.73 ID:XIGB6bHM.net] よくわからないけどこんなスレよりqiitaとかzennとかで記事書いたほうがいいと思う 96 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:06:16.82 ID:lpjuAWj9.net] >>86 屁理屈 97 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:11:54.58 ID:lpjuAWj9.net] どんな非負整数Mに対して と自分で書いている 当然与える情報はMである 各Mに対応するポインタを保持するなら 挿入時にそのテーブルを更新しなきゃならないから O(1)では出来ない 98 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:38:39.28 ID:dS7angqs.net] >>96 Mを与える情報とは書いてない。 Mというものを使わないと、LinkedListとVectorで共通した議論が出来なく なるから書いてるだけ。数学では良く使う論法。 つまり、Mは、議論の中で場所を特定するために用いているだけで、 プログラム中で用いているとは言ってない。 99 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:41:20.99 ID:dS7angqs.net] 例えば、コンテナに100個のノードが入っていたとする。 コンテナは、LinkedListやVectorなどどんなアルゴリズムを使っているかは何でも良い。 で、「5番目の場所にノードを追加する」という言葉は、LinkedListにも使えるが、 その場合、プログラム中では5という数値で識別せず使わず、ポインタで識別する のが C言語での常識。 でも、「5番目の場所に追加する」という言葉は使ってよい事になっている。 100 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:43:19.62 ID:iOAXb/4V.net] >>96 その人は数学が得意と言いながらそこすら理解できていない人だからね Cでもプログラミングしたことあるならすぐわかることだからプログラミング経験も乏しいと推測される つまりRustを叩きたいだけの人が暴れているだけの構図

---

---

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

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