-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
35 lines (30 loc) · 968 Bytes
/
main.cpp
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
#include <iostream>
#include <random>
#include <set>
#include <cassert>
#include "UniqCounter.h"
double relative_error(int expected, int got) {
return abs(got - expected) / (double) expected;
}
int main() {
std::random_device rd;
std::mt19937 gen(rd());
const int N = (int) 1e6;
for (int k : {1, 10, 1000, 10000, N / 10, N, N * 10}) {
std::uniform_int_distribution<> dis(1, k);
std::set<int> all;
UniqCounter counter;
for (int i = 0; i < N; i++) {
int value = dis(gen);
all.insert(value);
counter.add(value);
}
int expected = (int) all.size();
int counter_result = counter.get_uniq_num();
double error = relative_error(expected, counter_result);
printf("%d numbers in range [1 .. %d], %d uniq, %d result, %.5f relative error\n", N, k, expected,
counter_result, error);
assert(error <= 0.1);
}
return 0;
}