要約

• 時間制限がややシビアな問題。
• 動的な配列確保は定数倍がとても重いので気をつける必要がある。
  • 参考: CPU

回文判定

        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回とすると、

• Vec を作成した場合: 100 + 5
• Iterator の eq を作成した場合: 5

となり、21倍の差が生じる。このコスト見積もりにはある程度妥当性がある。

参考: 特別講義「定数倍高速化の技術」by tatyam - YouTube, CPU

オーダーを落としても計算時間が長くなることがある