[過去ﾛｸﾞ] Rust part15 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

133(5): 2022/05/19(木)00:16 ID:IEr5OW/T(1/2) AAS
>>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}");
}
}
省13

---

137(1): 2022/05/19(木)01:21 ID:f3pwm4rC(1/3) AAS
>>134
直前の2つだけ記録して再帰にしない方法ならば
おそらくこうする案だと思うが
>>133がO(n)で済んでいるのに対して
これは二重のforによりO(n^2)になっていてこれは悪手

fn main() {
for n in 0..100 {
let f = f(n);
println!("f({n}) = {f}");
}
省17

---

142: 2022/05/19(木)04:01 ID:f3pwm4rC(3/3) AAS
>>141
mainに既にforループがある
だから個々をO(n)で求めると全体でO(n^2)となる
もし個々をO(log(n))で求めたとしても全体でO(n✕log(n))となる
一方で>>133は優れていて全体でO(n)だから圧倒的に良手

---

146(3): 2022/05/19(木)12:44 ID:2eGzkY/T(1) AAS
>>143
メモ化は良いが>>133のコードはインターフェースがあまりよくない
逆に>>138のコードはn個の列挙にO(n^2)も費やしている
以下のように書けばn個の列挙がO(n)に収まり、個別f(n)もO(n)で両立できる

fn main() {
println!("f(77) = {}", f(77));
for (n, f) in fibonacci_iter().enumerate() {
println!("f({n}) = {f}");
}
}
省13

---

152(3): 2022/05/19(木)19:56 ID:X9gr9ket(1) AAS
>>151
マジで>>133のメモ化が好ましいと思っているのか？
イテレータはメモ化とも相性が良い
例えば>>146のfibonacci_iter()を含むイテレータ汎用メモ化は即席でこんな感じ

fn main() {
let mut memo = IterMemo::new(fibonacci_iter());
assert_eq!(memo.nth(10), Some(55));
assert_eq!(memo.nth(0), Some(0));
assert_eq!(memo.nth(30), Some(832040));
assert_eq!(memo.nth(5), Some(5));
省19

---

156(2): 2022/05/19(木)21:27 ID:SnnzWk5R(4/4) AAS
どうしてもイテレータが欲しいなら>>133に建て増ししたほうがよっぽど整理されていいよ
外部ﾘﾝｸ:play.rust-lang.org

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 2.378s*