From ff3b67478b1f08b0a2b83565de8a454e23441f3a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 15:41:25 +0200 Subject: more testcases --- content/datastructures/monotonicConvexHull.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'content/datastructures/monotonicConvexHull.cpp') diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 44bff83..119015e 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,27 @@ -// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue +// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { - ll m, b; - ll operator()(ll x) {return m*x+b;} + ll m, c; + ll operator()(ll x) {return m*x+c;} }; vector ls; -int ptr = 0; +ll ptr = 0; bool bad(Line l1, Line l2, Line l3) { - return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); + return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll b) { // Laufzeit O(1) amortisiert - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { +void add(ll m, ll c) { // Laufzeit O(1) amortisiert + while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } - ls.push_back({m, b}); + ls.push_back({m, c}); ptr = min(ptr, sz(ls) - 1); } ll query(ll x) { // Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); - while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); } \ No newline at end of file -- cgit v1.2.3 From bbec09408867e82fb9dd9b242e6d99014f9534b6 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 20:10:57 +0200 Subject: more tests --- content/datastructures/dynamicConvexHull.cpp | 2 +- content/datastructures/monotonicConvexHull.cpp | 6 +-- tcr.pdf | Bin 691039 -> 691129 bytes test/datastructures/dynamicConvexHull.cpp | 72 +++++++++++++++++++++++++ test/datastructures/monotonicConvexHull.cpp | 7 +-- 5 files changed, 77 insertions(+), 10 deletions(-) create mode 100644 test/datastructures/dynamicConvexHull.cpp (limited to 'content/datastructures/monotonicConvexHull.cpp') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index d669847..dfcfe0b 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -4,7 +4,7 @@ struct Line { bool operator<(ll x) const {return p < x;} }; -struct HullDynamic : multiset> { +struct HullDynamic : multiset> { // max über Geraden // (for doubles, use inf = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 119015e..e84ad86 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,4 +1,4 @@ -// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue +// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { ll m, c; @@ -12,7 +12,7 @@ bool bad(Line l1, Line l2, Line l3) { return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll c) { // Laufzeit O(1) amortisiert +void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } @@ -20,7 +20,7 @@ void add(ll m, ll c) { // Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // Laufzeit: O(1) amortisiert +ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); diff --git a/tcr.pdf b/tcr.pdf index 48a07d7..1b58dc4 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp new file mode 100644 index 0000000..e0e56ef --- /dev/null +++ b/test/datastructures/dynamicConvexHull.cpp @@ -0,0 +1,72 @@ +#include "../util.h" +namespace dch { + constexpr ll INF = LL::INF; + #include +} + +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(1, 100); + + vector naive; + + dch::HullDynamic hd; + for (int i = 0; i < n; i++) { + ll m = Random::integer(-range, range); + ll c = Random::integer(-range, range); + hd.add(m, c); + naive.emplace_back(m, c); + + for (int j = 0; j < 100; j++) { + ll x = Random::integer(-range, range); + + ll got = hd.query(x); + ll expected = naive[0](x); + for (auto l : naive) expected = max(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; + dch::HullDynamic hd; + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer(-1'000'000'000, 1'000'000'000); + ll c = Random::integer(-1'000'000'000, 1'000'000'000); + ll x = Random::integer(-1'000'000'000, 1'000'000'000); + + t.start(); + hd.add(m, c); + hash += hd.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(); +} diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 0d4e10d..4dafbd4 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -23,7 +23,7 @@ void stress_test(ll range) { MCH mch; for (ll m : ms) { - ll c = Random::integer(-1000, 1000); + ll c = Random::integer(-range, range); mch.add(m, c); naive.emplace_back(m, c); @@ -34,11 +34,6 @@ void stress_test(ll range) { 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++; } -- cgit v1.2.3 From c31dcca8b822a38298c3dd624c3c1c0c23caa57d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 17 Aug 2024 20:30:08 +0200 Subject: improved monotonic onvex hull --- content/datastructures/monotonicConvexHull.cpp | 4 +-- tcr.pdf | Bin 691092 -> 691111 bytes test/datastructures/monotonicConvexHull.cpp | 41 ++++++++++++++++++++----- 3 files changed, 35 insertions(+), 10 deletions(-) (limited to 'content/datastructures/monotonicConvexHull.cpp') diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index e84ad86..f1721ae 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,5 +1,5 @@ // Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue -// Gerade hat kleinere Steigung als alle vorherigen. +// Gerade hat kleineres pair(m, c) als alle vorherigen. struct Line { ll m, c; ll operator()(ll x) {return m*x+c;} @@ -20,7 +20,7 @@ void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert +ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); diff --git a/tcr.pdf b/tcr.pdf index d107dab..199c3de 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 9edfb4b..0415068 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -13,17 +13,30 @@ void stress_test(ll range) { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); - auto ms = Random::distinct(n, -range, range); + auto ms = Random::integers(n, -range, range); sort(all(ms), greater<>{}); - auto xs = Random::distinct(n*100, -range*n, range*n); + auto cs = ms; + for (int l = 0, r = 0; l < n;) { + while (r < n && ms[l] == ms[r]) r++; + auto tmp = Random::distinct(r - l, -range, range); + sort(all(tmp), greater<>{}); + for (int c : tmp) { + cs[l] = c; + l++; + } + } + + auto xs = Random::integers(n*100, -range*n, range*n); sort(all(xs)); int i = 0; vector naive; MCH mch; - for (ll m : ms) { - ll c = Random::integer(-range, range); + for (int k = 0; k < n; k++) { + ll m = ms[k]; + ll c = cs[k]; + mch.add(m, c); naive.emplace_back(m, c); @@ -46,18 +59,30 @@ void stress_test_independent(ll range) { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); - auto ms = Random::distinct(n, -range, range); + auto ms = Random::integers(n, -range, range); sort(all(ms), greater<>{}); + auto cs = ms; + for (int l = 0, r = 0; l < n;) { + while (r < n && ms[l] == ms[r]) r++; + auto tmp = Random::distinct(r - l, -range, range); + sort(all(tmp), greater<>{}); + for (int c : tmp) { + cs[l] = c; + l++; + } + } vector naive; MCH mch; - for (ll m : ms) { - ll c = Random::integer(-range, range); + for (int i = 0; i < n; i++) { + ll m = ms[i]; + ll c = cs[i]; + mch.add(m, c); naive.emplace_back(m, c); - auto xs = Random::distinct(100, -range, range); + auto xs = Random::integers(100, -range, range); sort(all(xs)); auto tmp = mch; -- cgit v1.2.3