let mut s = self.s.clone();
s.sort();
while {
let is_ok = s.windows(k).all(|t_sub| {
// t_sub が回文でないことを調べる
// t_sub != t_sub.iter().copied().rev().collect_vec() // こう書くと実行時間500ms
!t_sub.iter().eq(t_sub.iter().rev()) // こう書くと実行時間50ms
});
cnt += is_ok as i64;
s.next_permutation()
} {}
逆順の Vec を作るかどうかで実行時間がかなり変わった。
↓実行時間
# 回文判定の部分を true に置き換え
===> multitime results
1: bash -c "./target/release/abc363_c <<< '10 5 abcdefghij' > /dev/null"
Mean Std.Dev. Min Median Max
real 0.016 0.001 0.015 0.015 0.018
user 0.011 0.004 0.006 0.011 0.018
sys 0.000 0.000 0.000 0.000 0.001
# 回文判定に Iterator の eq を使用
===> multitime results
1: bash -c "./target/release/abc363_c <<< '10 5 abcdefghij' > /dev/null"
Mean Std.Dev. Min Median Max
real 0.031 0.002 0.029 0.030 0.036
user 0.027 0.004 0.021 0.024 0.036
sys 0.000 0.000 0.000 0.000 0.000
# 回文判定で逆順の Vec を作成
===> multitime results
1: bash -c "./target/release/abc363_c <<< '10 5 abcdefghij' > /dev/null"
Mean Std.Dev. Min Median Max
real 0.388 0.026 0.357 0.381 0.440
user 0.383 0.027 0.356 0.375 0.434
sys 0.000 0.000 0.000 0.000 0.001
つまり、回文判定の処理において、逆順の Vec を作成した場合は Iterator の eq を使った場合と比べて25倍程度遅くなっている。
Vec のメモリ確保のコストを100、比較のコストを1として考えてみる。比較回数を5回とすると、
となり、21倍の差が生じる。このコスト見積もりにはある程度妥当性がある。
参考: 特別講義「定数倍高速化の技術」by tatyam - YouTube, CPU