Описание реализованных методов

Исходя из описания алгоритма HyperLogLog его имплементация не должна представлять особых проблем. Ниже представлено переложение алгоритма HyperLogLog на C#.

• Конструктор public HyperLogLog(int k) принимает параметр k=4..16 такое, что \( m={ 2 }^{ k } \) - число байтовых регистров, которое будет выделено в оперативной памяти для приблизительного подсчета числа уникальных элементов лежащего в интервале \( \left[ 0,10^9 \right] \). При этом стандартная ошибка при оценке числа уникальных элементов будет составлять \( \frac { 1.04 }{ \sqrt { { 2 }^{ k } } } \).
• Метод public void Add(int hash) принимает 32-битный хеш элемента из набора, в котором нужно оценить число уникальных элементов. В главе о хешировании можно прочесть слова Дональда Кнута, который говорит, что на практике возможно создать хеш-функцию, которая бы из неслучайных данных создавала данные хоть и не совсем случайные, но очень похожие на случайные. Этому стоит уделить особое внимание, потому что недостаточно хорошая хеш-функция, которая будет генерировать хеши не похожие на случайные, сведет весь алгоритм на нет. В реализации метода можно можно увидеть, что после получения индекса регистра из хеша (по первым k битам) далее ведется подсчет младших нулевых битов, а не старших, как это описано в алгоритме. На самом деле совершенно нет разницы, считаем мы последовательность нулевых битов в старших битах или в младших, ведь хеш - это как бы случайное число.
• Метод public double EstimateCount() позволяет произвести оценку числа уникальных элементов, хеши которых были ранее добавлены через вызов метода public void Add(int hash).
• Наконец метод public void UnionWith(HyperLogLog other) позволяет объединить уникальные элементы из разных наборов. Это может быть полезно, если, например, исходная выборка была разбита на несколько частей и для каждой части независимо производилась оценка числа уникальных элементов. Очень важно помнить, что объединяемые объекты класса HyperLogLog должны использовать то же самое число регистров (параметр k должен быть одним и тем же) и для добавляемых элементов должна использоваться одна и та же хеш-функция. Нельзя использовать для двух разных объектов класса HyperLogLog две разные пусть и очень хорошие хеш-функции, т.к. в результате в лучшем случае получится сумма уникальных элементов из каждого набора по отдельности, в худшем случае просто чепуха.

Проверяем правильность работы алгоритма на случайных данных

Прежде чем пробовать алгоритм на каких-то реальных данных, проверим, насколько хорошо он работает на случайных. То есть вместо хешей будем подавать случайные хеши (предполагая, что коллизий будет мало) и проверять на сколько алгоритм ошибается в оценке.

Для проверки возьмем криптографический генератор случайных чисел, не будем полагаться на простой random. Напишем такой генератор бесконечного списка случайных 32-битных чисел:

IEnumerable<int> GetRandomInts()
{
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var intBytes = new byte[4];
    
    while(true)
    {
        rng.GetBytes(intBytes);
        var rndInt = BitConverter.ToInt32(intBytes, 0);     
        yield return rndInt;
    }
}

Прогоним теперь через объект класса HyperLogLog наши случайные числа и в определенных точках сверим оценку с числом поданых случайных чисел:

// здесь будут точки, в которых будем производить оценку
var ticks = new HashSet<int>(Enumerable
    .Range(1, 8)
    .Select(i => (int)Math.Pow(10,i))
    .SelectMany(i => new[]{i, 5*i}));
    
var hll = new HyperLogLog(10); // k = 10
var cnt = 0;                   // число добавленных хешей

Console.WriteLine("| Разных значений | Оценка     | Ошибка,% |");
Console.WriteLine("|----------------:|-----------:|:--------:|");
foreach (var hash in GetRandomInts().Take(100000000))
{
    hll.Add(hash); // добавляем хеш
    cnt++;         // увеличиваем число добавленных хешей
    
    if (!ticks.Contains(cnt)) { continue; }
    // производим оценку и вычисляем ошибку
    var estimateCount = hll.EstimateCount();
    Console.WriteLine("|{0,17}|{1,12:0.00}|{2,10:0.0000}|", cnt, estimateCount, Math.Abs(cnt - estimateCount)/cnt*100.0);
}

