ds_verifier's Introduction

ds_verifier

目標

データ構造のverifyはそれよりより下位のデータ構造でverifyするべき.
例えば, セグ木のfoldは合っているが, atが実は間違っていますみたいな事故を減らしたい. より多くの種類のクエリを簡単にverifyしたい.

Example

累積和のライブラリであるds::accumlationをverifyするとする.

ds::verifierは

template<
  class Target, // verifyするデータ構造
  class Checker, // Targetが正しく動いているかを確かめるデータ構造
  class Gen, // std::mt19937などの乱数生成器
  class InitMethod, // データ構造の初期化の方法
  const std::size_t Q, // クエリの回数
  class Query // verifyしたいクエリの種類
>
class verifier { /* ... */ }

という定義になっている.

VERIFY_START() {
  using i32 = ds::int32; // 乱数で初期化できるようにしたintのラッパ
  using accum_verify = ds::verifier<
    ds::array_wrapper<i32, ds::accumulation<i32>>, // accumulationのラッパ (最初に累積和を計算する)
    ds::array_wrapper<i32, std::vector<i32>>, // std::vectorのラッパ (forで毎回, 累積和を計算する)
    std::mt19937,
    ds::random_init_vector<i32, 100>, // データ構造を要素100個のランダムなintで初期化する
    300, // クエリは300回
    ds::accum_from0<i32> // [0, r)の累積和を計算するクエリをverifyする
    >;

  std::mt19937 gen(1);
  VERIFY(accum_verify()(gen, "accumulation_example1")); // verify
}
VERIFY_END();

このソースコードを実行すると, verifyした結果をjsonで出力する.

verify自動化

現段階なので, よりよくしていきたい

verifyしたいコードが入っているディレクトリのCMakeLists.txtにこれを書く

file(GLOB_RECURSE verify_source_list *_verify.cpp)

set(verify_list)
file(REMOVE "${CMAKE_BINARY_DIR}/verify_list")

foreach(verify_source IN LISTS verify_source_list)
  file(RELATIVE_PATH relative_source "${CMAKE_SOURCE_DIR}" "${verify_source}")
  message("verify_source: ${relative_source}")
  get_filename_component(verify_target "${verify_source}" NAME_WE)
  add_executable("${verify_target}" "${verify_source}")
  target_link_libraries("${verify_target}" ds_verifier)
  list(APPEND verify_list "${verify_target}")
  file(APPEND "${CMAKE_BINARY_DIR}/verify_list" "${CMAKE_CURRENT_BINARY_DIR}/${verify_target}:${relative_source}\n")
endforeach()

ソースコードをビルド

out-of-sourceで

$ mkdir build
$ cd build
$ cmake ..
$ make

$ python3 verify.py buildでverify

$ python3 verify.py build --allをすると, すべてverify済みのときにverifyをスキップします.

$ python3 generate.pyでGitHub Pages用のHTMLソースを生成

ds_verifier's People

Contributors

Watchers

ds_verifier's Issues

random_choise

template<class Q, class... Qs>
struct Checker {
  static void checker(int n) {
    if(sizeof...(Qs) == n) {
      std::cout << Q::name() << std::endl;
    }
    else {
      Checker<Qs...>::checker(n);
    }
  }
};

template<class Q>
struct Checker<Q> {
  static void checker(int n) {
    assert(n == 0);
    std::cout << Q::name() << std::endl;
  }
};


struct A { static const char* name() { return "A"; } };
struct B { static const char* name() { return "B"; } };
struct C { static const char* name() { return "C"; } };
struct D { static const char* name() { return "D"; } };

int main() {
  Checker<A, B, C, D>::checker(1);
}

Queryの柔軟性を高める

このまままと柔軟性がない

template<class Query>
Query::result_type query(const Query::arg_type&);

template<>
accum_from0<value_type>::result_type query<accum_from0<value_type>>(const accum_from0<value_type>::arg_type& i) {
    //...
}

とすると wavelet matrixのverifyに

using quantile = concat_query<range_sorted<value_type>, access_index<value_type>>;
quantile::result_type query<quantile>(const quantile::arg_type& arg) {
    //...
}

これができる.

concat_queryは, 最初に特殊化しておけば, std::vectorに対しては愚直に, wavelet matrixにはquantileを使うことができて良さそう.