https://blog.naskya.net/

[[ 🗃 ^wzWnj blog ]] :: [📥 Inbox] [📤 Outbox] [💥 Errbox] [🐤 Followers] [🤝 Collaborators] [🏗 Projects] [🛠 Commits]

Clone

HTTPS: git clone https://code.naskya.net/repos/wzWnj

SSH: git clone USERNAME@code.naskya.net:wzWnj

Branches

Tags

main :: content / post /

6eu0u8uze4h1.md

目的

2021 年 3 月から始まった AtCoder Heuristic Contest で遊ぶために準備をします。

AtCoder Heuristic Contest は、最適解を求めるのが難しい問題に対して決められた時間内に少しでも良い解を見つけて出力する競技です。

この競技では自分の書いたプログラムを評価するために様々なテストケースを試して点数を確認することが大事です。しかし、テストの実行には時間が掛かります。例えば実行時間制限が 3 秒間の問題で 500 個のケースを試したい場合、テストを 1 個ずつ実行していると 25 分間もの時間が掛かります。そこでテストケースを並列で実行して時間を短縮したくなります。例えばプログラムを 16 個並列で動かすと、500 個のテストを(単純に 16 で割れば) 1.6 分間で実行できるようになります。

また、自分の書いたプログラムがどのような途中経過を経て最終的な解を出したのかを把握することも重要です。AtCoder Heuristic Contest では公式のビジュアライザが提供されていて、テストケースの入力とプログラムからの出力をビジュアライザに与えるとそのビジュアライズ結果が svg 画像として返ってくるようになっています。これを活用して、

条件を満たすようにしながら長方形をなるべく上手く敷き詰める問題
20 × 20 のマスに英文字を配置して指定された単語をできるだけ作る問題

のように求解の途中経過を動画として出力できると良いです。解だけでなく得点がどのように変化しているかをグラフで表示もしたいです。

そこで、以下のことがそれぞれコマンドを一つ叩くだけでできるようにします。

作ったものはここに置いてあります。Issue や Pull Request は歓迎します。使い方がちゃんと分かっているか怪しいけど。

テンプレートの作成

時計

いつも実行時間を計測するので、それをテンプレートに含めておきましょう。以下の実装は一例で、好みに合わせて内容を変えてもよいです。他にも作っておきたいものがあったら作っておきます(焼き鈍し法に用いる温度計とかもある方が良いかな)。

#include <chrono>

namespace utility {
  struct timer {
    private:
    const std::chrono::system_clock::time_point start;

    public:
    constexpr unsigned time_limit = 2000 - 20;  // 20 ms くらいは余裕を持たせる

    timer() noexcept : start(std::chrono::system_clock::now()) {}

    // 経過時間 (ms) を返す
    [[nodiscard]] auto elapsed() const {
      using namespace std::chrono;
      return duration_cast<milliseconds>(system_clock::now() - start).count();
    }

    // 経過時間が制限時間の num/den 倍未満かを返す
    // 例えば frac<1, 2>() は経過時間が制限時間の 1/2 未満かを返す
    template <unsigned num, unsigned den> [[nodiscard]] bool frac() const {
      return elapsed() < time_limit * num / den;
    }

    // 経過時間が制限時間未満かを返す
    [[nodiscard]] bool good() const { return elapsed() < time_limit; }
  };
}  // namespace utility

int main() {
  const utility::timer tm;

  // 制限時間内のループ
  while (tm.good()) {
    // なんかする
  }
}

入出力

出力する内容(問題の解)は result 型のオブジェクトとしてまとめます。求解を行う solve 関数と解を出力する print 関数をそれぞれ作成して main 関数からそれらを呼ぶようにします。

#include <iostream>  // std::cin, std::cout

// 問題の解
struct result {};

// res の内容を os に出力する
void print(std::ostream& os, const result& res) {}

// 入力を is から読み、問題を解いて答えを res に書き込む
void solve(std::istream& is, result& res) {}

int main() {
  result res;             // result 型のオブジェクトを作成
  solve(std::cin, res);   // 入力は標準入力から受け取る
  print(std::cout, res);  // 出力は標準出力へ
}

例えば AHC001 なら出力する内容は 4 つの数の配列(a, b, c, d)なので、これを格納するのに std::vector<int> を用いるなら以下のようになります。

#include <iostream>
#include <vector>

struct result {
  std::vector<int> a, b, c, d;  // 答え
};

