Rust part15

1 名前：デフォルトの名無しさん mailto:sage [2022/05/12(木) 18:28:20.99 ID:cuIcFT6k.net] 公式 https://www.rust-lang.org/ https://blog.rust-lang.org/ https://github.com/rust-lang/rust Web上の実行環境 https://play.rust-lang.org 日本語の情報 https://rust-jp.rs/ ※Rustを学びたい人はまず最初に公式のThe Bookを読むこと https://doc.rust-lang.org/book/ ※Rustを学ぶ際に犯しがちな12の過ち https://dystroy.org/blog/how-not-to-learn-rust ※Rustのasyncについて知りたければ「async-book」は必読 https://rust-lang.github.io/async-book/ ※C++との比較は専用スレへ C++ vs Rust https://mevius.5ch.net/test/read.cgi/tech/1619219089/ ※次スレは原則>>980が立てること 前スレ Rust part14 https://mevius.5ch.net/test/read.cgi/tech/1644596656/ 46 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 18:10:04.46 ID:ThGcWJJo.net] もはやどのレスもギャグにしか見えん 俺のしってるCopyとは確実に違う 47 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 18:38:28.59 ID:qW5+0T97.net] 今までで一番意味不明なこと言ってるな Copyのコストが高いならmoveのコストはどうなるのよ 48 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 18:44:18.84 ID:Mb2xQVjt.net] >>45 所有権に複製という概念はない Copyをimplすると使われる時に値が自動的に複製される そのためCopyは最も高コスト >>46 君のレスがギャグにしか見えん 49 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 18:47:50.19 ID:/5k6Bg80.net] Rust のムーブはビットパターンのコピーだもんな。 低レイヤの視点で見たらコピーと何の差も無い。 なるべく参照を使う場合にしても間接参照の実行コストとコピーの実行コストを天秤にかけてどちらが有利かは場合による。 50 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 18:55:12.38 ID:W7mPHnnh.net] >>47 それは理解不足すぎるぜ 大文字のCopyはCopyトレイトを意味しCopyトレイトを実装するか否かの話だろ moveは別方向の話であり比較対象にすらならない 比較するならば「Copy実装(必然的にClone)も実装」「Cloneのみ実装」「どちらも実装なし」の3つだな 51 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:00:08.16 ID:GLqKLCqS.net] >>48 ギャグだと分からない人がいるとは想定していませんでした。 誤解を招いたのであれば申し訳ございません。 52 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:06:18.85 ID:78bNbDCr.net] >>49 デタラメすぎ ムーブでビットパターンのコピーは発生しない ビットパターンのコピーが発生するのは引数の値渡し等であってムーブとは関係ない さらに引数の値渡しでのでビットパターンのコピーとCopyのコピーも全く異なる Copyのコピーはディープであって高コスト 53 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:08:38.74 ID:NE3SiQoq.net] そもそもフィボナッチ数列イテレータなんて誰も求めてないので 前スレのだれかさんの実装に問題があると思うなら自分で勝手に改善してなさい そしてその結果はここに貼らなくていいぞ 54 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:11:06.58 ID:zgsMMZOB.net] 「ヒープ使うならCloneまでにしとけ」 このセリフが一番刺さった 55 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:11:50.62 ID:rHnqcaqs.net] >>52 おじさんマジかよwww 56 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:22:59.76 ID:NE3SiQoq.net] >>54 Dropを実装する型はCopyを実装できないよ BoxもRcもStringもVecもそもそもCopyを実装できないので、するかしないか考えること自体が無意味 どういう型にCopyを実装できるか、できないか、すべきかはdocsに書いてあるので なんのかんの言う前にまずはこれを読もうね https://doc.rust-lang.org/std/marker/trait.Copy.html 57 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:37:56.79 ID:tTdd7GU5.net] >>53 これだけCopyやCloneを理解していない連中が多い状況だと >>30の質問に答えられるかどうかは最低限クリアすべきテストとして有用ではないか？ フィボナッチ自体はもちろんどうでもよい話だがCopyやCloneを避けるRustの基本ができるかどうかわかる点で 58 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:45:37.77 ID:/5k6Bg80.net] >>52 じゃあムーブでなにが起こるとおもってんの？ 59 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 19:54:25.89 ID:SHnkjBGX.net] >>53 > フィボナッチ数列イテレータなんて誰も求めてない それはそうなんだけど 唯一本人にとっては伝家の宝刀だから 少なくともこのスレいっぱいまでは引っ張って 何度も何度も参照するはず 60 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 20:38:11.38 ID:NE3SiQoq.net] フィボナッチがどうでもいいならこの話は終わりです 61 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 20:45:13.08 ID:Mz4z3EAu.net] 関数の深いところから順に構造体をムーブで返していって 各関数で渡ってきた構造体のアドレスを表示させてみた #[derive(Debug)] struct S([i32; 100]); fn main() { let mut s1 = sub1(100); s1.0[1] = 111; println!("s1: {:p}", &s1); println!("{s1:?}"); } fn sub1(p: i32) -> S { let q = p + 3; let mut s2 = sub2(q); s2.0[2] = p - 300; println!("s2: {:p}", &s2); s2 } fn sub2(s: i32) -> S { let t = s * 2; let mut s3 = S([123; 100]); s3.0[3] = t; println!("s3: {:p}", &s3); s3 } s1もs2もs3もアドレスが一致 ムーブではアドレスそのままであり ビットパターンのコピーが為されないという結論 62 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 20:58:36.88 ID:qW5+0T97.net] >>50 "Copyのコストが高い" は Copy を実装する行為そのもののコストが高いと解釈すべきということ？ そんなばかな >>52 ドキュメント読みましょうねー https://doc.rust-lang.org/stable/std/marker/trait.Copy.html > It’s important to note that in these two examples, the only difference is whether you are allowed to access x after the assignment. > Under the hood, both a copy and a move can result in bits being copied in memory, although this is sometimes optimized away. ... > The behavior of Copy is not overloadable; it is always a simple bit-wise copy. ... > The implementation of Clone can provide any type-specific behavior necessary to duplicate values safely. > For example, the implementation of Clone for String needs to copy the pointed-to string buffer in the heap. 63 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:06:43.52 ID:qW5+0T97.net] >>61 アドレスが同じか否かでコピーの有無を判断する意味はよくわからんが その理屈だとこのコードだと違うアドレスが表示されるからビットパターンのコピーがされてるって結論になるのか？ #[derive(Debug)] struct S([i32; 100]); fn main() { let mut s1 = S([0; 100]); println!("s1: {:p}", &s1); let s2 = s1; println!("s2: {:p}", &s2); } 64 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:07:20.55 ID:f/Xu02FO.net] >>61 struct S {} fn main() { let s1 = S{}; println!("s1: {:p}", &s1); let s2 = s1; println!("s2: {:p}", &s2); } 65 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:08:00.98 ID:f/Xu02FO.net] ごめん被った。やっぱそう思うよね。 66 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:16:19.81 ID:9Ab93Lwf.net] >>56 ちょっとw なんで刺さったのか少しは考えてよww ギャグゴロシめ 67 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:19:28.47 ID:51EzJkQ/.net] >>61 >>63 その二つの相異なる結果を見るとビットパターンのコピーはムーブ以外の要因で起きている？？ 68 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:30:56.46 ID:W905eBh/.net] >>57 一番分かってないお前が言うなよw 69 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:38:19.38 ID:/vD2A9J9.net] >>61 高コストなCopyも実装してから確認してみてねww 70 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:38:29.32 ID:NE3SiQoq.net] >>66 ごめんよ 刺さったって「ためになった」みたいな意味で言ってるのかと思ったよ てっきりオジの自演かと 71 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:39:12.01 ID:DoCeaK1g.net] >>67 デバッグビルドだけじゃなくリリースビルドでも確認してねw 72 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:42:44.19 ID:51EzJkQ/.net] >>71 リリースモードでもどちらも同じ結果 73 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 21:49:25.30 ID:sElCPUyn.net] >>72 ごめんよー >>64と間違えた 74 名前：デフォルトの名無しさん mailto:sage [2022/05/16(月) 23:46:37.66 ID:jfEIc0ZW.net] このスレはいつもおかしい人間たちが集まってるな Rustの何が人を狂わせるんだ？ 75 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 00:09:43.95 ID:HbNyXd2X.net] おじさんイジリ飽きたので結論いっておく Copyもmoveもスタックの中身をコピーしてるのは同じ 最適化によって不要なコピーが除去されるかどうかはLLVM次第 でかい配列やでかい構造体などの極一部を除けばCopyは参照の受け渡しよりも低コスト ついでに言うと&TもCopy 76 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 00:26:01.61 ID:+9bLcV37.net] >>75 頭悪すぎ Copyが低コストなのではなく 低コストなものだけにCopyが実装されている なぜならCopyは高コストであるため 77 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 02:09:56.03 ID:2XRLgT14.net] >>76 ここでいうCopyのコストって具体的にどういう操作のコストのこと言ってる？ 構造体データのbitwise-copyのこと？それとも別の何か？ Cloneやmoveの場合にそのコストは発生しないと主張しているの？ 78 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 02:13:55.30 ID:tAEVG8cC.net] >>62 ほーCopyってCloneの実装によらずmemcpy相当の結果になるのか 自動的に.clone()が差し挟まれる感じかと思ってた 79 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 07:41:41.18 ID:1GDSnWAB.net] >>78 俺も同じくCopyは自動的にclone()されると思ってた そう思ってた理由はClone実装せずにCopy実装するとエラーとなるため そこで実験 #[derive(Debug,Copy)] struct S { not_cloned: usize, cloned: usize } impl Clone for S { fn clone(&self) -> Self { S { not_cloned: self.not_cloned / 3, cloned: self.cloned } } } fn main() { let s0 = S { not_cloned: 123, cloned: 456 }; let s1 = s0.clone(); let s2 = s0; // copy println!("Cloned: {s1:?}"); println!("Copied: {s2:?}"); } 結果 Cloned: S { not_cloned: 41, cloned: 456 } Copied: S { not_cloned: 123, cloned: 456 } 別物になった… 80 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 10:53:02 ID:GxF458pr.net] >>52 >>>49 >デタラメすぎ >ムーブでビットパターンのコピーは発生しない >ビットパターンのコピーが発生するのは引数の値渡し等であってムーブとは関係ない >さらに引数の値渡しでのでビットパターンのコピーとCopyのコピーも全く異なる >Copyのコピーはディープであって高コスト このレス最強だな 一つ一つの文すべてが間違ってる 「デタラメすぎ」てw 81 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 14:50:42.61 ID:94ESmIzZ.net] ガイジムーブ来てんね 82 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 21:03:27.69 ID:VS5jQHYL.net] Copyはshallow copyだわな 83 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 22:07:44 ID:LjbtS7tD.net] 色々と正確な情報が出揃ったところで質問 まず前提として話を明白かつ簡単にするため、 ここでは!DropつまりCopy実装可能な型のみ対象、 そしてもしClone実装するならば*selfつまりCopy実装と同一、 CloneやCopyを実装するかどうかは任意、 小文字のcloneとcopyはそれぞれCloneやCopyを実装した時にそれらが使われることを意味するとする このとき、次のどちらの主張が正しい？ Ａ「copy/cloneはコストが生じるので、回避できるならば回避したほうが有利」 Ｂ「copy/cloneのコストはmoveと同じなので回避する必要はない」 84 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 22:30:37.28 ID:VUKzLr9a.net] 場合による。 たとえコピーであっても結局は内容が同じものであると看破すれば 実際にはコピーしないようなコードを生成するといったことは有りうる。 Rust は原理的にエイリアス解析がやりやすい言語だと思うし。 実行コスト的にどうかなんて考えずに所有権管理の側面からの妥当性で決めたほうがよい。 その上でどうしても実行コストを切り詰めないといけないようになったならその時に考えればいい。 85 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 22:33:27.98 ID:5/60CrrJ.net] >>83 前提もまちがってるが 比較する対象がそもそも意味がない もうちょっと勉強してから出直して 86 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 23:40:20.70 ID:XaJZCLYj.net] >>83 >Ａ「copy/cloneはコストが生じるので、回避できるならば回避したほうが有利」 何と比べてコストが生じると言ってるの？ 回避した場合は何で代用するつもりなの？ 87 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 23:43:19.03 ID:nlEgMvZ6.net] 考えてみたけどmove/copyが問題になるレベルの大きさの型をスタックに置いて扱ったことが無いな… 使うとすれば固定長配列のバッファ？ でもそんなものmove/copyするわけないし やっぱり考える意味の無い二択だと思う 88 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 23:47:41.13 ID:FqAlYuq2.net] >>86 回避する前と回避した後の比較だろう 回避したコードが書けたならばcopyの代用の必要はない 89 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 23:49:36.53 ID:YviCLBk+.net] >>83 一般的にはAが正しい ただし>>84が言うように無駄なコピーが消える場合もある Ａ「copy/cloneはコストが生じるので、回避できるならば回避したほうが有利になることがある」ならば正確 90 名前： Bについては前半はある意味正しいとしても後半が間違い >>85 批判や主張はその理由を伴わないと議論とならず意味がない [] [ここ壊れてます] 91 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 23:54:01.76 ID:VUKzLr9a.net] >>89 > 批判や主張はその理由を伴わないと議論とならず意味がない 基本的にはそうだが、こっちが説明しても理解できるレベルに達してない場合にはどうせ議論にならんのでな。 92 名前：デフォルトの名無しさん mailto:sage [2022/05/17(火) 23:55:13.39 ID:tAEVG8cC.net] あっこの流れC++相談室で見たやつだ 93 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 00:07:06.58 ID:P5Km+xQv.net] 要は参照使えるなら使っとけって？ 今更すぎませんか 94 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 00:30:37.66 ID:DGffctwq.net] オナコードペタペタされてたほうがマシだったなこりゃ 95 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 00:45:17.78 ID:opn2S8Zb.net] >>92 それもあるが、例えば多数のコピーが行われているコードに対して、回避できる分を見直し、少数のコピーで済むように改善できる場合もある Copy実装せずに明示clone()した方が見つけやすいかもしれない 96 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 01:26:17.77 ID:lxQ5l4ey.net] >>88 さすがに意味が分からないよ 値の受け渡しにcopyを使わないなら何が他の方法を使う必要があるでしょ 97 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 01:42:43.25 ID:d5NnfCmB.net] 一人だけ間違った思い込みをしてるのに 説明されても「俺は間違ってない、間違ってるのはお前ら」が続くだけだからな 98 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 01:46:16.75 ID:6ezlEFaX.net] >>95 頭が硬すぎないか？ 回避できる分を回避するだけだろ 回避できない分まで回避する、と思い込んてるのはYouのみ 99 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 01:51:55.82 ID:Da/MVUm8.net] >>89 「○○はコストが生じるので、回避できるならば回避したほうが有利になることがある」 言葉の定義を明確にしないジェネリック文は 恣意的に常に真にも常に偽にもできる 100 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 02:06:14.30 ID:UgigdTUo.net] >>90 無駄にプライド高いな 嫌われるぜ 101 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 07:08:20 ID:bcZKOTNR.net] 大きいフィールドを持つ型には、Copyは実装しないだろうし普通はCopy/Moveのコスト差を気にすることなくない？ どちらにすべきかボーダーが難しいことはありそうだけど 102 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 07:14:11 ID:P5Km+xQv.net] >>94 データフローを見直して単純に消せるclone/copyは消せってことか？ それこそ今更すぎるわ 単純に消せないところまで消した後、さらにパフォーマンス改善するにはどうするかってことで、参照の話か？って聞いたんだけど どこの誰とも知れないやつのフィボナッチのコードに対する指摘をされても知らねーよ 問題があって対策が分かってるなら自分で直すがいい 103 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 07:41:25.51 ID:4GWzufxp.net] >>97 実行回数の話だったのかよww まさかねw 104 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 07:56:39.00 ID:HgdHe2aE.net] >>101 フィボナッチの件はBigIntなど非Copyも対象で今回の話は全く無関係だろ そこを区別できていないのは相当ヤバいぞ 105 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 08:12:27.72 ID:BE/QrV8J.net] 流れからすると本当はジェネリックのフィボナッチにCopyを付けないほうが有利と主張したかったんじゃね？ でも後から回避できないことに気づいて苦しい言い訳を重ねてるだけと見た 106 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 08:21:27.45 ID:6swlbHlO.net] >>85 根拠も示さず批判だけする一番アカン人間やな 107 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 08:33:04.08 ID:6hDwlDoy.net] >>104 フィボナッチはCopyを回避できないものなの？ 108 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 08:45:43.18 ID:2HNq06l+.net] 分からないなら分からないから教えてって言えばいいのに意地を張るからこうなる 構えば構うほど意味不明な発言が出てくる 真面目に議論したいならせめてIDコロコロ変えるのやめな 109 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 09:10:15.39 ID:Gy2qdhBc.net] フィボナッチってこれだろ f(0) = 0 f(1) = 1 f(n) = f(n - 1) + f(n - 2) 関数呼び出しに足し算に大量のコピーは避けられない 110 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 09:28:25.87 ID:3vPi03ro.net] >>87 async関数やasyncブロックで生成されるFutureは結構大きくなることがあって、boxingした方が性能出るケースもある 111 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:05:07.09 ID:jV65BxdQ.net] >>106 型制約からCopyを外すこことcopyを回避することは全く意味が違う >>83の質問は明らかに後者 プリミティブも対象になるフィボナッチでcopyを回避するのは無理 112 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:20:40.09 ID:AWXqkW+Q.net] >>110 型制約からCopyを外せばプリミティブと言えどもcopyされなくなる 具体的には個々のプリミティブ型へモノモーフィゼーゼーションされる前の段階でCopy実装していない型に対してのcopy発生エラーが生じる フィボナッチでcopyを回避するのは可能 113 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:38:43.35 ID:2JRtSvHV.net] 複オジの主張まとめ(1) 37, 39, 44 ===== CopyやCloneを使っているから別問題だろう。 一般的にRustのプログラミングでは、 Copy(暗黙的な自動コピー)やClone(clone()による明示的な手動コピー)を使うと楽になるが、コストは高くなる。 そのため不要なclone()を見極めてそれを回避するプログラミングが出来るかどうか、というRustにおける根源的な話だろう。 もちろんCopyは最もコストが高い。 個々のコスト自体は通常clone()と同じだが、常に自動的にclone()が起きるため最もコストが高くなる。 Copyはコストが一番高いから出来る限り避けるべきだな 特にヒープを使うならCloneまでにしておくべき 可能ならばCloneも避けるべきだが 114 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:39:05.95 ID:2JRtSvHV.net] 複オジの主張まとめ(2) 50, 52, 57 ===== それは理解不足すぎるぜ 大文字のCopyはCopyトレイトを意味しCopyトレイトを実装するか否かの話だろ moveは別方向の話であり比較対象にすらならない 比較するならば「Copy実装(必然的にClone)も実装」「Cloneのみ実装」「どちらも実装なし」の3つだな デタラメすぎ ムーブでビットパターンのコピーは発生しない ビットパターンのコピーが発生するのは引数の値渡し等であってムーブとは関係ない さらに引数の値渡しでのでビットパターンのコピーとCopyのコピーも全く異なる Copyのコピーはディープであって高コスト これだけCopyやCloneを理解していない連中が多い状況だと >>30の質問に答えられるかどうかは最低限クリアすべきテストとして有用ではないか？ フィボナッチ自体はもちろんどうでもよい話だがCopyやCloneを避けるRustの基本ができるかどうかわかる点で 115 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:41:41.09 ID:2JRtSvHV.net] 複オジの一連の主張を読んでから>>83の複オジ質問を読むべし 116 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:44:21.46 ID:Jso4/z1R.net] 複おじに反応するやつも複おじ 117 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 10:52:26.71 ID:j9G6SOiS.net] 主張が毎回変わる 口調も毎回変わる 表記も毎回変わる 間違いなく多重人格者 118 名前：デフォルトの名無しさん [2022/05/18(水) 10:55:48.57 ID:TXrPyH7a.net] >>98 この文脈では○○にはなんでも当てはまるから意味がないよね 以下なら議論になる？ Ａ「copy/cloneはmoveよりコストが生じるので、copyが必要な部分とそうでない部分で構造体を分離してでも出来るだけmoveを使用する」 Ｂ「copy/cloneのコストはmoveよりコストが生じるとは限らないので、一部でもcopyが必要な部分がある構造体は丸ごとcopyして構わない」 119 名前：デフォルトの名無しさん [2022/05/18(水) 11:00:11.80 ID:TXrPyH7a.net] >>116 そこまでいったらネット上では別人で良いだろ 120 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 11:05:55.27 ID:f/6XNiB/.net] >>108 やってみた fn main() { for n in 0..100 { let f = f(n); println!("f({n}) = {f}"); } } fn f(n: i32) -> i32 { match n { 0 => 0, 1 => 1, n => f(n - 1) + f(n - 2), } } このあたりから非常に重くなった f(43) = 433494437 f(44) = 701408733 f(45) = 1134903170 f(46) = 1836311903 f(47) = -1323752223 f(48) = 512559680 121 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 11:24:29.81 ID:Rx65yaNy.net] メモ化されてないんやから遅くなるのは当然 >>108は定義を示しただけちゃう？ 122 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 11:25:30.07 ID:Rx65yaNy.net] つかオーバーフローしとるな 123 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 11:29:30.10 ID:e0i+LLok.net] >>119 そのコードだとcopyは何回くらい発生してるのだろう 0回？1回？2回？3回？たくさん？ 124 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 12:13:31 ID:QV9C5cPM.net] ぼくのかんがえたさいきょうのcountup<T>()をみんなバカにしたので ぼくのかんがえたさいきょうのfibonacchi<T>()でやっつけようとしたら わざをだすまえにボコボコにやられてしまいました く、くやしいです！ 125 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 13:41:52 ID:mX15beFi.net] clone()が一個でコンパイル通ったからそのコードでのコピーは一回ではないか use std::ops::{Add, Sub}; fn f<T>(n: T) -> T where T: Clone + PartialEq + TryFrom<usize> + Add<Output=T> + Sub<Output=T> { let [zero, one, two] = [0, 1, 2].map(|n| T::try_from(n).ok().unwrap()); match n { n if n == zero => zero, n if n == one => one, n => f(n.clone() - one) + f(n - two), } } 126 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 13:50:00 ID:FQ8O/3lA.net] >>119 計算量はO(n), メモリ使用量は定数オーダーにできるのになんで定義どおり実装したの？ 127 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 14:41:04.77 ID:xTux5YG/.net] >>123 ぼくのかんがえたさいきょうのfizzbuzz<T>()もわすれないで 128 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 15:04:45.49 ID:dI/aN4vs.net] >>125 そんな魔法はありません 129 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 16:48:40.40 ID:pQAvghMm.net] >>127 え？ 130 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 17:53:48.13 ID:jsK0MVuh.net] Rust以前の問題じゃん スレ違い 131 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 23:22:25.69 ID:z2ufbs5N.net] >>124 そのclone()は子のf(n-1)とf(n-2)やそれらの子孫でも呼ばれるので1回ではなくO(n)より大きい それをO(n)すなわちn回＋定数回以下に抑えられるのかどうか あるいはO(0)回すなわち定数回以下に抑えられるのかどうか 132 名前：デフォルトの名無しさん mailto:sage [2022/05/18(水) 23:41:48.24 ID:RLh6XGtQ.net] フィボナッチはu128を使ってもf(187)でオーバフローするからBigInt必須 clone()はできる限り少なくしないと厳しい 133 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 00:10:47.96 ID:SnnzWk5R.net] どうでもいいから複おじはTRPL読み直してきてね 134 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 00:16:28.52 ID:IEr5OW/T.net] >>120 メモ化したら速くなったけど memoをこちらで用意して毎回渡していくのを避けられないのかな？ fn main() { let mut memo: Vec<usize> = Vec::new(); for n in 0..100 { let f = f(n, &mut memo); println!("f({n}) = {f}"); } } fn f(n: usize, memo: &mut Vec<usize>) -> usize { if let Some(result) = memo.get(n) { *result } else { let result = match n { 0 => 0, 1 => 1, n => f(n - 1, memo) + f(n - 2, memo), }; memo.push(result); result } } 135 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 00:24:17.53 ID:d4KplWCH.net] メモ化する必要ある？ 直前の2つだけ記録しておけば次の一項が計算できるんだから再帰にする必要ないよね 136 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 00:33:12.40 ID:IEr5OW/T.net] >>134 具体的にどうすればよいてすか？ 137 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 00:46:08.98 ID:HY3grr6d.net] >>135 "rust fibonacci"でググるとよいです 138 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 01:21:23 ID:f3pwm4rC.net] >>134 直前の2つだけ記録して再帰にしない方法ならば おそらくこうする案だと思うが >>133がO(n)で済んでいるのに 139 名前：対して これは二重のforによりO(n^2)になっていてこれは悪手 fn main() { for n in 0..100 { let f = f(n); println!("f({n}) = {f}"); } } fn f(n: usize) -> usize { match n { 0 => 0, 1 => 1, n => { let mut prepre = 0; let mut pre = 1; for i in 2..n { let tmp = pre; pre += prepre; prepre = tmp; } pre + prepre }, } } [] [ここ壊れてます] 140 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 01:31:14.77 ID:d4KplWCH.net] >>135 fn main(){ for n in 0..10{ println!("f({}) = {}", n, f(n)); } } fn f(n:usize) -> usize{ let mut a = 0; let mut b = 1; for i in 0..n{ let tmp = b; b = a + b; a = tmp; } return a; } わざわざRustっぽい書き方をする必要はない 141 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 01:39:04.90 ID:f3pwm4rC.net] >>138 それもforが二重となっていて全体でO(n^2)だから同じく悪手 142 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 02:09:27.74 ID:XQuKTBpO.net] >>131 なら尚のことジェネリックにする意味ないよね？ 143 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 03:45:23.95 ID:jyObMdH0.net] >>137,139 悪手ってなにをもって悪手だよ 一般項の導出は高校生でもできるレベルで、そうすればO(log(n))で求められるし、つまらん計算量改善のためだけのアルゴリズム議論はもうやめろ これ以上計算量の話をするなら別のスレでやってくれ 144 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 04:01:44.79 ID:f3pwm4rC.net] >>141 mainに既にforループがある だから個々をO(n)で求めると全体でO(n^2)となる もし個々をO(log(n))で求めたとしても全体でO(n✕log(n))となる 一方で>>133は優れていて全体でO(n)だから圧倒的に良手 145 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 08:08:36.85 ID:SnnzWk5R.net] まあ(usize) -> usizeのインターフェースを持たせつつ逐次処理したければメモ化が楽だわな Rustとは特に関係の無いアルゴリズム一般論の話だけど 146 名前：デフォルトの名無しさん mailto:sage [2022/05/19(木) 12:20:27.39 ID:TVQgVkXp.net] なんでmainのループまで計算量に入れてるの？ 今やってるのはフィボナッチ数列の計算量の話でしょ 余計なところまで話し広げてどうするの？

---

---

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

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