summaryrefslogtreecommitdiff
path: root/content/math/linearSieve.cpp
AgeCommit message (Collapse)Author
2024-07-28Test (#4)mzuenni
* update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? #include "../util.h" #include <datastructures/sparseTableDisjoint.cpp> void stress_test() { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); vector<ll> naive = Ran
jointST st; st.init(naive); for (int operations = 0; operations < 1000; operations++) { queries++; int l = Random::integer<int>(0, n+1); int r = Random::integer<int>(0, n+1); ll got = st.query(l, r); ll expected = 0; for (int j = l; j < r; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } cerr << "tested random queries: " << queries << endl; } constexpr int N = 1'250'000; void performance_test() { timer t; vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); DisjointST st; st.init(naive); t.stop(); hash_t hash = 0; for (int operations = 0; operations < N; operations++) { auto [l, r] = Random::pair<int>(0, N+1); t.start(); hash += st.query(l, r); t.stop(); } if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { stress_test(); performance_test(); }