Как все знают с помощью n-бит, можно реализовать счетчик считающий до 2n-1, но если у вас очень ограниченные ресурсы, или вам просто хочется поэкспериментировать и объединить в одно целое последовательности, вероятности, рандом и увеличение счетчика, то прошу под кат.
В этой статье мы увидим как работает, так называемый вероятностный счетчик.
Впервые он был представлен Робертом Моррисом в 1977 году, шифровальщиком, работающим в BellLabs, известного своей фразой
«Три золотых правила для обеспечения компьютерной безопасности: не владейте компьютером, не включайте его и не используйте его».
Подробнее о счетчике
В нашем распоряжении есть t бит.
Выбираем какую-либо неотрицательную возрастающую последовательность ni (i лежит в промежутке от 0 до 2t — 1), заходя немного вперед скажу, что значения ni это и будут наши значения счетчика.
Теперь самое интересное — прибавление счетчика на 1 происходит с вероятностью 1/(ni+1 — ni)
Например наша последовательность это ni = i2, тогда увеличение счетчика от значения 8 сбудется с вероятностью 1/(16-8) = 0.125, в итоге счетчик с ni до ni+1 в среднем увеличится как раз за ni+1 — ni операций
Частный случай вероятностного счетчика это ni = i, очевидно, что при такой последовательности счетчик будет обычным и вероятность прибавления его будет равна 1
Реализация
Теперь попробуем реализовать его на практике.
Реализовывать его будем на языке java.
Предположим, что у нас есть постоянной памяти только на 8-битный byte. Так как он знаковый, то с помощью него можно вести счет до 127, но нам этого мало.
Встает вопрос какую последовательность использовать. Её выбор зависит от того до скольки вам нужно вести счетчик и сильно ли вы готовы пожертвовать точностью. В вашем распоряжении любые целочисленные возрастающие последовательности, например можно поискать их в Онлайн энциклопедии последовательностей.
Мы будем использовать числа Фиббоначи и квадраты чисел.
У нас будет две основных функции. Первая будет увеличивать счетчик, вторая — возвращать i-ое число последовательности.
private byte counter = 0;
public void increase(){
Random rand = new Random();
int randNumber = rand.nextInt(getElementSequence(counter + 1) - getElementSequence(counter));
if(randNumber == 0)
counter++;
}
Здесь реализовано увеличение счетчика в зависимости от вероятности. Счетчик ничего не знает о последовательности и только возвращает i-ый элемент, в зависимости от успеха либо неуспеха события.
Вот последовательность из квадратов чисел
private int getElementSequence(int number){
return (int) Math.pow(number, 2);
}
А вот из чисел Фиббоначи
private int getElementSequence(int number){
int sumFib = 1;
int previousElement = 0;
int temp;
for(int i = 0; i < number + 1; i++){
temp = sumFib;
sumFib = sumFib + previousElement;
previousElement = temp;
}
return sumFib;
}
Эмулируем увеличение счетчика обычным циклом, предположим в 10 000 итераций.
public static void main(String[] args) {
TestApproximateCounting test = new TestApproximateCounting();
for(int i=0; i<10000; i++){
test.increase();
};
}
Подведем итоги
для каждой из последовательностей я провел по 10 прогонов счетчика по 10 000 итераций
| Номер прогона | значение counter для квадратов чисел | Квадраты чисел | значение counter для чисел Фибоначчи | числа Фиббоначи |
|---|---|---|---|---|
| 1 | 93 | 8 649 | 20 | 6 765 |
| 2 | 111 | 12 321 | 20 | 6 765 |
| 3 | 105 | 11 025 | 20 | 6 765 |
| 4 | 103 | 10 609 | 21 | 10 946 |
| 5 | 96 | 9 216 | 21 | 10 946 |
| 6 | 94 | 8 836 | 22 | 17 711 |
| 7 | 93 | 8 639 | 19 | 4 181 |
| 8 | 106 | 11 236 | 19 | 4 181 |
| 9 | 104 | 10 816 | 21 | 10 946 |
| 10 | 94 | 8 836 | 20 | 6 765 |
Как видно, погрешности весьма ощутимые, но если вам нужно на 8 битах считать больше чем до 10 000, то вероятностный счетчик является неплохим вариантом.
Литература:
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. — Алгоритмы. построение и анализ — 2005
Morris, R. Counting large numbers of events in small registers. Communications of the ACM 21, 10 (1977), 840–842
UPD. по просьбам добавил в таблицу два столбца, показывающих значения counter для каждой из последовательностей, но еще раз скажу, что значение самого счетчика получается не из counter а из функции getElementSequence с counter на вход.