void print(std::ostream& os, const result& res) {
  // 指定された形式で出力
  for (std::size_t i = 0; i < std::size(res.a); ++i)
    os << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << '\n';
}

void solve(std::istream& is, result& res) {
  // 入力は is から読む
  int n;
  is >> n;

  // ... (答えを求める)
}

int main() {
  result res;
  solve(std::cin, res);
  print(std::cout, res);
}

何故このようにするかというと、

#include <fstream>
#include <iostream>
#include <sstream>

// is から x を受け取る
int scan_from(std::istream& is) {
  int x;
  is >> x;
  return x;
}

// os に Hello と出力する
void print_to(std::ostream& os) {
  os << "Hello\n";
}

int main() {
  // 入力
  std::ifstream ifs("source.txt");
  std::istringstream iss("10");

  int from_stdin  = scan_from(std::cin);  // OK (標準入力から整数を入力)
  int from_file   = scan_from(ifs);       // OK (ファイルから整数を入力)
  int from_string = scan_from(iss);       // OK (from_string = 10)

  // 出力
  std::ofstream ofs("output.txt");
  std::ostringstream oss;

  print_to(std::cout);  // OK (標準出力へ Hello と出力)
  print_to(ofs);        // OK (ファイルへ Hello と出力)
  print_to(oss);        // OK (oss 内に保持されている文字列に Hello を付加)
}

というように関数で入力元を std::istream& で、出力先を std::ostream& 型にすると同じ関数で様々な相手に入出力を行えるからです。通常の実行で標準入出力を用いる必要があるのはもちろん、テストケースの並列実行を行うにはファイル入出力も必要になるのでこのように抽象化しておきます。

並列実行

以下のようなコードを並列実行することを考えます。簡単のために、整数を 2 つ入力してその和を求める単純なプログラムにしています。

#include <iostream>

struct result {
  int val;
};

// 解の出力
void print(std::ostream& os, const result& res) {
  os << res.val << '\n';
}

// 求解 (a, b を読んで res.val に a + b を書き込むだけ)
void solve(std::istream& is, result& res) {
  int a, b;
  is >> a >> b;
  res.val = a + b;
}

int main() {
  result res;
  solve(std::cin, res);
  print(std::cout, res);
}

テストケースは test/in ディレクトリに入っているテキストファイルで、結果を test/out ディレクトリにテキストファイルとして出力したいとします{{< note 例えば入力は test/in/0000.txt, test/in/0001.txt, ...、出力は test/out/0000.txt, test/out/0001.txt, ... など >}}。

まずは並列実行のことを考えずに、テストケースを一つずつ連続で実行する処理を書いてみます。

#include <filesystem>
#include <fstream>
#include <string_view>

struct result {
  int val;
};

void print(std::ostream& os, const result& res) {
  os << res.val << '\n';
}

void solve(std::istream& is, result& res) {
  int a, b;
  is >> a >> b;
  res.val = a + b;
}

int main() {
  constexpr std::string_view TEST_IN_DIR = "test/in/";
  const std::string TEST_OUT_DIR         = "test/out/";

  for (auto&& file : std::filesystem::directory_iterator(TEST_IN_DIR)) {
    if (file.path().extension() != ".txt") continue;

    // test/in/xxxx.txt
    std::ifstream ifs(file.path());
    // test/out/xxxx.txt
    std::ofstream ofs(TEST_OUT_DIR + file.path().filename().string());

    result res;

    // 入力はファイルから
    solve(ifs, res);
    // 出力はファイルへ
    print(ofs, res);
  }
}

C++17 以降のバージョンを使っているなら、std::filesystem::directory_iterator を使って for ループでテストケースを走査するのがいいでしょう。テストケースの入っているディレクトリを書く必要はありますが{{< note 別に標準入力から受け取るとかにしてもいいけど。 >}}、ファイルの名前やループの回数を直書きする必要はありません。

これを並列化します。並列処理について何も分かっていないので、おかしな点があったら教えてください。

#include <algorithm>
#include <array>
#include <bitset>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <mutex>
#include <string>
#include <string_view>
#include <thread>

std::mutex mtx;

template <class Func> void safe_invoke(const Func& f) {
  std::lock_guard lock(mtx);
  f();
}

struct result {
  result() = default;
  int val;
};

void print(std::ostream& os, const result& res) {
  os << res.val << '\n';
}

