概要

ヒューリスティックコンテストにおける小手先のテクニックを自分用にまとめたもの。 汎用的な手法というよりは細かい高速化テクニックが多め。 あくまで備忘録なので説明は少なめかつ順番は適当。 出典があるものはリンクで代用。

怪しい記述があれば@ethylene_66までご連絡いただければ幸いです。

テクニック

高速化前のボトルネック把握

• プロファイラを用いて時間がかかっている処理を把握してから、その処理を高速化
• Linuxではperf+https://github.com/KDAB/hotspotがおすすめ

• Windowsでは噂によるとIntelのVTune Profilerが良いらしい

乱数生成

• xorshiftですら遅い時はpcgかlcg←自分でベンチマークを取ったわけではないので怪しいかも

  • 自分は歴史的経緯によりmwcの亜種を使っている(気がする)
  • 要求される乱数の品質はその時々で異なるので、本当は提出ごとに最適な擬似乱数列生成法を探索するべき

• [0, n) から整数を一様サンプリングするには (rand32()*n)>>32

  • rand()%n は遅いので
  • 擬似乱数列生成法によってはこの手法では品質がかなり悪くなる
  • 要求される品質により%nと使い分ける

• bool乱数の高速化

  • trueの確率pが予めわかっていれば非型テンプレートパラメータを用いてコンパイル時に最適化可能
    • e.g. 近傍1と近傍2を割合25:75で適用したいときは bool_random<0.25>()

  template <auto P>
  inline bool bool_random() {
      return uint_random() < (P * 4294967296);
  }
  

特殊関数の前計算

• 特殊関数の計算は遅いので前計算する
• 特に焼きなまし法ではlogの前計算をすることで高速な受理/棄却判定が可能
  • 焼きなまし法での評価関数の打ち切り

constexpr int LOG_TABLE_SIZE = 1<<20;
double log_table[LOG_TABLE_SIZE];
double log_table_stable[LOG_TABLE_SIZE];
void init_log_table() {
    for (int i = 0; i < LOG_TABLE_SIZE; i++) {
        double x = ((double)i + 0.5) / LOG_TABLE_SIZE;
        log_table[i] = log(x);
        log_table_stable[i] = log_table[i];
    }
    // shuffle
    for (int i = 1; i < LOG_TABLE_SIZE; i++) {
        int j = rng.range_random_safe(LOG_TABLE_SIZE);
        swap(log_table[i], log_table[j]);
    }
}
inline double log_random() {
    static int idx = 0;
    if (idx == LOG_TABLE_SIZE)
        idx = 0;
    return log_table[idx++];
}