/count-distinct-problem

Primary LanguageC++

count-distinct-problem

Необходимо написать алгоритм, который приблизительно подсчитывает количество различных чисел в массиве, используя константный объём памяти.

Более формально, надо реализовать класс с двумя функциями:

  • void add(int x); — добавить число x к набору;
  • int get_uniq_num(); — возвращает приблизительное количество различных чисел, которые были переданы в функцию add.

Ваш класс должен использовать не более 32 Кб памяти.

Идею алгоритма можно придумать самому или найти в интернете (при этом оставить ссылку на источник). Весь код должен быть написан вами.

Для проверки базовой функциональности вашего решения можете использовать следующий тест: https://pastebin.com/ZZjg1MzV

Описание алгоритма

Для подсчета приблизительного количества различных чисел использован алгоритм Probabilistic Counting, найденный мной на StackOverFlow. В качестве хэш-функции выбрана FNV-1a, только с константами для 32-битного целочисленного типа из статьи по ссылке.

Альтернативы

  1. Count-min sketch. Судя по статье из Википедии данный алгоритм предполагает, что частоты различных типов не могут уменьшаться со временем, то есть является решением лишь для частного случая.
  2. Алгоритм LogLog. Данный алгоритм, судя по комментарию на StackOverFlow, требует больше памяти и имеет относительно большую погрешность ошибки.
  3. Алгоритм HyperLogLog. Этот алгоритм хоть и использует меньше памяти, его погрешность ошибки все же больше, чем у приведенного алгоритма.