Rust part15

**デフォルトの名無しさん** · 2022/05/12(木) 18:28:20.99

公式
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/

**デフォルトの名無しさん** · 2022/05/16(月) 08:58:48.98

複製おじさんはいつも自分勝手な妄想を「一般的には～」とか「皆は～」と言って自分を正当化しようとするよね

**デフォルトの名無しさん** · 2022/05/16(月) 10:03:10.22

>>40
間違いは誰にでもあるからまだいいんだが
指摘されても反省するどころかさらなる妄想を撒き散らすのがほんと迷惑

**デフォルトの名無しさん** · 2022/05/16(月) 11:11:33.48

おじさん使いの人の自演がいつもよくわからん
唐突に妄想(?)を攻撃し出すが幻覚か何か見えてるのか

**デフォルトの名無しさん** · 2022/05/16(月) 16:19:03.24

>>39
Cloneのコストが高い型にCopyを実装するな

**デフォルトの名無しさん** · 2022/05/16(月) 16:30:48.20

Copyはコストが一番高いから出来る限り避けるべきだな
特にヒープを使うならCloneまでにしておくべき
可能ならばCloneも避けるべきだが

**デフォルトの名無しさん** · 2022/05/16(月) 18:08:42.72

Copyは所有権を複製するから最も高コスト(ｷﾘｯ！！

**デフォルトの名無しさん** · 2022/05/16(月) 18:10:04.46

もはやどのレスもギャグにしか見えん
俺のしってるCopyとは確実に違う

**デフォルトの名無しさん** · 2022/05/16(月) 18:38:28.59

今までで一番意味不明なこと言ってるな
Copyのコストが高いならmoveのコストはどうなるのよ

**デフォルトの名無しさん** · 2022/05/16(月) 18:44:18.84

>>45
所有権に複製という概念はない
Copyをimplすると使われる時に値が自動的に複製される
そのためCopyは最も高コスト

>>46
君のレスがギャグにしか見えん

**デフォルトの名無しさん** · 2022/05/16(月) 18:47:50.19

Rust のムーブはビットパターンのコピーだもんな。
低レイヤの視点で見たらコピーと何の差も無い。

なるべく参照を使う場合にしても間接参照の実行コストとコピーの実行コストを天秤にかけてどちらが有利かは場合による。

**デフォルトの名無しさん** · 2022/05/16(月) 18:55:12.38

>>47
それは理解不足すぎるぜ
大文字のCopyはCopyトレイトを意味しCopyトレイトを実装するか否かの話だろ
moveは別方向の話であり比較対象にすらならない
比較するならば「Copy実装(必然的にClone)も実装」「Cloneのみ実装」「どちらも実装なし」の3つだな

**デフォルトの名無しさん** · 2022/05/16(月) 19:00:08.16

>>48
ギャグだと分からない人がいるとは想定していませんでした。
誤解を招いたのであれば申し訳ございません。

**デフォルトの名無しさん** · 2022/05/16(月) 19:06:18.85

>>49
デタラメすぎ
ムーブでビットパターンのコピーは発生しない
ビットパターンのコピーが発生するのは引数の値渡し等であってムーブとは関係ない
さらに引数の値渡しでのでビットパターンのコピーとCopyのコピーも全く異なる
Copyのコピーはディープであって高コスト

**デフォルトの名無しさん** · 2022/05/16(月) 19:08:38.74

そもそもフィボナッチ数列イテレータなんて誰も求めてないので
前スレのだれかさんの実装に問題があると思うなら自分で勝手に改善してなさい
そしてその結果はここに貼らなくていいぞ

**デフォルトの名無しさん** · 2022/05/16(月) 19:11:06.58

「ヒープ使うならCloneまでにしとけ」
このセリフが一番刺さった

**デフォルトの名無しさん** · 2022/05/16(月) 19:11:50.62

>>52
おじさんマジかよwww

**デフォルトの名無しさん** · 2022/05/16(月) 19:22:59.76

>>54
Dropを実装する型はCopyを実装できないよ
BoxもRcもStringもVecもそもそもCopyを実装できないので、するかしないか考えること自体が無意味

どういう型にCopyを実装できるか、できないか、すべきかはdocsに書いてあるので
なんのかんの言う前にまずはこれを読もうね
https://doc.rust-lang.org/std/marker/trait.Copy.html

**デフォルトの名無しさん** · 2022/05/16(月) 19:37:56.79

>>53
これだけCopyやCloneを理解していない連中が多い状況だと
>>30の質問に答えられるかどうかは最低限クリアすべきテストとして有用ではないか？
フィボナッチ自体はもちろんどうでもよい話だがCopyやCloneを避けるRustの基本ができるかどうかわかる点で

**デフォルトの名無しさん** · 2022/05/16(月) 19:45:37.77

>>52
じゃあムーブでなにが起こるとおもってんの？

**デフォルトの名無しさん** · 2022/05/16(月) 19:54:25.89

>>53
> フィボナッチ数列イテレータなんて誰も求めてない

それはそうなんだけど
唯一本人にとっては伝家の宝刀だから
少なくともこのスレいっぱいまでは引っ張って
何度も何度も参照するはず

**デフォルトの名無しさん** · 2022/05/16(月) 20:38:11.38

フィボナッチがどうでもいいならこの話は終わりです

**デフォルトの名無しさん** · 2022/05/16(月) 20:45:13.08

関数の深いところから順に構造体をムーブで返していって
各関数で渡ってきた構造体のアドレスを表示させてみた

#[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もアドレスが一致
ムーブではアドレスそのままであり
ビットパターンのコピーが為されないという結論

**デフォルトの名無しさん** · 2022/05/16(月) 20:58:36.88

>>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.

**デフォルトの名無しさん** · 2022/05/16(月) 21:06:43.52

>>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);
}

