Здравствуйте, на собеседовании задали такую задачку (оптимального ответа как потом признались не знают и сами кто проводил собеседование ), сут такая есть некая функция addValue(int64 nValue), которая вызывается много раз (порядка миллиарда) с различными значениям nValue (тоже неизвестно сколько различных может быть 1 может все ), необходимо предложить способ как можно точнее оценить сколько различных значений nValue было передано.
Я предложил несколько способов использовать дерево количество памяти O(n) от количество различных элементов, Хеш не многим лучше, как вариант битовый массив памяти потребуется меньше чем для дерева как минимум в 64 раза (без учета внутреннего устройства дерева), ну и последнее использовать фильтр Блума, но правда в последнем случае число различных элементов может быть меньше чем в реальности.
Возможно есть еще варианты?

Здравствуйте, Аноним, Вы писали:

А>(оптимального ответа как потом признались не знают и сами кто проводил собеседование )
Так а чем конкретно не подошел вариант запомнить все параметры, тем более, что их всего миллиард? Может у собеседующих были проблемы не с отсутствием оптимального ответа, а с выбором самого критерия оптимальности? :)
А>Возможно есть еще варианты?
Вот если дополнительной использовать можно совсем памяти мало, то семейство алгоритмов типа HyperLogLog есть. По идее способа подсчёта похожи на тот же фильтр Блума, то есть дают также приближенное значение, но точнее чем у фильтра.

Здравствуйте, watchmaker, Вы писали:
W>Вот если дополнительной использовать можно совсем памяти мало, то семейство алгоритмов типа HyperLogLog есть. По идее способа подсчёта похожи на тот же фильтр Блума, то есть дают также приближенное значение, но точнее чем у фильтра.

Ну да в качестве требования использование как можно меньшего количества памяти, ознакомился с HyperLogLog интересный алгоритм, вроде в теории дает ошибку меньше чем у Блума, надо будет сравнить на практике.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, на собеседовании задали такую задачку (оптимального ответа как потом признались не знают и сами кто проводил собеседование ), сут такая есть некая функция addValue(int64 nValue), которая вызывается много раз (порядка миллиарда) с различными значениям nValue (тоже неизвестно сколько различных может быть 1 может все ), необходимо предложить способ как можно точнее оценить сколько различных значений nValue было передано.
А>Я предложил несколько способов использовать дерево количество памяти O(n) от количество различных элементов, Хеш не многим лучше, как вариант битовый массив памяти потребуется меньше чем для дерева как минимум в 64 раза (без учета внутреннего устройства дерева), ну и последнее использовать фильтр Блума, но правда в последнем случае число различных элементов может быть меньше чем в реальности.
А>Возможно есть еще варианты?

Не будучи в курсе, что такое фильтр Блума...

1) Используя хеш-функцию, уменьшаем пространство чисел из M=2^64 до H корзин, таким образом, каждой соответствует D = M/H разных чисел.
2) Заводим H счётчиков и считаем количество попаданий в каждую корзину
3) Вероятное количество (матожидание) уникальных попаданий U в одну корзину в зависимости от общего количества попаданий T в неё — это некая функция: U(D,T)
4) После забега находим сумму U(D,T[k]), k=1..H, а заодно и точность можем сосчитать.

Понятно, что
U(D,0) = 0, — нет попаданий
U(D,1) = 1, — единственное попадание по определению уникально
U(D,oo) = D, — скорее всего, мы хотя бы по разу кинули в корзину все возможные числа

Частный случай для D=1 отражает суть битового флага
U(1,T) = min(1,T)

Разрядность счётчика можно ограничить, т.е. принять, что
U(D,Tmax(D)) = D

Дальше нужно закапываться в теорвер Мне почему-то кажется, что U(D,T) = D*(1-exp(-T/D))
А затем нужно закапываться в оптимизацию и придумывать, как это всё запихать в память.

С одной стороны, нам требуется до 8Гб памяти под массив значений (и O(nlogn) времени).
С другой стороны, — если вектор счётчиков плотный, то, при линейном времени, в эту же память влезет
— или 2^(33+8) битовых счётчиков-флажков, т.е. каждая корзина охватывает D=2^23;
— или 2^33 8-битовых счётчиков, т.е. 2^31 укладывается в 2^8;
— или 2^32 16-битовых, т.е. 2^32 — в 2^16;
— или 2^31 32-битовых, т.е. 2^33 — в 2^32; видимо, есть смысл остановиться именно на этом варианте
Наконец, если вектор разреженный, то при линейнологарифмическом времени, в эту же память влезет
— или миллиард корзин (32-битный номер, 32-битный счётчик) / (48-битный номер, 16-битный счётчик) / (64-битный номер, 0-битный счётчик)
— или 2 миллиарда (16-битный номер, 16-битный счётчик) ... (63-битный номер, 0-битный счётчик)
и т.д.
То есть, мы можем сократить расход памяти, либо выбрать линейное время ценой ещё больших потерь точности.