diff options
Diffstat (limited to 'test')
| -rw-r--r-- | test/datastructures/lichao.cpp | 22 | ||||
| -rw-r--r-- | test/datastructures/monotonicConvexHull.cpp | 79 |
2 files changed, 91 insertions, 10 deletions
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index acd048f..c8a56a3 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -2,11 +2,11 @@ constexpr ll inf = LL::INF; #include <datastructures/lichao.cpp> -void stress_test() { +void stress_test(ll range) { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); - xs = Random::distinct<ll>(n, -1000, 1000); + xs = Random::distinct<ll>(n, -range, range); sort(all(xs)); vector<ll> naive(n, inf); @@ -15,9 +15,9 @@ void stress_test() { for (int operations = 0; operations < 1000; operations++) { { ll m = Random::integer<ll>(-100, 100); - ll c = Random::integer<ll>(-1000, 1000); - ll l = Random::integer<ll>(-1000, 1000); - ll r = Random::integer<ll>(-1000, 1000); + ll c = Random::integer<ll>(-range, range); + ll l = Random::integer<ll>(-range, range); + ll r = Random::integer<ll>(-range, range); Fun f{m, c}; tree.segmentInsert(f, l, r); @@ -31,11 +31,11 @@ void stress_test() { ll got = tree.query(xs[i]); ll expected = naive[i]; if (got != expected) cerr << xs[i] << endl; - if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } } - cerr << " tested random queries: " << queries << endl; + cerr << "tested random queries: " << queries << endl; } constexpr int N = 200'000; @@ -63,11 +63,13 @@ void performance_test() { hash ^= tree.query(x); t.stop(); } - if (t.time > 1000) cerr << " too slow: " << t.time << FAIL; - cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { - stress_test(); + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); performance_test(); } diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp new file mode 100644 index 0000000..0d4e10d --- /dev/null +++ b/test/datastructures/monotonicConvexHull.cpp @@ -0,0 +1,79 @@ +#include "../util.h" +struct MCH { + #include <datastructures/monotonicConvexHull.cpp> +}; + +struct Line { + ll m, c; + Line(ll m_, ll c_) : m(m_), c(c_) {} + ll operator()(ll x) {return m*x+c;} +}; + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer<int>(1, 100); + auto ms = Random::distinct<ll>(n, -range, range); + sort(all(ms), greater<>{}); + auto xs = Random::distinct<ll>(n*100, -range*n, range*n); + sort(all(xs)); + int i = 0; + + vector<Line> naive; + + MCH mch; + for (ll m : ms) { + ll c = Random::integer<ll>(-1000, 1000); + mch.add(m, c); + naive.emplace_back(m, c); + + for (int j = i + 100; i < j; i++) { + ll x = xs[i]; + + ll got = mch.query(x); + ll expected = naive[0](x); + for (auto l : naive) expected = min(expected, l(x)); + + if (got != expected) { + for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; + cerr << x << ": " << got << " " << expected << endl; + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto ms = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); + sort(all(ms), greater<>{}); + auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); + sort(all(xs)); + MCH mch; + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000); + ll m = ms[operations]; + ll x = xs[operations]; + + t.start(); + mch.add(m, c); + hash += mch.query(x); + t.stop(); + } + if (t.time > 100) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); + performance_test(); +} |