**デフォルトの名無しさん** · 2022/05/16(月) 21:07:20.55

>>61
struct S {}
fn main() {
let s1 = S{};
println!("s1: {:p}", &s1);
let s2 = s1;
println!("s2: {:p}", &s2);
}

**デフォルトの名無しさん** · 2022/05/16(月) 21:08:00.98

ごめん被った。やっぱそう思うよね。

**デフォルトの名無しさん** · 2022/05/16(月) 21:16:19.81

>>56
ちょっとw
なんで刺さったのか少しは考えてよww
ギャグゴロシめ

**デフォルトの名無しさん** · 2022/05/16(月) 21:19:28.47

>>61
>>63
その二つの相異なる結果を見るとビットパターンのコピーはムーブ以外の要因で起きている？？

**デフォルトの名無しさん** · 2022/05/16(月) 21:30:56.46

>>57
一番分かってないお前が言うなよw

**デフォルトの名無しさん** · 2022/05/16(月) 21:38:19.38

>>61
高コストなCopyも実装してから確認してみてねww

**デフォルトの名無しさん** · 2022/05/16(月) 21:38:29.32

>>66
ごめんよ
刺さったって「ためになった」みたいな意味で言ってるのかと思ったよ
てっきりオジの自演かと

**デフォルトの名無しさん** · 2022/05/16(月) 21:39:12.01

>>67
デバッグビルドだけじゃなくリリースビルドでも確認してねw

**デフォルトの名無しさん** · 2022/05/16(月) 21:42:44.19

>>71
リリースモードでもどちらも同じ結果

**デフォルトの名無しさん** · 2022/05/16(月) 21:49:25.30

>>72
ごめんよー
>>64と間違えた

**デフォルトの名無しさん** · 2022/05/16(月) 23:46:37.66

このスレはいつもおかしい人間たちが集まってるな
Rustの何が人を狂わせるんだ？

**デフォルトの名無しさん** · 2022/05/17(火) 00:09:43.95

おじさんイジリ飽きたので結論いっておく

Copyもmoveもスタックの中身をコピーしてるのは同じ
最適化によって不要なコピーが除去されるかどうかはLLVM次第
でかい配列やでかい構造体などの極一部を除けばCopyは参照の受け渡しよりも低コスト
ついでに言うと&TもCopy

