code/hyperloglog/hyperloglog_optimized_ut.cpp - master - AMaftuna/Cardinality-Estimation-Algorithm

code/hyperloglog/hyperloglog_optimized_ut.cpp
97 строк3 KB
Abdulloeva Maftuna
02 апр 2025, 15:24
02 апр 2025, 15:24c46503f
#include "hyperloglog_optimized.h"

#include <library/cpp/testing/unittest/registar.h>
#include <util/random/mersenne.h>
#include <cmath>

Y_UNIT_TEST_SUITE(TImprovedHyperLogLogTests) {

    Y_UNIT_TEST(BitPackedRegisters_SetGetEdgeCases) {
        BitPackedRegisters regs(100);
        for (int i = 0; i < 100; ++i) {
            regs.set(i, i % 64);
            UNIT_ASSERT_EQUAL(regs.get(i), i % 64);
        }

        for (int i = 0; i < 100; ++i) {
            regs.set(i, 63);
            UNIT_ASSERT_EQUAL(regs.get(i), 63);
        }

        for (int i = 0; i < 100; ++i) {
            regs.set(i, 0);
            UNIT_ASSERT_EQUAL(regs.get(i), 63);
        }
    }

    Y_UNIT_TEST(BitPackedRegisters_LargeMerge) {
        BitPackedRegisters regs1(1000);
        BitPackedRegisters regs2(1000);

        for (int i = 0; i < 1000; ++i) {
            regs1.set(i, i % 64);
            regs2.set(i, (i + 32) % 64);
        }

        regs1.merge(regs2);

        for (int i = 0; i < 1000; ++i) {
            UNIT_ASSERT_EQUAL(regs1.get(i), std::max(i % 64, (i + 32) % 64));
        }
    }

    Y_UNIT_TEST(ImprovedHyperLogLog_HighPrecisionEstimate) {
        ImprovedHyperLogLog hll(18);
        const int numItems = 1 << 20;

        for (int i = 0; i < numItems; ++i) {
            hll.Add(std::to_string(i));
        }

        double estimation = hll.Estimate();
        double error = std::abs(estimation - numItems) / numItems;

        UNIT_ASSERT(error < 0.005);
    }

    Y_UNIT_TEST(ImprovedHyperLogLog_RandomDataAccuracy) {
        ImprovedHyperLogLog hll(16);
        TMersenne<ui64> rng;

        constexpr ui64 numItems = 500000;
        for (ui64 i = 0; i < numItems; ++i) {
            hll.Add(std::to_string(rng()));
        }

        double estimation = hll.Estimate();
        double error = std::abs(estimation - numItems) / numItems;

        UNIT_ASSERT(error < 0.01);
    }

    Y_UNIT_TEST(ImprovedHyperLogLog_LargeMergeComplex) {
        ImprovedHyperLogLog hll1(14);
        ImprovedHyperLogLog hll2(14);

        for (int i = 0; i < 300000; ++i) {
            hll1.Add("hll1_" + std::to_string(i));
        }

        for (int i = 150000; i < 450000; ++i) {
            hll2.Add("hll2_" + std::to_string(i));
        }

        hll1.Merge(hll2);

        double estimation = hll1.Estimate();
        double error = std::abs(estimation - 450000) / 450000;

        UNIT_ASSERT(error < 0.015);
    }

    Y_UNIT_TEST(ImprovedHyperLogLog_InvalidPrecision) {
        UNIT_ASSERT_EXCEPTION(ImprovedHyperLogLog(-1), std::exception);
        UNIT_ASSERT_EXCEPTION(ImprovedHyperLogLog(0), std::exception);
        UNIT_ASSERT_NO_EXCEPTION(ImprovedHyperLogLog(4));
    }
}