Эта проблема немного похожа на проблему, решаемую reservoir sampling, но не то же самое. Я думаю, что это тоже довольно интересная проблема.Эффективная оценка количества уникальных элементов в большом списке
У меня есть большой набор данных (обычно сотни миллионов элементов), и я хочу оценить количество уникальных элементов в этом наборе данных. Там может быть от нескольких, до миллионов уникальных элементов в типичном наборе данных.
Конечно, очевидное решение состоит в том, чтобы поддерживать бегущий хэш элементов, с которыми вы сталкиваетесь, и подсчитывать их в конце, это даст точный результат, но потребует от меня переноса потенциально большого количества состояний со мной как Я просматриваю набор данных (т. Е. Все уникальные элементы, встречающиеся до сих пор).
К сожалению, в моей ситуации для этого потребуется больше оперативной памяти, чем доступно для меня (ничего, что набор данных может быть намного больше, чем доступная оперативная память).
Мне интересно, будет ли статистический подход к этому, который позволил бы мне сделать один проход через набор данных и придумать подсчет уникальных элементов в конце, сохраняя при этом относительно небольшое количество состояний пока я сканирую набор данных.
Вклад в алгоритм будет набором данных (Iterator в языке Java), и он вернет оцененный уникальный счет объекта (возможно, число с плавающей запятой). Предполагается, что эти объекты могут быть хэшированы (т. Е. Вы можете поместить их в HashSet, если хотите). Обычно это строки или числа.
А, хорошая идея. Я немного пинаю себя за то, что не думаю об этом сам, поскольку я уже очень хорошо знаком с фильтрами Блума. – sanity
Я думал о фильме Блума, но я думаю, вы должны быть осторожны. Если вы найдете что-то, что соответствует фильтру, это означает, что вы, возможно, видели его, или вы, возможно, получили ложный результат. Если он не соответствует фильтру, то вы определенно не видели его раньше. Проблема в том, что чем больше элементов у вас есть, тем больше вероятность ложного позитива, что фактически уменьшит ваш счет. Я не проработал это подробно, но я был бы обеспокоен тем, что вы можете увидеть некоторые нечетные эффекты, используя фильтр Bloom для этой проблемы. –
Брайан, я думал, что вместо увеличения моего счета на 1.0 каждый раз, когда я вижу элемент, который, как я думаю, новый, я увеличиваю его на 1.0-P, где P - вероятность ложного положительного (который можно легко вычислить). – sanity