**デフォルトの名無しさん** · 2022/05/17(火) 00:26:01.61

>>75
頭悪すぎ
Copyが低コストなのではなく
低コストなものだけにCopyが実装されている
なぜならCopyは高コストであるため

**デフォルトの名無しさん** · 2022/05/17(火) 02:09:56.03

>>76
ここでいうCopyのコストって具体的にどういう操作のコストのこと言ってる？
構造体データのbitwise-copyのこと？それとも別の何か？
Cloneやmoveの場合にそのコストは発生しないと主張しているの？

**デフォルトの名無しさん** · 2022/05/17(火) 02:13:55.30

>>62
ほーCopyってCloneの実装によらずmemcpy相当の結果になるのか
自動的に.clone()が差し挟まれる感じかと思ってた

**デフォルトの名無しさん** · 2022/05/17(火) 07:41:41.18

>>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 }
別物になった…

**デフォルトの名無しさん** · 2022/05/17(火) 10:53:02.16

>>52
>>>49
>デタラメすぎ
>ムーブでビットパターンのコピーは発生しない
>ビットパターンのコピーが発生するのは引数の値渡し等であってムーブとは関係ない
>さらに引数の値渡しでのでビットパターンのコピーとCopyのコピーも全く異なる
>Copyのコピーはディープであって高コスト

このレス最強だな
一つ一つの文すべてが間違ってる
「デタラメすぎ」てw

**デフォルトの名無しさん** · 2022/05/17(火) 14:50:42.61

ガイジムーブ来てんね

**デフォルトの名無しさん** · 2022/05/17(火) 21:03:27.69

Copyはshallow copyだわな

**デフォルトの名無しさん** · 2022/05/17(火) 22:07:44.57

色々と正確な情報が出揃ったところで質問

まず前提として話を明白かつ簡単にするため、
ここでは!DropつまりCopy実装可能な型のみ対象、
そしてもしClone実装するならば*selfつまりCopy実装と同一、
CloneやCopyを実装するかどうかは任意、
小文字のcloneとcopyはそれぞれCloneやCopyを実装した時にそれらが使われることを意味するとする

このとき、次のどちらの主張が正しい？
Ａ「copy/cloneはコストが生じるので、回避できるならば回避したほうが有利」
Ｂ「copy/cloneのコストはmoveと同じなので回避する必要はない」

**デフォルトの名無しさん** · 2022/05/17(火) 22:30:37.28

場合による。
たとえコピーであっても結局は内容が同じものであると看破すれば
実際にはコピーしないようなコードを生成するといったことは有りうる。
Rust は原理的にエイリアス解析がやりやすい言語だと思うし。
実行コスト的にどうかなんて考えずに所有権管理の側面からの妥当性で決めたほうがよい。
その上でどうしても実行コストを切り詰めないといけないようになったならその時に考えればいい。

**デフォルトの名無しさん** · 2022/05/17(火) 22:33:27.98

>>83
前提もまちがってるが
比較する対象がそもそも意味がない

もうちょっと勉強してから出直して

**デフォルトの名無しさん** · 2022/05/17(火) 23:40:20.70

>>83
>Ａ「copy/cloneはコストが生じるので、回避できるならば回避したほうが有利」
何と比べてコストが生じると言ってるの？
回避した場合は何で代用するつもりなの？

**デフォルトの名無しさん** · 2022/05/17(火) 23:43:19.03

考えてみたけどmove/copyが問題になるレベルの大きさの型をスタックに置いて扱ったことが無いな…

使うとすれば固定長配列のバッファ？
でもそんなものmove/copyするわけないし
やっぱり考える意味の無い二択だと思う

**デフォルトの名無しさん** · 2022/05/17(火) 23:47:41.13

>>86
回避する前と回避した後の比較だろう
回避したコードが書けたならばcopyの代用の必要はない

**デフォルトの名無しさん** · 2022/05/17(火) 23:49:36.53

