code/hyperloglog/hyperloglog_optimized.h - HLL - AMaftuna/Cardinality-Estimation-Algorithm

code/hyperloglog/hyperloglog_optimized.h
79 строк2 KB
Abdulloeva Maftuna
improved
22 июн 2025, 02:46
22 июн 2025, 02:46f7fca03
#include <vector>
#include <string>
#include <cstdint>
#include <stdexcept>
#include <mutex>
#include <util/stream/output.h>
#include <util/stream/input.h>

uint64_t MurmurHash64A(const void* key, int len, uint64_t seed);

inline uint64_t HashString(const std::string& s, uint64_t seed = 0xadc83b19ULL) {
    return MurmurHash64A(s.data(), static_cast<int>(s.size()), seed);
}

class BitPackedRegisters {
public:
    explicit BitPackedRegisters(int numRegisters);
    uint8_t get(int index) const;
    void set(int index, uint8_t newVal);
    void merge(const BitPackedRegisters& other);
    int getSize() const;
    const std::vector<uint8_t>& RawData() const;
    int ByteSize() const;
    void LoadRaw(const std::vector<uint8_t>& buf);
private:
    int m;
    std::vector<uint8_t> data;
};

class ImprovedHyperLogLog {
public:
    explicit ImprovedHyperLogLog(unsigned precision);

    ImprovedHyperLogLog(const ImprovedHyperLogLog& other);

    ImprovedHyperLogLog& operator=(const ImprovedHyperLogLog& other);

    void Add(const std::string& value);

    double Estimate() const;

    void Merge(const ImprovedHyperLogLog& other);

    unsigned GetPrecision() const;

    void Serialize(IOutputStream& out) const;
    
    static ImprovedHyperLogLog Deserialize(IInputStream& in);

    static double EstimateIntersection(const ImprovedHyperLogLog& a, const ImprovedHyperLogLog& b);

    static double EstimateDifference(const ImprovedHyperLogLog& a, const ImprovedHyperLogLog& b);

    static const constexpr unsigned PRECISION_MIN = 4;

    static const constexpr unsigned PRECISION_MAX = 18;
private:
    unsigned precision_;
    int num_buckets_;
    BitPackedRegisters registers_;

    bool sparseMode_;
    std::vector<std::pair<uint32_t, uint8_t>> sparseRegs_;
    size_t sparseThreshold_;

    mutable std::mutex mtx_;

    uint8_t CountLeadingZeros(uint64_t value) const;

    double GetAlphaConstant(int m) const;

    void AddSparse(uint32_t idx, uint8_t rank);

    void ToDense();

    double EstimateRaw() const;

    double BiasCorrected(double E) const;
};