Размер линейного счетчика

14 April 2013 algorithms math probability

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

Допустим, вы хотите создать линейный счетчик для оценки количества элементов в потоке, с максимальным количеством уникальных элементов равным 10 миллионам. Какой длины должна быть битовая маска? Ответ на этот вопрос позволяет найти следующее неравенство:

Минимальное положительное целое m, для которого выполняется это неравенство, является длиной маски при которой обеспечивается необходимая точность.

В этой формуле:

К сожалению, у этого неравенства нет алгебраического решения, – из него нельзя выразить m. Для прикладного применения ответ можно получить несколькими способами.

Таблицы

В оригинальной публикации приведены таблицы для точности 1 и 10%. Приведу здесь часть таблицы для полноты повествования.

n 1% 10%
102 5034 80
103 5329 268
104 7960 1709
105 26729 12744
106 154171 100880
107 1096582 831809

Если вам нужна оценка для точности 1 или 10%, её можно узнать интерполяцией двух промежуточных значений из таблицы.

Определение длины маски численным методом

Если табличный метод не подходит, решение можно получить числено. Пожалуй, самый простой и вместе с тем довольно эффективный способ заключается в слегка модифицированном бинарном поиске.

Использование такого подхода возможно, так как правая часть неравенства хоть и не является дифференцируемой на всём промежутке значений, тем не менее, можно показать, что она монотонно убывает при (так как данная заметка носит прикладной характер, доказательство остается на совести читателя). Это означает, что есть такое вещественное значение , которое делит всю область допустимых значений на две: справа неравенство выполняется, а слева не выполняется. Округлив это значение до ближайшего целого сверху мы получим искомый ответ.

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);
}

Как и любой другой бинарный поиск, этот выполняется за (где d — размер диапазона по которому происходит поиск). Таким образом, этот подход позволяет находить ответ за несколько десятков итераций даже для больших значений d. Этого более чем достаточно для большинства прикладных задач.