>>83
一般的にはAが正しい
ただし>>84が言うように無駄なコピーが消える場合もある
Ａ「copy/cloneはコストが生じるので、回避できるならば回避したほうが有利になることがある」ならば正確
Bについては前半はある意味正しいとしても後半が間違い

>>85
批判や主張はその理由を伴わないと議論とならず意味がない

**デフォルトの名無しさん** · 2022/05/17(火) 23:54:01.76

>>89
> 批判や主張はその理由を伴わないと議論とならず意味がない

基本的にはそうだが、こっちが説明しても理解できるレベルに達してない場合にはどうせ議論にならんのでな。

**デフォルトの名無しさん** · 2022/05/17(火) 23:55:13.39

あっこの流れC++相談室で見たやつだ

**デフォルトの名無しさん** · 2022/05/18(水) 00:07:06.58

要は参照使えるなら使っとけって？
今更すぎませんか

**デフォルトの名無しさん** · 2022/05/18(水) 00:30:37.66

オナコードペタペタされてたほうがマシだったなこりゃ

**デフォルトの名無しさん** · 2022/05/18(水) 00:45:17.78

>>92
それもあるが、例えば多数のコピーが行われているコードに対して、回避できる分を見直し、少数のコピーで済むように改善できる場合もある
Copy実装せずに明示clone()した方が見つけやすいかもしれない

**デフォルトの名無しさん** · 2022/05/18(水) 01:26:17.77

>>88
さすがに意味が分からないよ
値の受け渡しにcopyを使わないなら何が他の方法を使う必要があるでしょ

**デフォルトの名無しさん** · 2022/05/18(水) 01:42:43.25

一人だけ間違った思い込みをしてるのに
説明されても「俺は間違ってない、間違ってるのはお前ら」が続くだけだからな

**デフォルトの名無しさん** · 2022/05/18(水) 01:46:16.75

>>95
頭が硬すぎないか？
回避できる分を回避するだけだろ
回避できない分まで回避する、と思い込んてるのはYouのみ

**デフォルトの名無しさん** · 2022/05/18(水) 01:51:55.82

>>89
「○○はコストが生じるので、回避できるならば回避したほうが有利になることがある」

言葉の定義を明確にしないジェネリック文は
恣意的に常に真にも常に偽にもできる

**デフォルトの名無しさん** · 2022/05/18(水) 02:06:14.30

>>90
無駄にプライド高いな
嫌われるぜ

**デフォルトの名無しさん** · 2022/05/18(水) 07:08:20.63

大きいフィールドを持つ型には、Copyは実装しないだろうし普通はCopy/Moveのコスト差を気にすることなくない？
どちらにすべきかボーダーが難しいことはありそうだけど

**デフォルトの名無しさん** · 2022/05/18(水) 07:14:11.27

>>94
データフローを見直して単純に消せるclone/copyは消せってことか？
それこそ今更すぎるわ
単純に消せないところまで消した後、さらにパフォーマンス改善するにはどうするかってことで、参照の話か？って聞いたんだけど

どこの誰とも知れないやつのフィボナッチのコードに対する指摘をされても知らねーよ
問題があって対策が分かってるなら自分で直すがいい

**デフォルトの名無しさん** · 2022/05/18(水) 07:41:25.51

>>97
実行回数の話だったのかよww
まさかねw

**デフォルトの名無しさん** · 2022/05/18(水) 07:56:39.00

>>101
フィボナッチの件はBigIntなど非Copyも対象で今回の話は全く無関係だろ
そこを区別できていないのは相当ヤバいぞ

**デフォルトの名無しさん** · 2022/05/18(水) 08:12:27.72

流れからすると本当はジェネリックのフィボナッチにCopyを付けないほうが有利と主張したかったんじゃね？

でも後から回避できないことに気づいて苦しい言い訳を重ねてるだけと見た

**デフォルトの名無しさん** · 2022/05/18(水) 08:21:27.45

>>85
根拠も示さず批判だけする一番アカン人間やな