void solve(std::istream& is, result& res) {
  int a, b;

  const auto scan = [&] {
    is >> a >> b;
  };
  // safe_invoke を通して実行する
  safe_invoke(scan);

  res.val = a + b;

  // 重い処理の再現
  // std::this_thread::sleep_for(std::chrono::seconds(2));
}

int main() {
  constexpr std::string_view TEST_IN_DIR = "test/in/";
  const     std::string TEST_OUT_DIR     = "test/out/";

  constexpr unsigned threads = 15;  // CPU のスレッド数か、それより少し小さく
  const auto tests           = std::distance(std::filesystem::directory_iterator(TEST_IN_DIR),
                                             std::filesystem::directory_iterator {});

  auto it = std::filesystem::directory_iterator(TEST_IN_DIR);

  unsigned started  = 0u;  // 始まったテストの数
  unsigned finished = 0u;  // 終わったテストの数

  std::array<std::thread, threads> jobs;   // スレッドを置いておく場所
  std::array<std::ifstream, threads> ifs;  // (ファイル)入力ストリームを置いておく場所
  std::array<std::ofstream, threads> ofs;  // (ファイル)出力ストリームを置いておく場所
  std::array<result, threads> res;         // result を置いておく場所

  std::bitset<threads> running;  // running[i] が true なら jobs[i] は実行中

  // 進捗状況を表示
  const auto show_progress = [&, bar_length = 50u, &os = std::cerr] {
    std::lock_guard lock(mtx);
    const auto bar_top = bar_length * finished / tests;
    os << "[\033[92m";
    for (unsigned j = 0u; j < bar_length; ++j)
      os << (j <= bar_top ? '#' : ' ');
    os << "\033[39m] " << (100 * bar_top / bar_length) << "% (" << finished << '/' << tests << ')';
    if (tests == finished)
      os << std::endl;
    else
      os << '\r' << std::flush;
  };

  // 最初は finished = 0 なので進捗率 0% のプログレスバーが表示される
  show_progress();

  // 全テストが終了するまでのループ
  while (finished < tests) {
    for (unsigned i = 0u; i < threads; ++i) {
      if (!running[i] && started < tests) {
        // もし jobs[i] が実行中でなくて、まだ開始していないテストがあるとき
        // テストを開始して running[i] を true にする
        std::lock_guard lock(mtx);
        ifs[i]  = std::ifstream((*it).path());
        ofs[i]  = std::ofstream(TEST_OUT_DIR + (*it).path().filename().string());
        res[i]  = result {};
        jobs[i] = std::thread(solve, std::ref(ifs[i]), std::ref(res[i]));
        running[i] = true;
        ++started;
        // テストケースを指すイテレータを進めて、次のテストケースを指すようにする
        ++it;
      } else if (running[i]) {
        // jobs[i] の終了を待ち、running[i] を false に戻す
        jobs[i].join();
        running[i] = false;
        ++finished;
        // safe_invoke を通して print 関数を呼ぶ
        safe_invoke([&] { print(ofs[i], res[i]); });
        show_progress();
      }
    }
  }
}

排他制御のために std::mutex mtx をグローバルに置いて、ファイル入出力などの操作は safe_invoke 関数を通して行うことにしています。std::future 等の機能を使うと終了したスレッドから順に次の処理を開始して待ち時間を減らしたりすることもできると思いますが、ヒューリスティックコンテストではほぼ同時に開始したタスクが制限時間(3 秒間など)を迎えるとほぼ同時に終了するので、単純に各スレッドの終了を待つ実装にしておいていいと思います。

コメントアウトしてある // 重い処理の再現 の部分(2 秒間待つ処理)のコメントアウトを解除して、テストケースを用意して実行を行うと並列でテストが実行できていることが分かります。

{{< youtube JZnXnUPy9yI >}}

途中経過の出力

今度は(全然面白くないですが)以下の例を考えます。

#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>

namespace utility {
  // さっきと同じ
}

struct result {
  double x;
};

void print(std::ostream& os, const result& res) {
  os << std::fixed << std::setprecision(15) << res.x << '\n';
}

void solve(std::istream& is, result& res) {
  const utility::timer tm;
  std::mt19937_64 engine(std::random_device{} ());

  int a, b;
  is >> a >> b;

  // f(x) = ax^2 + bx
  const auto f = [&](const double x) {
    return a * x * x + b * x;
  };

  std::uniform_real_distribution<> dist(-1e7, 1e7);

  // 適当な初期値を設定し、初期スコアを計算
  res.x      = dist(engine);
  double val = f(res.x);

  while (tm.good()) {
    // 乱数を発生させる
    const double cand     = dist(engine);
    const double cand_val = f(cand);

    // スコアが改善した場合には答えを更新する
    if (cand_val < val) {
      res.x = cand;
      val   = cand_val;
    }
  }
}

