library/cpp/hyperloglog/hyperloglog.h


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>>;