При k=10 получается такая таблица (стандартная ошибка \( \frac { 1.04 }{ \sqrt { { 2 }^{ 10 } } } = 3.25\)%):

При k=16 получается такая таблица (стандартная ошибка \( \frac { 1.04 }{ \sqrt { { 2 }^{ 16 } } } = 0.40625\)%):

Как видим ошибки оценок довольно неплохо укладываются в теорию. Теперь можно взять какой-нибудь набор данных и выбрать хеш-функцию для него.

Выбираем функцию хеширования

Как выше было сказано в описании, выбору хеш-функции следует уделить особое внимание по нескольким причинам:

1. Если хеш-функция выдает не достаточно случайные хеши для начальных данных, вычисленная оценка будет скорее всего очень сильно занижать реальное значение так, что погрешность может достигать почти 100% делая вычисления бессмысленными.
2. Если статистика собирается на длительном промежутке времени, нельзя будет на ходу просто поменять хеш-функцию на другую более хорошую, т.к. иначе уже собранную статистику придется сбросить в ноль.

Для начала опробуем хеш-функцию FNV-1a на 32-битных целых числах.

static int Fnv1AHash(byte[] bytes)
{
    unchecked
    {
        const int fnv32Offset = (int)2166136261;
        const int fnv32Prime = 16777619;
        int hash = fnv32Offset;

        foreach (var t in bytes)
        {
            hash = hash ^ t;
            hash *= fnv32Prime;

        }
        return hash;
    }
}

Тепер для чисел целых 32-битных чисел начиная с 0 применим эту хеш-функцию. В коде, который мы применяли для тестирования алгоритма на случайных числах заменим строку:

foreach (var hash in GetRandomInts().Take(100000000))

на

foreach (var hash in Enumerable
                        .Range(0, 100000000)           // все целые числа, начиная с нуля в количестве 100000000
                        .Select(BitConverter.GetBytes) // конвертируем в массив из 4-х байтов
                        .Select(Fnv1AHash))            // применим к каждому массиву хеш-функцию

При k=10 получим такие результаты:

Как видим, хеш-функция для наших входных данных (последовательности целых чисел начиная с нуля) не достаточно хороша, т.к. ошибка очень большая получается. Что можно сделать? Можно попробовать сделать два раунда хеширования - сначала хешируем входные данные, затем хешируем полученный хеш:

foreach (var hash in Enumerable
                        .Range(0, 100000000)           // все целые числа, начиная с нуля в количестве 100000000
                        .Select(BitConverter.GetBytes) // конвертируем в массив из 4-х байтов
                        .Select(Fnv1AHash)             // применим к каждому массиву хеш-функцию
                        .Select(BitConverter.GetBytes) // конвертируем каждый хеш в массив из 4-х байтов
                        .Select(Fnv1AHash))            // применим к каждому массиву снова хеш-функцию

Теперь при k=10 результаты заметно улучшились:

Многие эксперименты показывают, что MurmurHash3 хоть и не является криптографически-безопасной хеш-функцией, но обладает хорошим распределением, обладает высокой скоростью и устойчивостью к коллизиям. За основу была взята эта реализация и немного допилена напильником.

После замены

foreach (var hash in Enumerable
                        .Range(0, 100000000)           // все целые числа, начиная с нуля в количестве 100000000
                        .Select(BitConverter.GetBytes) // конвертируем в массив из 4-х байтов
                        .Select(MurMurHash3.Hash))     // применим к каждому массиву хеш-функцию

были полученные такие результаты при k=10:

При k=16:

Таким образом MurmurHash3 оказалась действительно неплохой хеш-функцией в нашем случае.

Объединяем результаты

