「実践コンパイラ構成法」を読んだ
Rustでプライオリティキューを扱う
RustにはC++でいうstd::priority_queue的なものとしてstd::collection::BinaryHeapが存在する。 使い方はC++や他言語のqueueと一緒だが、Option型を返すので少し気を使う必要がある。
以下サンプル
use std::collections::BinaryHeap; fn main() { let mut heap = BinaryHeap::new(); heap.push(3); heap.push(1); heap.push(5); // unwrap()を使うパターン。あまり行儀がよくない(競技プログラミングでは使うかもしれない) println!("{}", heap.pop().unwrap()); // => 5 // if letでアンラップするパターン。 if let Some(n) = heap.pop() { println!("{}", n) // => 3 } // パターンマッチ。 match heap.pop() { Some(n) => println!("{}", n), // => 1 None => unreachable!(), } }
RustでPOJ 3253を解く
POJ 3253、蟻本にも載ってる。身近な問題がモデルになっているが、ハフマン符号を作るときのアルゴリズムとほとんど一緒で、Queueを使って実装すればで解ける。
この実装では貪欲法でナイーブな実装なので時間計算量は になっているけど、Rustの練習的な側面もあるので今回は妥協する。
競技プログラミング的な文脈ではこれで十分ACが取れる。
use std::mem::swap; fn main() { let mut n = 3; let mut l = vec![8, 5, 8]; let mut ans = 0; while n > 1 { let mut mii1 = 0; let mut mii2 = 1; if l[mii1] > l[mii2] { swap(&mut mii1, &mut mii2); } for i in 2..n { if l[i] < l[mii1] { mii2 = mii1; mii1 = i; } else if l[i] < l[mii2] { mii2 = i; } } let t = l[mii1] + l[mii2]; ans += t; if mii1 == n - 1 { swap(&mut mii1, &mut mii2); } l[mii1] = t; l[mii2] = l[n - 1]; n -= 1; } println!("{}", ans); }
アルゴリズムについての解説は蟻本p.50に任せる。
「プログラミングRust」を読んだ
１ヶ月くらい使ってずっとRustの勉強をしていて、やっとプログラミングRustを通読しました。 よく考えたらプログラミング言語についての本でここまで分厚い本を読んだのは初めてかもしれない...
この本はよくあるリファレンス的に用いる本とは違って、最初から最後まで通読して初めて価値の出てくる本のような気がします。
若干のオライリー本っぽさがありますが、厳密性とのトレードオフを考えれば現状で最高の入門書だと思います。（そもそもRustの学習曲線的に一番最初が山場だと思うので、入門書がこの分厚さになってしまうのは仕方のないこと）
