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

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

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

---

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

---

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

---

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

151: デフォルトの名無しさん [sage] 2022/05/19(木) 19:01:17.07 ID:SnnzWk5R >>146はメモ捨ててるから計算済みのf(n)引っ張ってくるのに毎回O(n)かかるけどね イテレータと相性良いように見えるとしたら0..nループと組み合わせることしかしてこなかったmainが見せる幻想 そろそろRustの話に戻ってもらっていいですか？ http://mevius.5ch.net/test/read.cgi/tech/1652347700/151

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

181: デフォルトの名無しさん [sage] 2022/05/20(金) 07:35:06.49 ID:SXN+DpBP >>177 >>146のオーバーフロー対策をしてみた これでいい？ fn fibonacci_iter() -> impl Iterator<Item=usize> { let mut op: Option<usize> = Some(0); let mut oq: Option<usize> = Some(1); std::iter::from_fn(move || { op.take().map(|p| { op = oq.take().map(|q| { oq = q.checked_add(p); q }); p }) }) } fn main() { for (n, f) in fibonacci_iter().enumerate() { println!("f({n}) = {f}"); } } http://mevius.5ch.net/test/read.cgi/tech/1652347700/181

---

ﾒﾓ帳

(0/65535文字)

---

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

---

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

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.052s