int main() {
  result res;
  solve(std::cin, res);
  print(std::cout, res);
}

標準入力から整数 a, b (a>0) を受け取って、ax2 + bx をできるだけ小さくする x を求める問題です。平方完成をすれば最適解はすぐに求まりますが、ここでは 2 秒間 double 型の乱数を生成し続けて結果が良くなれば採用、悪くなれば棄却ということをしています。

求解の途中経過を出力するプログラムを書いてみます。

#include <cassert>
#include <chrono>
#include <condition_variable>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <mutex>
#include <random>
#include <string>
#include <thread>

std::mutex mtx;
std::condition_variable cv;
bool is_paused = false, is_finished = false;

namespace utility {
  // さっきと同じ
}

struct result {
  double x;
};

void print(std::ostream& os, const result& res) {
  os << std::fixed << std::setprecision(15) << res.x << '\n';
}

void solve(std::istream& is, result& res) {
  const utility::timer tm;
  std::mt19937_64 engine(std::random_device{} ());

  int a, b;
  is >> a >> b;

  const auto f = [&](const double x) {
    return a * x * x + b * x;
  };

  std::uniform_real_distribution<> dist(-1e7, 1e7);

  res.x      = dist(engine);
  double val = f(res.x);

  while (tm.good()) {
    const double cand     = dist(engine);
    const double cand_val = f(cand);
    if (cand_val < val) {
      res.x = cand;
      val   = cand_val;
    }

    // スナップショットを取る準備ができていることをメインスレッドに知らせる
    {
      std::lock_guard lock(mtx);
      is_paused = true;
    }
    cv.notify_one();
    std::unique_lock lock(mtx);

    // スナップショットを取り終わるまで待機
    cv.wait(lock, [&] { return (!is_paused) || is_finished; });
  }

  // 求解が終了したことをメインスレッドに知らせる
  {
    std::lock_guard lock(mtx);
    is_finished = true;
  }
  cv.notify_one();
}

int main() {
  const auto padding = [](const unsigned i) {
    assert(i <= 9999);
    std::string s = "000" + std::to_string(i);
    return s.substr(std::size(s) - 4);
  };

  result res;
  std::thread job(solve, std::ref(std::cin), std::ref(res));

  const std::string SNAPSHOT_OUT_DIR = "test/snapshot/";
  unsigned num                       = 0;

  const utility::timer tm;

  auto prev = std::chrono::system_clock::now();

  while (tm.good()) {
    {
      // スナップショットを取る準備ができるまで待機
      std::unique_lock lock(mtx);
      cv.wait(lock, [&] { return is_paused || is_finished; });

      auto now = std::chrono::system_clock::now();

      // 前回のスナップショットから 10 ms 以上経過している時にのみスナップショットを取る
      if (std::chrono::duration_cast<std::chrono::milliseconds>(now - prev).count() >= 10) {
        std::ofstream ofs(SNAPSHOT_OUT_DIR + padding(num) + ".txt");
        print(ofs, res);
        ++num;
        prev = now;
      }

      is_paused = false;
    }
    // スナップショットを取り終わったことを求解するスレッドに知らせる
    cv.notify_one();
  }

  // スナップショットはもう取らないことを求解のスレッドに知らせる
  {
    std::lock_guard lock(mtx);
    is_finished = true;
  }
  cv.notify_one();

  // 求解のスレッドが終了するのを待つ
  job.join();
}

