File: hyperloglog.cc

package info (click to toggle)
mold 2.37.1%2Bdfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: trixie
  • size: 43,640 kB
  • sloc: ansic: 190,908; cpp: 153,224; asm: 29,233; sh: 13,504; python: 4,247; makefile: 3,322; ada: 1,681; pascal: 1,139; xml: 278; objc: 176; javascript: 37
file content (20 lines) | stat: -rw-r--r-- 453 bytes parent folder | download 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
// This file implements HyperLogLog algorithm, which estimates
// the number of unique items in a given multiset.
//
// For more info, read
// https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog

#include "common.h"

#include <cmath>

namespace mold {

i64 HyperLogLog::get_cardinality() const {
  double z = 0;
  for (i64 val : buckets)
    z += std::ldexp(1.0, -val);
  return ALPHA * NBUCKETS * NBUCKETS / z;
}

} // namespace mold