Теперь наглядно убедимся, что можно объединять результаты оценки уникальных элементов. Для этого возьмем числа из интервала [0, 9999] произведем оценку числа уникальных элементов на этом интервале, затем то же самое отдельно сделаем для интервала [5000, 14999], после чего объединим результаты. Т.е. в итоге у нас должно получиться порядка 15000 уникальных элементов:

var hll1 = new HyperLogLog(10);
var hll2 = new HyperLogLog(10); 

foreach (var hash in Enumerable
                    .Range(0, 10000)                // все целые числа, начиная с нуля в количестве 10000
                    .Select(BitConverter.GetBytes) // конвертируем в массив из 4-х байтов
                    .Select(MurMurHash3.Hash))     // применим к каждому массиву хеш-функцию                        
{
    hll1.Add(hash);     
}

foreach (var hash in Enumerable
                    .Range(5000, 10000)            // все целые числа, начиная с 5000 в количестве 10000
                    .Select(BitConverter.GetBytes) // конвертируем в массив из 4-х байтов
                    .Select(MurMurHash3.Hash))     // применим к каждому массиву хеш-функцию                        
{
    hll2.Add(hash);     
}

Console.WriteLine("Уникальных элементов на интервале 0-9999: {0:0.00}", hll1.EstimateCount());
Console.WriteLine("Уникальных элементов на интервале 5000-14999: {0:0.00}", hll2.EstimateCount());

hll1.UnionWith(hll2); // в hll1 будет объединение всех уникальных элементов
Console.WriteLine("Уникальных элементов на интервале 0-14999: {0:0.00}", hll1.EstimateCount());

В результате получаем:

Уникальных элементов на интервале 0-9999: 9625,14
Уникальных элементов на интервале 5000-14999: 10013,74
Уникальных элементов на интервале 0-14999: 15139,33

Что нисколько не отличается, если бы мы произвели измерения на одном объекте:

var hll = new HyperLogLog(10);

foreach (var hash in Enumerable
                    .Range(0, 15000)               // все целые числа, начиная с нуля в количестве 15000
                    .Select(BitConverter.GetBytes) // конвертируем в массив из 4-х байтов
                    .Select(MurMurHash3.Hash))     // применим к каждому массиву хеш-функцию                        
{
    hll.Add(hash);      
}

Console.WriteLine("Уникальных элементов на интервале 0-14999: {0:0.00}", hll.EstimateCount());

И в этом случае получили абсолютно тот же самый результат:

Уникальных элементов на интервале 0-14999: 15139,33

Это не должно нас удивлять, т.к. хеши одинаковых элементов совпадают до бита, и попадают в одни и те же регистры, а максимум последовательности нулей в хешах можно искать в произвольном порядке и в результате получим одно и то же число. Это все равно что искать максимальное число в массиве - можно поделить его на несколько частей, параллельно там найти максимумы, а потом среди максимумов найти один единственный максимум. То же самое происходит в нашем случае на уровне отдельных регистров.

Имплементация хеш-функции MurmurHash3 на C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

public static class MurMurHash3
{
    const uint seed = 0;
 
    public static int Hash(byte[] bytes)
    {
        unchecked
        {
            const uint c1 = 0xcc9e2d51;
            const uint c2 = 0x1b873593;
    
            uint h1 = seed;
            uint k1 = 0;        
    
            for (int i = 0; i < bytes.Length; i = i + 4)
            {
                var chunkLength = bytes.Length - i;
                switch(chunkLength)
                {
                    case 4:
                        k1 = (uint)(bytes[i] | bytes[i + 1] << 8 | bytes[i + 2] << 16 | bytes[i + 3] << 24);
    
                        k1 *= c1;
                        k1 = rotl32(k1, 15);
                        k1 *= c2;
    
                        h1 ^= k1;
                        h1 = rotl32(h1, 13);
                        h1 = h1 * 5 + 0xe6546b64;
                        break;
                    case 3:
                        k1 = (uint)(bytes[i] | bytes[i + 1] << 8 | bytes[i + 2] << 16);
                        k1 *= c1;
                        k1 = rotl32(k1, 15);
                        k1 *= c2;
                        h1 ^= k1;
                        break;
                    case 2:
                        k1 = (uint) (bytes[i] | bytes[i + 1] << 8);
                        k1 *= c1;
                        k1 = rotl32(k1, 15);
                        k1 *= c2;
                        h1 ^= k1;
                        break;
                    case 1:
                        k1 = (uint)(bytes[i]);
                        k1 *= c1;
                        k1 = rotl32(k1, 15);
                        k1 *= c2;
                        h1 ^= k1;
                        break;              
                }           
            }
                    
            h1 ^= (uint)bytes.Length;
            h1 = finalizer32(h1);
    
            return (int)h1;         
        }
    }
    
