From 09b844f47c87814e0c825dfcd6cba9ce15e01123 Mon Sep 17 00:00:00 2001 From: MZuenni Date: Thu, 1 Aug 2024 18:04:48 +0200 Subject: add preformance test --- test/graph/connect.cpp | 44 ++++++++++++++++++++++++++++++-------------- 1 file changed, 30 insertions(+), 14 deletions(-) (limited to 'test/graph') diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index 065e21f..bba8104 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -95,27 +95,43 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } -constexpr int N = 2'000'000; +constexpr int N = 100'000; +constexpr int M = 500'000; void performance_test() { - /*timer t; + timer t; t.start(); - UF uf(N); + connect con(N, M); t.stop(); - hash_t hash = 0; - for (int operations = 0; operations < N; operations++) { - int i = Random::integer(0, N); - int j = Random::integer(0, N); - int k = Random::integer(0, N); - int l = Random::integer(0, N); + + vector insertOrder(M); + iota(all(insertOrder), 0); + shuffle(all(insertOrder), Random::rng); + vector inserted(M); + + for (int i = 0, j = 0; i < N; i++) { + int a = Random::integer(0, N); + int b = a; + while (b == a) b = Random::integer(0, N); t.start(); - uf.unionSets(i, j); - hash += uf.size(k); - hash += uf.size(l); + con.addEdge(a, b, insertOrder[i]); + t.stop(); + inserted[i] = true; + + while (j < M && inserted[j] && Random::integer(2) == 0) { + t.start(); + con.eraseEdge(j); + t.stop(); + } + } + hash_t hash = 0; + for (int i = 1; i < N; i++) { + t.start(); + hash += con.connected(i - 1, i); t.stop(); } - if (t.time > 500) 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() { -- cgit v1.2.3