HyperLogLog Cardinality

Counting exact distinct items over a high-volume stream (unique symbols seen, unique order comments, unique client IDs in a log) normally means keeping every item seen so far in a set - memory grows with the true distinct count. HyperLogLog trades exactness for a fixed, small memory footprint: this implementation keeps m single- byte registers (m = 2^p, p configurable), hashes each item, routes it to one register by the top p bits of the hash, and keeps the longest run of leading zero bits seen in that register's remaining bits. Longer runs are exponentially rarer, so the longest run seen across many distinct items is a genuine statistical signal of how many distinct items there must have been - that is the actual HyperLogLog algorithm, not an approximation of it. Adding the same item again can only ever leave its register the same (a repeat produces the identical hash and therefore the identical leading-zero run) - duplicates never inflate the estimate, which the demo proves directly by adding every item three times and comparing against adding it once. Merge() unions two estimators of equal precision by taking the elementwise maximum of their registers - a real, lossless HyperLogLog union, exactly as accurate as building one estimator from both streams' items from the start. The demo splits a known item set into two disjoint estimators and shows the merged estimate lands close to the true combined count. MQL4 has no built-in general-purpose hash function, so this reimplements a 32-bit FNV-1a hash inline. It is the same well-known non-cryptographic checksum used elsewhere in this catalogue by ManifestIntegrityVerifier.mqh, reimplemented independently here per house style (no cross-project #include). Notes and limitations - This is a genuine statistical estimator, not an exact count - expect typical relative error around 1.04/sqrt(m), with occasional runs further off; it is not suitable where an exact count is required. - Items are hashed as strings via StringToCharArray() + FNV-1a; two different items that happen to hash to the same 32-bit value are indistinguishable to this structure (an inherent hash-based cardinality estimator limitation, not specific to this implementation). - Merge() requires both estimators to share the same precision (register count); it returns false and does nothing if they differ. - Very small true counts (a handful of items) are handled by the standard small-range linear-counting correction, not the raw harmonic-mean formula alone, to avoid the well-known HyperLogLog small-cardinality bias.

Script · MT4 · v1.0 · Free

Tags: Volume · MT4 Script · MQL4 Source Code

MQL4 & MQL5 scripts · PolyMaria