    private static uint rotl32(uint x, byte r)
    {
        return (x << r) | (x >> (32 - r));
    }
 
    private static uint finalizer32(uint h)
    {
        unchecked
        {
            h ^= h >> 16;
            h *= 0x85ebca6b;
            h ^= h >> 13;
            h *= 0xc2b2ae35;
            h ^= h >> 16;
            return h;           
        }
    }
}

Имплементация алгоритма HyperLogLog на C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

public sealed class HyperLogLog
{
    const double TwoPowOf32 = 0x100000000;

    private readonly int _kComplement;
    private readonly int _m;
    private readonly double _alphaM2;
    private readonly byte[] _registerM;

    public HyperLogLog(int k)
    {
        if (k < 4 || k > 16)
        {
            throw new ArgumentOutOfRangeException("k", k, "k must be between 4 and 16 inclusive");
        }

        _kComplement = 32 - k;
        _m = 1 << k;
        var alphaM = _m == 16
            ? 0.673
            : _m == 32
                ? 0.697
                : _m == 64
                    ? 0.709
                    : 0.7213/(1.0 + 1.079/_m);
        _alphaM2 = alphaM * _m * _m;
        _registerM = new byte[_m];
    }

    public void Add(int hash)
    {
        var idx = (uint) hash >> _kComplement;
        var rank = Math.Min(_kComplement, CountTrailingZeroBits(hash)) + 1;
        _registerM[idx] = (byte) Math.Max(_registerM[idx], rank);
    }

    public double EstimateCount()
    {
        double c = 0.0;
        for (int i = 0; i < _m; i++)
        {
            c += 1.0 / Math.Pow(2, _registerM[i]);
        }

        double estimate = _alphaM2 / c;

        if (estimate <= (2.5 * _m))
        {
            int v = 0;
            for (int i = 0; i < _m; i++)
            {
                if (_registerM[i] == 0) { v++; }
            }

            if (v > 0)
            {
                estimate = _m * Math.Log((double)_m / v);
            }
        }
        else if (estimate > (TwoPowOf32 / 30.0))
        {
            estimate = -TwoPowOf32 * Math.Log(1.0 - (estimate / TwoPowOf32));
        }

        return estimate;
    }

    public void UnionWith(HyperLogLog other)
    {
        if (other == null)
        {
            throw new ArgumentNullException("other");
        }

        if (other._m != _m)
        {
            throw new InvalidOperationException("The number of counters must be the same.");
        }

        if (other == this)
        {
            return;
        }

        for (int i = 0; i < _m; i++)
        {
            _registerM[i] = Math.Max(_registerM[i], other._registerM[i]);
        }
    }

    private static int CountTrailingZeroBits(int v)
    {
        if ((v & 0x1) == 1) { return 0; }
        
        int c = 1;
        if ((v & 0xffff) == 0) { v >>= 16; c += 16; }
        if ((v & 0xff) == 0) { v >>= 8; c += 8; }
        if ((v & 0xf) == 0) { v >>= 4; c += 4; }
        if ((v & 0x3) == 0) { v >>= 2; c += 2; }
        c -= v & 0x1;
        return c;
    }
}