HyperLogLog.cs

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;

namespaceDataStructures.Probabilistic;

publicclassHyperLogLog<T>whereT:notnull
{
privateconstintP=16;
privateconstdoubleAlpha=.673;
privatereadonlyint[]registers;
privatereadonlyHashSet<int>setRegisters;

/// <summary>
/// Initializes a new instance of the <see cref="HyperLogLog{T}"/> class.
/// </summary>
publicHyperLogLog()
{
varm=1<<P;
registers=newint[m];
setRegisters=newHashSet<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>
publicstaticHyperLogLog<T>Merge(HyperLogLog<T>first,HyperLogLog<T>second)
{
varoutput=newHyperLogLog<T>();
for(vari=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);
returnoutput;
}

/// <summary>
/// Adds an item to the HyperLogLog.
/// </summary>
/// <param name="item">The Item to be added.</param>
publicvoidAdd(Titem)
{
varx=item.GetHashCode();
varbinString=Convert.ToString(x,2);// converts hash to binary
varj=Convert.ToInt32(binString.Substring(0,Math.Min(P,binString.Length)),2);// convert first b bits to register index
varw=(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>
publicintCardinality()
{
// calculate the bottom part of the harmonic mean of the registers
doublez=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));
}
}