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