Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
88 lines (81 sloc) 2.54 KB
// hyperloglog.cc
// from "HyperLogLog: the analysis of a near-optimal cardinality estimation
// algorithm," by Flajolet, Fusy, Gandouet, & Meunier
#include <cmath>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>
auto num_zeros(const std::vector<uint32_t>& xs) -> uint32_t {
return std::accumulate(std::begin(xs), std::end(xs), 0,
[](uint32_t x, uint32_t y) -> uint32_t { return x + (y == 0); });
}
auto h(const std::string& s) -> uint32_t {
// FNV-1a
const auto fnv_offset_basis = uint32_t{2166136261};
return std::accumulate(std::begin(s), std::end(s), fnv_offset_basis,
[](uint32_t h, char c) -> uint32_t {
static const auto fnv_prime = uint32_t{1676619};
return fnv_prime * (h ^ c);
});
}
auto rho(uint32_t s) -> uint32_t {
return 32 - static_cast<uint32_t>(log(std::max(s, 1u)));
}
auto alpha(uint32_t m) -> double {
switch(m) {
case 16:
return 0.673;
break;
case 32:
return 0.697;
break;
case 64:
return 0.709;
break;
default:
return 0.7123 / (1 + 1.079 / m);
break;
}
}
auto hyperloglog(std::ifstream& data, uint32_t b) -> double {
auto m = uint32_t{1u << b}, bf32 = uint32_t{32u - b};
auto M = std::vector<uint32_t>(m);
auto v = std::string{""};
while (data.good()) {
data >> v;
auto x = h(v);
auto j = x >> bf32;
auto w = x & ((1u << bf32) - 1);
M[j] = std::max(M[j], rho(w));
}
auto E = alpha(m) * m * m / std::accumulate(std::begin(M), std::end(M), 0,
[](double x, double y) -> double { return x + pow(2, -y); });
auto E_star = E, two32 = pow(2.0, 32);
if (E < 2.5 * m) {
auto V = num_zeros(M);
if (V != 0) {
E_star = m * log(m / static_cast<double>(V));
}
} else if (E > two32 / 30.0) {
E_star = -two32 * log(1.0 - E / two32);
}
return E_star;
}
auto main(int argc, char *argv[]) -> int {
if (argc != 3) {
std::cerr << "usage: " << argv[0] << " <file> <b>" << std::endl;
return EXIT_FAILURE;
} else {
auto b = static_cast<uint32_t>(std::stoi(argv[2]));
if (b > 31) {
std::cerr << b << " too large" << std::endl;
return EXIT_FAILURE;
} else {
std::ifstream data(argv[1]);
std::cout << hyperloglog(data, b) << std::endl;
data.close();
return EXIT_SUCCESS;
}
}
}