others/bench/dynamic_sequence/bench.cpp

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00
• Link: http://creativecommons.org/publicdomain/zero/1.0/deed.ja
• Link: https://github.com/uni-kakurenbo/competitive-programming-workspace

Code

/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ 28 GCC */
// #define DEBUGGER_ENABLED

#include "benchmark/benchmark.h"

#include "template/standard.hpp"

#include "data_structure/dynamic_sequence.hpp"
#include "data_structure/red_black_tree.hpp"

#include "utility/timer.hpp"

template<class T, class Tree>
static void test(const i32 times, const i64 range) {
    uni::random_adaptor<uni::random_engine_64bit> rng;

    Tree seq(range);

    REP(times) {
        std::array<uni::u64, 4> is = { rng(range), rng(range), rng(range), rng(range) };
        std::ranges::sort(is);

        seq.swap_ranges(is[0], is[1], is[2], is[3]);
    }

    assert(seq.size() == range);
}


template<class Context>
static void bench(benchmark::State& state) {
    const auto n = 1LL << state.range();

    while(state.KeepRunning()) {
        using Target = uni::dynamic_sequence<char, Context>;
        test<i64, Target>(1LL << 16, n);
    }
}


BENCHMARK(bench<uni::treap_context<uni::i64, false>>)
    ->Name("treap-A")->DenseRange(4, 28, 4);

BENCHMARK(bench<uni::treap_context<uni::i64, true>>)
    ->Name("treap-B")->DenseRange(4, 60, 4);


BENCHMARK(bench<uni::red_black_tree_context<uni::i64, false>>)
    ->Name("rbt-A")->DenseRange(4, 24, 4);
BENCHMARK(bench<uni::red_black_tree_context<uni::i64, true>>)
    ->Name("rbt-B")->DenseRange(4, 60, 4);


BENCHMARK(bench<uni::persistent_red_black_tree_context<uni::i64, false>>)
    ->Name("per-rbt-A")->DenseRange(4, 24, 4);

BENCHMARK(bench<uni::persistent_red_black_tree_context<uni::i64, true>>)
    ->Name("per-rbt-B")->DenseRange(4, 60, 4);


BENCHMARK_MAIN();

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: benchmark/benchmark.h: line -1: no such header

Back to top page