1 | #include <iomanip> |
---|---|
2 | #include <iostream> |
3 | #include <map> |
4 | #include <string> |
5 | |
6 | #include <Common/SpaceSaving.h> |
7 | #include <common/StringRef.h> |
8 | |
9 | int main(int, char **) |
10 | { |
11 | { |
12 | using Cont = DB::SpaceSaving<int>; |
13 | Cont first(10); |
14 | |
15 | /* Test biased insertion */ |
16 | |
17 | for (int i = 0; i < 200; ++i) |
18 | { |
19 | first.insert(i); |
20 | int k = i % 5; // Bias towards 0-4 |
21 | first.insert(k); |
22 | } |
23 | |
24 | /* Test whether the biased elements are retained */ |
25 | |
26 | std::map<int, UInt64> expect; |
27 | for (int i = 0; i < 5; ++i) |
28 | { |
29 | expect[i] = 41; |
30 | } |
31 | |
32 | for (auto x : first.topK(5)) |
33 | { |
34 | if (expect[x.key] != x.count) |
35 | { |
36 | std::cerr << "key: "<< x.key << " value: "<< x.count << " expected: "<< expect[x.key] << std::endl; |
37 | } |
38 | else |
39 | { |
40 | std::cout << "key: "<< x.key << " value: "<< x.count << std::endl; |
41 | } |
42 | expect.erase(x.key); |
43 | } |
44 | |
45 | if (!expect.empty()) |
46 | { |
47 | std::cerr << "expected to find all heavy hitters"<< std::endl; |
48 | } |
49 | |
50 | /* Create another table and test merging */ |
51 | |
52 | Cont second(10); |
53 | for (int i = 0; i < 200; ++i) |
54 | { |
55 | first.insert(i); |
56 | } |
57 | |
58 | for (int i = 0; i < 5; ++i) |
59 | { |
60 | expect[i] = 42; |
61 | } |
62 | |
63 | first.merge(second); |
64 | |
65 | for (auto x : first.topK(5)) |
66 | { |
67 | if (expect[x.key] != x.count) |
68 | { |
69 | std::cerr << "key: "<< x.key << " value: "<< x.count << " expected: "<< expect[x.key] << std::endl; |
70 | } |
71 | else |
72 | { |
73 | std::cout << "key: "<< x.key << " value: "<< x.count << std::endl; |
74 | } |
75 | expect.erase(x.key); |
76 | } |
77 | } |
78 | |
79 | { |
80 | /* Same test for string keys */ |
81 | |
82 | using Cont = DB::SpaceSaving<StringRef, StringRefHash>; |
83 | Cont cont(10); |
84 | |
85 | for (int i = 0; i < 400; ++i) |
86 | { |
87 | cont.insert(std::to_string(i)); |
88 | cont.insert(std::to_string(i % 5)); // Bias towards 0-4 |
89 | } |
90 | |
91 | // The hashing is going to be more lossy |
92 | // Expect at least ~ 10% count |
93 | std::map<std::string, UInt64> expect; |
94 | for (int i = 0; i < 5; ++i) |
95 | { |
96 | expect[std::to_string(i)] = 38; |
97 | } |
98 | |
99 | for (auto x : cont.topK(5)) |
100 | { |
101 | auto key = x.key.toString(); |
102 | if (x.count < expect[key]) |
103 | { |
104 | std::cerr << "key: "<< key << " value: "<< x.count << " expected: "<< expect[key] << std::endl; |
105 | } |
106 | else |
107 | { |
108 | std::cout << "key: "<< key << " value: "<< x.count << std::endl; |
109 | } |
110 | expect.erase(key); |
111 | } |
112 | |
113 | if (!expect.empty()) |
114 | { |
115 | std::cerr << "expected to find all heavy hitters"<< std::endl; |
116 | abort(); |
117 | } |
118 | } |
119 | |
120 | return 0; |
121 | } |
122 |