**デフォルトの名無しさん** · 2022/05/18(水) 08:33:04.08

>>104
フィボナッチはCopyを回避できないものなの？

**デフォルトの名無しさん** · 2022/05/18(水) 08:45:43.18

分からないなら分からないから教えてって言えばいいのに意地を張るからこうなる
構えば構うほど意味不明な発言が出てくる

真面目に議論したいならせめてIDコロコロ変えるのやめな

**デフォルトの名無しさん** · 2022/05/18(水) 09:10:15.39

フィボナッチってこれだろ
f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2)
関数呼び出しに足し算に大量のコピーは避けられない

**デフォルトの名無しさん** · 2022/05/18(水) 09:28:25.87

>>87
async関数やasyncブロックで生成されるFutureは結構大きくなることがあって、boxingした方が性能出るケースもある

**デフォルトの名無しさん** · 2022/05/18(水) 10:05:07.09

>>106
型制約からCopyを外すこことcopyを回避することは全く意味が違う
>>83の質問は明らかに後者

プリミティブも対象になるフィボナッチでcopyを回避するのは無理

**デフォルトの名無しさん** · 2022/05/18(水) 10:20:40.09

>>110
型制約からCopyを外せばプリミティブと言えどもcopyされなくなる
具体的には個々のプリミティブ型へモノモーフィゼーゼーションされる前の段階でCopy実装していない型に対してのcopy発生エラーが生じる
フィボナッチでcopyを回避するのは可能

**デフォルトの名無しさん** · 2022/05/18(水) 10:38:43.35

複オジの主張まとめ(1)
37, 39, 44
=====
CopyやCloneを使っているから別問題だろう。
一般的にRustのプログラミングでは、
Copy(暗黙的な自動コピー)やClone(clone()による明示的な手動コピー)を使うと楽になるが、コストは高くなる。
そのため不要なclone()を見極めてそれを回避するプログラミングが出来るかどうか、というRustにおける根源的な話だろう。

もちろんCopyは最もコストが高い。
個々のコスト自体は通常clone()と同じだが、常に自動的にclone()が起きるため最もコストが高くなる。

Copyはコストが一番高いから出来る限り避けるべきだな
特にヒープを使うならCloneまでにしておくべき
可能ならばCloneも避けるべきだが

**デフォルトの名無しさん** · 2022/05/18(水) 10:39:05.95

複オジの主張まとめ(2)
50, 52, 57
=====
それは理解不足すぎるぜ
大文字のCopyはCopyトレイトを意味しCopyトレイトを実装するか否かの話だろ
moveは別方向の話であり比較対象にすらならない
比較するならば「Copy実装(必然的にClone)も実装」「Cloneのみ実装」「どちらも実装なし」の3つだな

デタラメすぎ
ムーブでビットパターンのコピーは発生しない
ビットパターンのコピーが発生するのは引数の値渡し等であってムーブとは関係ない
さらに引数の値渡しでのでビットパターンのコピーとCopyのコピーも全く異なる
Copyのコピーはディープであって高コスト

これだけCopyやCloneを理解していない連中が多い状況だと
>>30の質問に答えられるかどうかは最低限クリアすべきテストとして有用ではないか？
フィボナッチ自体はもちろんどうでもよい話だがCopyやCloneを避けるRustの基本ができるかどうかわかる点で

**デフォルトの名無しさん** · 2022/05/18(水) 10:41:41.09

複オジの一連の主張を読んでから>>83の複オジ質問を読むべし

**デフォルトの名無しさん** · 2022/05/18(水) 10:44:21.46

複おじに反応するやつも複おじ

**デフォルトの名無しさん** · 2022/05/18(水) 10:52:26.71

主張が毎回変わる
口調も毎回変わる
表記も毎回変わる
間違いなく多重人格者

**デフォルトの名無しさん** · 2022/05/18(水) 10:55:48.57

>>98
この文脈では○○にはなんでも当てはまるから意味がないよね

