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

Допустим, вы хотите создать линейный счетчик для оценки количества элементов в потоке, с максимальным количеством уникальных элементов равным 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%. Приведу здесь часть таблицы для полноты повествования.

n1%10%
$10^2$503480
$10^3$5329268
$10^4$79601709
$10^5$2672912744
$10^6$154171100880
$10^7$1096582831809

Если вам нужна оценка для точности 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. Этого более чем достаточно для большинства прикладных задач.