1#include <iomanip>
2#include <iostream>
3#include <map>
4#include <string>
5
6#include <Common/SpaceSaving.h>
7#include <common/StringRef.h>
8
9int 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