blob: d0a6e7376d681b5b3d31bdb0b3b38e707a1a594f (
plain) (
blame)
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
|
#pragma once
#include <util/system/types.h>
#include <util/stream/input.h>
#include <util/generic/array_ref.h>
#include <vector>
class IOutputStream;
class THyperLogLogBase {
protected:
explicit THyperLogLogBase(unsigned precision);
public:
static const constexpr unsigned PRECISION_MIN = 4;
static const constexpr unsigned PRECISION_MAX = 18;
void Update(ui64 hash);
void Merge(const THyperLogLogBase& rh);
ui64 Estimate() const;
void Save(IOutputStream& out) const;
protected:
unsigned Precision;
TArrayRef<ui8> RegistersRef;
};
template <typename Alloc>
class THyperLogLogWithAlloc : public THyperLogLogBase {
private:
explicit THyperLogLogWithAlloc(unsigned precision)
: THyperLogLogBase(precision) {
Registers.resize(1u << precision);
RegistersRef = MakeArrayRef(Registers);
}
public:
THyperLogLogWithAlloc(THyperLogLogWithAlloc&&) = default;
THyperLogLogWithAlloc& operator=(THyperLogLogWithAlloc&&) = default;
static THyperLogLogWithAlloc Create(unsigned precision) {
return THyperLogLogWithAlloc(precision);
}
static THyperLogLogWithAlloc Load(IInputStream& in) {
char precision = {};
Y_ENSURE(in.ReadChar(precision));
auto res = Create(precision);
in.LoadOrFail(res.Registers.data(), res.Registers.size() * sizeof(res.Registers.front()));
return res;
}
private:
std::vector<ui8, Alloc> Registers;
};
using THyperLogLog = THyperLogLogWithAlloc<std::allocator<ui8>>;
|
