[過去ﾛｸﾞ] Rust part15 (1002ﾚｽ)

Rust part15 http://mevius.5ch.net/test/read.cgi/tech/1652347700/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

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

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

133: デフォルトの名無しさん [sage] 2022/05/19(木) 00:16:28.52 ID:IEr5OW/T >>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 } } http://mevius.5ch.net/test/read.cgi/tech/1652347700/133

137: デフォルトの名無しさん [sage] 2022/05/19(木) 01:21:23.38 ID:f3pwm4rC >>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 }, } } http://mevius.5ch.net/test/read.cgi/tech/1652347700/137

142: デフォルトの名無しさん [sage] 2022/05/19(木) 04:01:44.79 ID:f3pwm4rC >>141 mainに既にforループがある だから個々をO(n)で求めると全体でO(n^2)となる もし個々をO(log(n))で求めたとしても全体でO(n✕log(n))となる 一方で>>133は優れていて全体でO(n)だから圧倒的に良手 http://mevius.5ch.net/test/read.cgi/tech/1652347700/142

146: デフォルトの名無しさん [sage] 2022/05/19(木) 12:44:11.02 ID:2eGzkY/T >>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}"); } } fn f(n: usize) -> usize { fibonacci_iter().nth(n).unwrap() } fn fibonacci_iter() -> impl Iterator<Item=usize> { let mut p = 0; let mut q = 1; std::iter::from_fn(move || { let r = p; p = q; q += r; Some(r) }) } http://mevius.5ch.net/test/read.cgi/tech/1652347700/146

152: デフォルトの名無しさん [sage] 2022/05/19(木) 19:56:30.02 ID:X9gr9ket >>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)); assert_eq!(memo.nth(50), Some(12586269025)); } struct IterMemo<I> { iter: I, memo: Vec<usize>, } impl<I: Iterator<Item=usize>> IterMemo<I> { fn new(iter: I) -> Self { IterMemo { iter, memo: Vec::new() } } fn nth(&mut self, n: usize) -> Option<usize> { for _i in self.memo.len()..=n { if let Some(x) = self.iter.next() { self.memo.push(x); } } self.memo.get(n).cloned() } } http://mevius.5ch.net/test/read.cgi/tech/1652347700/152

156: デフォルトの名無しさん [sage] 2022/05/19(木) 21:27:22.70 ID:SnnzWk5R どうしてもイテレータが欲しいなら>>133に建て増ししたほうがよっぽど整理されていいよ https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=86c556a9709d959e8b9ecff08223b099 http://mevius.5ch.net/test/read.cgi/tech/1652347700/156

---

ﾒﾓ帳

(0/65535文字)

---

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

---

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

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.054s