1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include "../util.h"
#include <datastructures/treap.cpp>
void add(Treap& t, vector<ll>& ans, int v) {
if (v < 0) return;
add(t, ans, t.treap[v].l);
ans.push_back(t.treap[v].val);
add(t, ans, t.treap[v].r);
}
vector<ll> to_vec(Treap& t) {
vector<ll> ans;
add(t, ans, t.root);
return ans;
}
void stress_test(int T, int n) {
for (int tries = 0; tries < T; tries++) {
int ins = Random::integer<int>(1, n);
int rem = Random::integer<int>(0, ins+1);
vector<ll> a;
Treap t;
while (ins + rem > 0) {
bool is_ins = Random::integer(0, ins+rem) < ins;
if (a.empty()) is_ins = true;
if (is_ins) {
int ind = Random::integer<int>(0, (int)sz(a)+1);
ll val = Random::integer((ll)-1e18, (ll)1e18+1);
t.insert(ind, val);
a.insert(a.begin() + ind, val);
ins--;
} else {
int ind = Random::integer<int>(0, (int)sz(a));
int cnt = Random::integer<int>(1, 1 + min<int>({(int)sz(a)-ind, rem, (int)sqrt(n)}));
t.remove(ind, cnt);
a.erase(a.begin() + ind, a.begin() + ind + cnt);
rem -= cnt;
}
}
if (to_vec(t) != a) cerr << "Failed stress test" << endl;
}
cerr << "Tested " << T << " random tests with n<=" << n << endl;
}
constexpr int N = 200'000;
void performance_test() {
timer t;
t.start();
Treap tr;
t.stop();
hash_t hash = 0;
for (int operations = 0; operations < N; operations++) {
int ind = Random::integer<int>(0, operations+1);
ll val = Random::integer((ll)-1e18, (ll)1e18+1);
t.start();
tr.insert(ind, val);
hash ^= tr.root;
t.stop();
}
while (tr.root != -1) {
t.start();
int sz = tr.getSize(tr.root);
t.stop();
int ind = Random::integer<int>(0, sz);
int cnt = Random::integer<int>(1, 1 + min<int>(sz-ind, 10));
t.start();
tr.remove(ind, cnt);
t.stop();
}
if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
int main() {
stress_test(10000, 10);
stress_test(1000, 100);
stress_test(100, 10000);
performance_test();
}
|