以下なら議論になる？
Ａ「copy/cloneはmoveよりコストが生じるので、copyが必要な部分とそうでない部分で構造体を分離してでも出来るだけmoveを使用する」
Ｂ「copy/cloneのコストはmoveよりコストが生じるとは限らないので、一部でもcopyが必要な部分がある構造体は丸ごとcopyして構わない」

**デフォルトの名無しさん** · 2022/05/18(水) 11:00:11.80

>>116
そこまでいったらネット上では別人で良いだろ

**デフォルトの名無しさん** · 2022/05/18(水) 11:05:55.27

>>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

**デフォルトの名無しさん** · 2022/05/18(水) 11:24:29.81

メモ化されてないんやから遅くなるのは当然
>>108は定義を示しただけちゃう？

**デフォルトの名無しさん** · 2022/05/18(水) 11:25:30.07

つかオーバーフローしとるな

**デフォルトの名無しさん** · 2022/05/18(水) 11:29:30.10

>>119
そのコードだとcopyは何回くらい発生してるのだろう
0回？1回？2回？3回？たくさん？

**デフォルトの名無しさん** · 2022/05/18(水) 12:13:31.53

ぼくのかんがえたさいきょうのcountup<T>()をみんなバカにしたので
ぼくのかんがえたさいきょうのfibonacchi<T>()でやっつけようとしたら
わざをだすまえにボコボコにやられてしまいました
く、くやしいです！

**デフォルトの名無しさん** · 2022/05/18(水) 13:41:52.15

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),
}
}

**デフォルトの名無しさん** · 2022/05/18(水) 13:50:00.30

>>119
計算量はO(n), メモリ使用量は定数オーダーにできるのになんで定義どおり実装したの？

**デフォルトの名無しさん** · 2022/05/18(水) 14:41:04.77

>>123
ぼくのかんがえたさいきょうのfizzbuzz<T>()もわすれないで

**デフォルトの名無しさん** · 2022/05/18(水) 15:04:45.49

>>125
そんな魔法はありません

**デフォルトの名無しさん** · 2022/05/18(水) 16:48:40.40

>>127
え？

**デフォルトの名無しさん** · 2022/05/18(水) 17:53:48.13

Rust以前の問題じゃん
スレ違い

**デフォルトの名無しさん** · 2022/05/18(水) 23:22:25.69

>>124
そのclone()は子のf(n-1)とf(n-2)やそれらの子孫でも呼ばれるので1回ではなくO(n)より大きい
それをO(n)すなわちn回＋定数回以下に抑えられるのかどうか
あるいはO(0)回すなわち定数回以下に抑えられるのかどうか

**デフォルトの名無しさん** · 2022/05/18(水) 23:41:48.24

フィボナッチはu128を使ってもf(187)でオーバフローするからBigInt必須
clone()はできる限り少なくしないと厳しい

**デフォルトの名無しさん** · 2022/05/19(木) 00:10:47.96

どうでもいいから複おじはTRPL読み直してきてね

**デフォルトの名無しさん** · 2022/05/19(木) 00:16:28.52

>>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
}
}

**デフォルトの名無しさん** · 2022/05/19(木) 00:24:17.53

メモ化する必要ある？
直前の2つだけ記録しておけば次の一項が計算できるんだから再帰にする必要ないよね

**デフォルトの名無しさん** · 2022/05/19(木) 00:33:12.40

>>134
具体的にどうすればよいてすか？

**デフォルトの名無しさん** · 2022/05/19(木) 00:46:08.98

>>135
"rust fibonacci"でググるとよいです

**デフォルトの名無しさん** · 2022/05/19(木) 01:21:23.38

>>134
直前の2つだけ記録して再帰にしない方法ならば
おそらくこうする案だと思うが
>>133がO(n)で済んでいるのに対して
これは二重の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
},
}
}

**デフォルトの名無しさん** · 2022/05/19(木) 01:31:14.77

>>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っぽい書き方をする必要はない

**デフォルトの名無しさん** · 2022/05/19(木) 01:39:04.90

>>138
それもforが二重となっていて全体でO(n^2)だから同じく悪手