Add HyperLogLog (TheAlgorithms#269)

slorello89 · web-flow · commit 81ec27451b33 · 2021-10-27T21:48:29.000+03:00
diff --git a/DataStructures.Tests/Probabilistic/HyperLogLogTest.cs b/DataStructures.Tests/Probabilistic/HyperLogLogTest.cs
@@ -0,0 +1,61 @@
+﻿using System;
+using System.Collections.Generic;
+using DataStructures.Probabilistic;
+using FluentAssertions;
+using NUnit.Framework;
+
+namespace DataStructures.Tests.Probabilistic
+{
+    public class HyperLogLogTest
+    {
+        [Test]
+        public void TestHyperLogLog()
+        {
+            var hll = new HyperLogLog<int>();
+            HashSet<int> actual = new ();
+
+            var rand = new Random();
+            var tolerance = .05;
+            for (var i = 0; i < 10000; i++)
+            {
+                var k = rand.Next(20000);
+                hll.Add(k);
+                actual.Add(k);
+            }
+
+            hll.Cardinality().Should()
+                .BeGreaterOrEqualTo((int)(actual.Count * (1 - tolerance)))
+                .And
+                .BeLessOrEqualTo((int)(actual.Count * (1 + tolerance)));
+        }
+
+        [Test]
+        public void TestHyperLogLogMerge()
+        {
+            var hll1 = new HyperLogLog<int>();
+            var hll2 = new HyperLogLog<int>();
+            var rand = new Random();
+            var tolerance = .05;
+            HashSet<int> actual = new ();
+            for (var i = 0; i < 5000; i++)
+            {
+                var k = rand.Next(20000);
+                hll1.Add(k);
+                actual.Add(k);
+            }
+
+            for (var i = 0; i < 5000; i++)
+            {
+                var k = rand.Next(20000);
+                hll2.Add(k);
+                actual.Add(k);
+            }
+
+            var hll = HyperLogLog<int>.Merge(hll1, hll2);
+            hll.Cardinality().Should()
+                .BeGreaterOrEqualTo((int)(actual.Count * (1 - tolerance)))
+                .And
+                .BeLessOrEqualTo((int)(actual.Count * (1 + tolerance)));
+        }
+    }
+}
diff --git a/DataStructures/Probabilistic/HyperLogLog.cs b/DataStructures/Probabilistic/HyperLogLog.cs
@@ -0,0 +1,70 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace DataStructures.Probabilistic
+{
+    public class HyperLogLog<T> where T : notnull
+    {
+        private const int P = 16;
+        private const double Alpha = .673;
+        private readonly int[] registers;
+        private readonly HashSet<int> setRegisters;
+
+        /// <summary>
+        /// Initializes a new instance of the <see cref="HyperLogLog{T}"/> class.
+        /// </summary>
+        public HyperLogLog()
+        {
+            var m = 1 << P;
+            registers = new int[m];
+            setRegisters = new HashSet<int>();
+        }
+
+        /// <summary>
+        /// Merge's two HyperLogLog's together to form a union HLL.
+        /// </summary>
+        /// <param name="first">the first HLL.</param>
+        /// <param name="second">The second HLL.</param>
+        /// <returns>A HyperLogLog with the combined values of the two sets of registers.</returns>
+        public static HyperLogLog<T> Merge(HyperLogLog<T> first, HyperLogLog<T> second)
+        {
+            var output = new HyperLogLog<T>();
+            for (var i = 0; i < second.registers.Length; i++)
+            {
+                output.registers[i] = Math.Max(first.registers[i], second.registers[i]);
+            }
+
+            output.setRegisters.UnionWith(first.setRegisters);
+            output.setRegisters.UnionWith(second.setRegisters);
+            return output;
+        }
+
+        /// <summary>
+        /// Adds an item to the HyperLogLog.
+        /// </summary>
+        /// <param name="item">The Item to be added.</param>
+        public void Add(T item)
+        {
+            var x = item.GetHashCode();
+            var binString = Convert.ToString(x, 2); // converts hash to binary
+            var j = Convert.ToInt32(binString.Substring(0, Math.Min(P, binString.Length)), 2); // convert first b bits to register index
+            var w = (int)Math.Log2(x ^ (x & (x - 1))); // find position of the right most 1.
+            registers[j] = Math.Max(registers[j], w); // set the appropriate register to the appropriate value.
+            setRegisters.Add(j);
+        }
+
+        /// <summary>
+        /// Determines the approximate cardinality of the HyperLogLog.
+        /// </summary>
+        /// <returns>the approximate cardinality.</returns>
+        public int Cardinality()
+        {
+            // calculate the bottom part of the harmonic mean of the registers
+            double z = setRegisters.Sum(index => Math.Pow(2, -1 * registers[index]));
+
+            // calculate the harmonic mean of the set registers
+            return (int)Math.Ceiling(Alpha * setRegisters.Count * (setRegisters.Count / z));
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -141,6 +141,7 @@ This repository contains algorithms and data structures implemented in C# for ed
   * [Probabilistic](./DataStructures/Probabilistic)
     * [BloomFilter](./DataStructures/Probabilistic/BloomFilter.cs)
     * [Count-Min Sketch](./DataStructures/Probabilistic/CountMinSketch.cs)
+    * [HyperLogLog](./DataStructures/Probabilistic/HyperLogLog.cs)
   * [Queue](./DataStructures/Queue)
     * [Array-based Queue](./DataStructures/Queue/ArrayBasedQueue.cs)
     * [List-based Queue](./DataStructures/Queue/ListBasedQueue.cs)
