Для использования линейного счетчика необходимо заранее знать приблизительное количество уникальных элементов в потоке. На основании этого количества, а также необходимого вам уровня точности, вычисляется длина битовой маски счетчика.
Допустим, вы хотите создать линейный счетчик для оценки количества элементов в потоке, с максимальным количеством уникальных элементов равным 10 миллионам. Какой длины должна быть битовая маска? Ответ на этот вопрос позволяет найти следующее неравенство:
$$m > \max\left(5, \frac{1}{(\epsilon t)^2}\right) \left(e^t - t - 1\right)$$
Минимальное положительное целое m, для которого выполняется это неравенство, является длиной маски при которой обеспечивается необходимая точность.
В этой формуле:
- $m$ — длина битовой маски;
- $\epsilon$ — необходимая точность оценки в виде доли (например, 0.01 для точности 1%);
- $t$ — так называемый, load factor ($t=\frac{n}{m}$). Отношение количества уникальных элементов в потоке к длине битовой маски.
К сожалению, у этого неравенства нет алгебраического решения, – из него нельзя выразить m. Для прикладного применения ответ можно получить несколькими способами.
Таблицы Link to heading
В оригинальной публикации приведены таблицы для точности 1 и 10%. Приведу здесь часть таблицы для полноты повествования.
| n | 1% | 10% |
|---|---|---|
| $10^2$ | 5034 | 80 |
| $10^3$ | 5329 | 268 |
| $10^4$ | 7960 | 1709 |
| $10^5$ | 26729 | 12744 |
| $10^6$ | 154171 | 100880 |
| $10^7$ | 1096582 | 831809 |
Если вам нужна оценка для точности 1 или 10%, её можно узнать интерполяцией двух промежуточных значений из таблицы.
Определение длины маски численным методом Link to heading
Если табличный метод не подходит, решение можно получить числено. Пожалуй, самый простой и вместе с тем довольно эффективный способ заключается в слегка модифицированном бинарном поиске.
Использование такого подхода возможно, так как правая часть неравенства хоть и не является дифференцируемой на всём промежутке значений, тем не менее, можно показать, что она монотонно убывает при $m\to\infty$ (так как данная заметка носит прикладной характер, доказательство остается на совести читателя). Это означает, что есть такое вещественное значение $m_0$, которое делит всю область допустимых значений на две: справа неравенство выполняется, а слева не выполняется. Округлив это значение до ближайшего целого сверху мы получим искомый ответ.
int computeRequiredBitMaskLength(double n, double eps) {
if (eps >= 1 || eps <= 0) {
throw new IllegalArgumentException("Epsilon should be in (0, 1) range");
}
if (n <= 0) {
throw new IllegalArgumentException("Cardinality should be positive");
}
int fromM = 1;
int toM = 100000000;
int m;
double eq;
do {
m = (toM + fromM) / 2;
eq = precisionInequalityRV(n / m, eps);
if (m > eq) {
toM = m;
} else {
fromM = m + 1;
}
} while (toM > fromM);
return m > eq ? m : m + 1;
}
double precisionInequalityRV(double t, double eps) {
return max(1.0 / pow(eps * t, 2), 5) * (exp(t) - t - 1);
}
Как и любой другой бинарный поиск, этот выполняется за $O(\log d)$ (где d — размер диапазона по которому происходит поиск). Таким образом, этот подход позволяет находить ответ за несколько десятков итераций даже для больших значений d. Этого более чем достаточно для большинства прикладных задач.