書き方が合っているかは分かりません。おかしな点があったら教(ry

この例では、10 ミリ秒毎に途中経過をファイルに出力しています。実行すると確かにスナップショットが保存されていることが分かります。

{{< youtube t3cKPNxLuFE >}}

書いたものをまとめる

一つのソースファイルで並列実行と途中経過の出力を行えるようにしたいので、ファイルを一つにまとめます。

こんな感じにした

これで、一つのソースファイルで通常の実行と並列実行と途中経過の出力ができるようになっています。使用する時はこのテンプレートをそのままコピーして、struct result の中身と print 関数の中身を問題の出力形式に合わせて変更し、solve 関数に答えを求めるコードを書けばよいです。

#if ~ #endif 内の #include や #define を

#ifdef something
#  include <thread>
#  include <mutex>
#endif

のようにインデントしていないのは、AtCoder の提出画面でシンタックスハイライトが壊れるからです。このページでも壊れています。 他にも気になる部分があったら直しつつ使ってください。

小道具を用意する

ファイルは以下のように配置されているとします。 utility ディレクトリ内にある 3 つのプログラムを書きます。

.
├─ test
│  ├─ in
│  │  ├─ 0000.txt
│  │  ├─ 0001.txt
│  │  └─ ...  <- テストケースたち
│  │
│  ├─ out
│  │  ├─ 0000.txt
│  │  ├─ 0001.txt
│  │  └─ ...  <- 各テストの出力たち (並列実行の結果)
│  │
│  └─ snapshot
│     ├─ 0000.txt
│     ├─ 0001.txt
│     └─ ...  <- あるテストの解のスナップショットたち
│
├─ utility
│  ├─ calc_score.cpp       <- テストの入力と出力を順番に受け取ってスコアを出力する
│  ├─ calc_multi_scores.py <- 並列実行の結果から点数を計算する
│  └─ draw_graph.py        <- 途中経過のスナップショットからスコアのグラフを作成する
│
└─ src
    └─ main.cpp <- 求解する(提出する)プログラム
  1. テストの入力と出力を標準入力から順番に受け取ってスコアを標準出力に出力するプログラムを書く
    • 問題によって内容が大きく異なるので省略
  2. 並列実行の結果から点数を計算し最高得点・最低得点・平均得点と得点の分布を出力するプログラムを書く
    • 多倍長整数を使いたくなるので Python を使うといいかも
    • こういう感じかな
  3. 途中経過のスナップショットからスコアのグラフを作成するプログラムを書く
    • matplotlib を使いたくなるのでこれも Python を使うといいかも
    • こういう感じかな
    • Python の書き方分からん

グラフを作成するプログラムは、さっきの二次式の値を最小化するプログラムで実行するとこんな感じのグラフを得ました(最初の 3 つのスナップシットのデータを含めると変化が激しすぎたのでそこは削りました)。 また、手持ちの AHC004 の解答で実行するとこんなグラフを得ました。 スコアの遷移を見るとプログラムの性質や改善点などが見えますね。

Makefile を書く

最後の頑張りです。冒頭に書いたように、コマンド一発で以下のことができる状態を目指します。cast=0000 の部分はテストケース名です。ケースを指定しない場合、0000.txt を入力にして実行します。

ビジュアライズには AtCoder 公式の Rust 製ビジュアライザを使用するので、visualizer ディレクトリを作ってその中に配布されたビジュアライザのアーカイブを解凍した中身を全部入れます。visualizer の直下に Cargo.toml がある状態になっていればよいです。

こんな感じにした

Makefile は書いたことが無いので書き方が合っているのか分か(ry

svg 画像を png 画像に変換し、更にそこから動画を作成するために ffmpeg を用いています。パッケージマネージャからインストールした ffmpeg でこれを実行しようとしても配布されているバージョンでは有効化されていない機能を用いているためにエラーとなるはずなので、ソースをダウンロードしてきて特定のフラグ{{< note --enable-librsvg, --enable-gpl, --enable-libx264 >}}を有効化して自分でビルドする必要があります。詳しくは調べてください(書くのが疲れてきた)。

また上記の Makefile では OPEN = /mnt/c/Windows/... としていますが、これは私が Windows Subsystem for Linux を使っているからです。Windows Subsystem for Linux では alias open=/mnt/c/Windows/System32/WindowsPowerShell/v1.0/powershell.exe /c start などとしておくと open vis.mov で動画が再生できたりとかする{{< link https://twitter.com/kymn_/status/1340670827218407425 >}}ので、これを利用しています。当然 Windows Subsystem for Linux ではない環境でこれを実行してもエラーとなるので、その場合は引数にファイル名を与えて動画と画像を開くことができるコマンドを OPEN = ... の右辺に書いてください。

引数無しで単に make を実行すると 5 つのバイナリ (normal.out, debug.out, parallel.out, snapshot.out, calc_score.out) のコンパイルが行われます。書いたコードのコンパイルが通るかのみを確認したい時に使ってください(コンパイラが警告を出すようなコードを書いた場合、ヤバい量の警告が出るかもしれませんが)。

掲載しているコードは自由に使用していただいて構いませんが、使用によって生じたあれこれに関して私は一切の責任を負いかねます。

[See repo JSON]