From ac2d9ad3f2c88bc12420fc439e8d0b4775a11169 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 30 Aug 2024 15:04:20 +0200 Subject: various small improvements --- content/other/pbs.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'content/other/pbs.cpp') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 7cb60e5..5508d6c 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -10,9 +10,8 @@ while (true) { // reset simulation for (int step = 0; auto [mid, i] : focus) { - while (step <= mid) { + for (; step <= mid; step++) { // simulation step - step++; } if (/* requirement already fulfilled */) high[i] = mid; else low[i] = mid + 1; -- cgit v1.2.3 From 1abc08be606b7379bb1b9c5150bf73841a4b9c66 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 30 Aug 2024 16:46:50 +0200 Subject: improve pbs --- content/other/pbs.cpp | 11 ++++++----- tcr.pdf | Bin 691903 -> 691692 bytes 2 files changed, 6 insertions(+), 5 deletions(-) (limited to 'content/other/pbs.cpp') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 5508d6c..6cf872a 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,10 +1,11 @@ // Q = # of queries, bucket sort is sometimes faster -vector low(Q, 0), high(Q, MAX_OPERATIONS); +vector low(Q, 0), high(Q, MAX_OPERATIONS + 1); while (true) { vector> focus; - for (int i = 0; i < Q; i++) if (low[i] < high[i]) { - focus.emplace_back((low[i] + high[i]) / 2, i); - } + for (int i = 0; i < Q; i++) { + if (low[i] + 1 < high[i]) { + focus.emplace_back((low[i] + high[i]) / 2, i); + }} if (focus.empty()) break; sort(all(focus)); @@ -14,5 +15,5 @@ while (true) { // simulation step } if (/* requirement already fulfilled */) high[i] = mid; - else low[i] = mid + 1; + else low[i] = mid; }} // answer in low (and high) diff --git a/tcr.pdf b/tcr.pdf index c6fc0ce..e349ca0 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 77997253fb0978c2f45b73982eb0926756747882 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 6 Sep 2024 18:03:19 +0200 Subject: more tests --- content/other/pbs.cpp | 2 +- test/other/pbs.cpp | 103 +++++++++++++++++++++++++++++++++++++++++++++++++ test/other/pbs.cpp.awk | 8 ++++ test/test.sh | 1 + 4 files changed, 113 insertions(+), 1 deletion(-) create mode 100644 test/other/pbs.cpp create mode 100644 test/other/pbs.cpp.awk (limited to 'content/other/pbs.cpp') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 6cf872a..e6ef07d 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,5 +1,5 @@ // Q = # of queries, bucket sort is sometimes faster -vector low(Q, 0), high(Q, MAX_OPERATIONS + 1); +vector low(Q, -1), high(Q, MAX_OPERATIONS); while (true) { vector> focus; for (int i = 0; i < Q; i++) { diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp new file mode 100644 index 0000000..ba3b9d0 --- /dev/null +++ b/test/other/pbs.cpp @@ -0,0 +1,103 @@ +#include "../util.h" + +struct Union { + vector a; + + Union(int n) : a(n, -1) {} + + int find(int i) { + return a[i] < 0 ? i : a[i] = find(a[i]); + } + + void join(int i, int j) { + i = find(i), j = find(j); + if (i == j) return; + a[j] = i; + } + + bool same(int i, int j) { + return find(i) == find(j); + } +}; + +int n; +Union un(0); +void reset() { + un = Union(n); +} + +vector> edges; +void do_step(int i) { + auto [u, v] = edges[i]; + un.join(u, v); +} + +vector> queries; +bool test(int i) { + auto [u, v] = queries[i]; + return un.same(u, v); +} + +#include +void stress_test() { + for (int it = 0; it < 100'000; it++) { + n = Random::integer(2, 31); + int Q = Random::integer(2, 31); + int MAX_OPERATIONS = n-1; + + edges.clear(); + for (int i=1; i ans = pbs(Q, MAX_OPERATIONS); + + vector correct(Q, -1); + Union un2(n); + for (int j=0; j ans = pbs(Q, MAX_OPERATIONS); + t.stop(); + ll hash = accumulate(all(ans), 0LL); + + if (t.time > 700) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/other/pbs.cpp.awk b/test/other/pbs.cpp.awk new file mode 100644 index 0000000..3084ebd --- /dev/null +++ b/test/other/pbs.cpp.awk @@ -0,0 +1,8 @@ +BEGIN { print "vector pbs(int Q, int MAX_OPERATIONS) {" } +{ + sub(/\/\* requirement already fulfilled \*\//, "test(i)") + sub(/\/\/ simulation step/, "do_step(step);") + sub(/\/\/ reset simulation/, "reset();") +} +{ print } +END { print "return high; }" } diff --git a/test/test.sh b/test/test.sh index 3cb5c9c..e4eecee 100755 --- a/test/test.sh +++ b/test/test.sh @@ -6,6 +6,7 @@ export MALLOC_PERTURB_="$((2#01011001))" declare -A cppstandard cppstandard["string/suffixArray.cpp"]="gnu++20" +cppstandard["other/pbs.cpp"]="gnu++20" seedmacro="" process_awk() { -- cgit v1.2.3 From d4352adae52b2606e5f5db069b2899d444e85e77 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 6 Sep 2024 18:04:58 +0200 Subject: fix comment --- content/other/pbs.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content/other/pbs.cpp') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index e6ef07d..f4db2fd 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -16,4 +16,4 @@ while (true) { } if (/* requirement already fulfilled */) high[i] = mid; else low[i] = mid; -}} // answer in low (and high) +}} // answer in low (MAX_OPERATIONS if never ok) -- cgit v1.2.3