Rustで動的計画法：Matching
はじめに
動的計画法を実装してみて、Rustの勉強をやってみる。問題としてはEducational DP Contestという動的計画法の練習を目的としたコンテストのものを使用。
AからZまで問題が設定されているが、今回はOのMatchingを解いてみる。男女の相性関係が与えられて、それを満たすペアの集合の組み合わせを求める問題。
利用したライブラリ
標準入力からデータを読み取る部分はproconioを利用。
最終的には使わなくなっているが、標準ライブラリのHashMapも使う。
完成したコード
最初に完成したコード。
use std::collections::HashMap;
use proconio::input;
const MOD: u64 = 10u64.pow(9) + 7;
fn main(){
input! {
n: usize,
chemistry: [[u8; n]; n],
}
let mut dp: HashMap<Vec<usize>, u64> = HashMap::new();
dp.insert(vec![], 1);
for i in 0.. n {
let mut next_dp: HashMap<Vec<usize>, u64> = HashMap::new();
for j in 0..n {
if chemistry[i][j] == 1u8 {
for (females, num) in &dp {
if females.iter().any(|x| *x == j) == false {
let mut new_females = females.clone();
new_females.push(j);
new_females.sort();
if let Some(entry) = next_dp.get(&new_females) {
let new_num = (*entry + *num) % MOD;
next_dp.insert(new_females, new_num);
} else {
next_dp.insert(new_females, *num);
}
}
}
}
}
dp = next_dp;
}
let key = Vec::from_iter(0..n);
if let Some(value) = dp.get(&key) {
println!("{:?}", value);
} else {
println!("0");
}
}
アルゴリズム
男性を1人ずつ追加していって、dp[x]は、
HashMap
HashMapは、他言語での「連想配列」を提供するコレクタである。ここでは「既にマッチング済みの集合」をキーとして、その組み合わせの数を保持するために使っている。HashMapのキーとなるためには、Hash, Eqの2つのトレイトを実装していればキーになれる。Vec<T>の場合は、TがHashを実装している場合実装されるため、Vec<usize>はキーになれる。
そこで、マッチング済みの番号をベクタにして、それをキーにしてHashMapとしている。ただ何も考えないと、[0, 1, 2]と[1, 0, 2]が別のものになってしまうので、sortしてからキーにするようにしている。
計算時間の測定
ただし、このままではとても遅い。小さい問題の時は気にならないのだが、例題となっている
ビット演算を使う
マッチング済みの集合を表現するのにベクタを使っているのは明らかにオーバヘッドが大きい。問題において
ループの順番も変えていて、dpとしては、1の数で何人目のものか分かるので、chemistryもビット列に変換している。こっちの方が僅かであるが速かった。
use proconio::input;
const MOD: u64 = 10u64.pow(9) + 7;
fn main(){
input! {
n: usize,
chemistry: [[u8; n]; n],
}
let mut chem = vec![0usize; n];
for i in 0..n {
let mut bits = 0usize;
for j in 0..n {
if chemistry[i][j] == 1 {
bits |= 1usize << j;
}
}
chem[i] = bits;
}
let pattern = 2usize.pow(n as u32);
let mut dp = vec![0u64; pattern];
dp[0] = 1;
for i in 0..n {
let male = chem[i];
for females in 0..pattern {
if females.count_ones() == i as u32 {
for j in 0..n {
let mask = 1usize << j;
if females & mask == 0 && male & mask == mask {
let new_famales = females | mask;
dp[new_famales] = (dp[new_famales] + dp[females]) % MOD;
}
}
}
}
}
let key = 2usize.pow(n as u32) - 1;
println!("{}", dp[key]);
}
計算時間の測定
問題作成
計算時間の測定のために問題を作成したスクリプト。相性の行列をどのように作成するかが、計算時間に影響する。最悪値としてはすべて1の行列を用意すればいいのだが、それも面白くないので、必ず解が１つはあるように設定して、あとは半分ぐらいが1となるような行列を作るようにした。
#!/user/bin/env python
import random
import sys
n = int(sys.argv[1])
chemistry = [[0 for i in range(n)] for j in range(n)]
male = list(range(0, n))
female = list(range(0, n))
random.shuffle(female)
for i in range(n):
chemistry[male[i]][female[i]] = 1
for i in range(int(n * n / 2)):
chemistry[random.randrange(0, n)][random.randrange(0, n)] = 1
print(n)
for i in range(n):
print(*chemistry[i])
測定結果
測定結果をグラフに示す。最初に作成したVec<usize>をキーとしたHashMapを用いたもの（vec hash)と、最後に示したビット列を用いたもの(bit)の他に、最初のHashMapのキーをビット列 (usize)に変更したもの（bit hash）ものも用意した。
Y軸は対数なので、vec hashと比較してbit hashは10倍、bitはさらに10倍速いことが分かる。
アルゴリズムとしては、ビット列を用いたものはfemalesのループでHashMapを使った方は必要な分しか回さないので、答えが小さい場合、つまり相性行列に1が少ない場合は効率が良いことが期待される。
そこで、1の数を1/8まで減らした場合のグラフが以下のようになる。bitは変化ないが、HashMapの場合は処理時間が短くなっていることが分かる。
ビット列を用いた場合でも以下のように枝切りをすることで同等にすることはできる。ただ、そこまで効果は大きくないのと、1の数が1/2の場合の例では、条件が増えたためか逆に遅くなった。
if females.count_ones() == i as u32 && dp[females] != 0 {
型について
Rustではベクタのインデックスに使えるのはusizeもしくはisizeのみになっている。これは実行環境に応じてu32やu64になるのだが、型変換を暗黙的にはやってくれないので、キャストする必要があり煩雑になる。このため、maskなどu32やu64の方が適切であるような場面においてもusizeを使っている。
個人的にはちゃんと「値」と「インデックス」は区別して書かないといけないかな？と思いつつ、キャストだらけになるのも可読性が落ちるので、usizeを積極的に使っている。
関連記事
Rustで動的計画法の実装:
🐸Frog | 🌴Vacation | 🎒Knapsack | 🐍LCS | 🚶♂️Longest Path | 🕸️Grid | 💰Coins | 🍣Sushi | 🪨Stones | 📐dequeue | 🍬Candies | 🫥Slimes | 💑Matching | 🌲Indipendent Set | 🌻Flowers | 👣Walk | 🖥️Digit Sum | 🎰Permutation | 🐰Grouping | 🌿Subtree | ⏱️Intervals | 🗼Tower | 🐸Frog3
Discussion