Счётчик Кнута

2019-10-23T11:11:17Z

217.66.152.112: Опечатка. Слово "дувумя" исправлено на "двумя".

{{Определение
|id=knuth_counter
|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, в которой добавление единицы к числу и вычитание единицы выполняется за <tex>O(1)</tex>.
}}

{{Определение
|id=knuth_counter
|definition= Неотрицательное целое число <tex>N</tex> в '''избыточной двоичной системе счисления''' записывается в виде последовательности разрядов <tex>(d_n d_{n-1} \dotsc d_2 d_1)</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex> {{---}} <tex>i</tex>–й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0,1,2\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^{i-1} = N.
</tex>
}}

Заметим, что в этой системе представление числа неоднозначно, например представление <tex>212</tex> эквивалентно <tex>1100</tex>.

== Счетчик Кнута ==

==== Описание операции инкремента ====

Оригинальный метод предложен Кнутом и состоит из двух действий:

# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>(\dotsc d_{i+1}d_i \dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0 \dotsc)</tex>
# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.

Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный [[Список|список]] позиций двоек в числе. Тогда, чтобы найти младший разряд равный двум, нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов, необходимо выполнять следующие дополнительные действия:

# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.
# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.

==== Инвариант с нулем ====

Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить
тройку. То есть недопустима следующая ситуация:

<tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>.

В свою очередь такая ситуация получается из этой:

<tex>(\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex>

Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.
Однако если между любой парой двоек всегда будет находиться хотя бы один
<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариант
поддерживается после инкремента, рассмотрев возможные ситуации:
: Число двоек не изменяется
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.
:: <tex>(\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2)</tex>.
:: <tex>(\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).
:: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.
: Пропадает одна двойка
:: <tex>(\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.
:: <tex>(\dotsc 02) \overset{Inc} {\longmapsto} (\dotsc 11)</tex>.
: Появление новой двойки
:: <tex>(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).
:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)</tex> (частный случай предыдущего).

Таким образом мы видим, что <tex>0</tex> всегда сохраняется.

==== Пример ====

В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):

{| class="wikitable"
|-
! Шаг
! Представление
|-
| 0
| 0
|-
| 1
| 1
|-
| 2
| 2
|-
| 3
| 11
|-
| 4
| 12
|-
| 5
| 21
|-
| 6
| 102
|-
| 7
| 111
|-
| 8
| 112
|-
| 9
| 121
|}

== Обобщение на системы с произвольным основанием ==

{{Определение
|id=b_ary_rr
|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричным избыточным представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex> {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex>
}}

{{Определение
|id=regular_rr
|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между двумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.
}}

{{Определение
|id=fixup
|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуя новое регулярное ИП, представляющее то же число, что и <tex>d</tex>.
}}

Чтобы добавить <tex>1</tex> к разряду <tex>d_i</tex> регулярного ИП <tex>d</tex>,
нужно выполнить следующие действия:
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.
# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.
# Добавить <tex>1</tex> к <tex>d_i</tex>.
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.

Для реализации данной схемы мы используем односвязный список разрядов от младших
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex>
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,
что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, если он равен <tex>b</tex>,
иначе этот указатель будет на произвольный разряд <tex>d_j</tex> (<tex>j>i</tex>).
Теперь во время увеличения разряда <tex>d_i</tex> на <tex>1</tex> будем проверять
разряд по указателю вперед (п. 2).

Такое представление позволяет увеличивать произвольный разряд на единицу за константное
время. Обновление указателя вперед происходит следующим образом: когда <tex>d_{i+}</tex> становится равен <tex>b-1</tex> при исправлении разряда <tex>d_{i-1}</tex>, устанавливаем указатель вперед разряда <tex>d_{i}</tex> на <tex>d_{i+1}</tex>, если <tex>d_{i+1}=b</tex>, либо копируем указатель вперед из <tex>d_{i+1}</tex> в <tex>d_{i}</tex>, если <tex>d_{i+1}=b-1</tex>.
При собственно добавлении единицы к разряду <tex>d_i</tex>, также необходимо обновлять его указатель вперед аналогичным образом,
если этот разряд становится равен <tex>b-1</tex>.

== См. также ==
* [[Амортизационный анализ]]
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]]

== Источники информации ==
* H. Kaplan и R. E. Tarjan. New heap data structures. 1998
* M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.
* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.
* H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. ''Proceedings of the 28th Annual ACM Symposium of Computing'', страницы 202-211. ACM Press, 1996
* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Викиконспекты - Вклад участника [ru]

Счётчик Кнута