Алгоритм Гончарова
Алгоритм Гончарова — способ, позволяющий подсчитать количество рядов в битовой последовательности, где под словом «ряд» подразумевается непрерывная подпоследовательность одинаковых битов.
Ряд длиной k бит состоит из k абсолютно идентичных битов, начинается и заканчивается с бита, содержащего противоположное значение.
Алгоритм[править]
где:
- x — входное значение
- n — количество рядов
- pop — функция, подсчитывающая количество единичных битов
Реализация[править]
|
<syntaxhighlight lang="cpp"> // Подсчитывает количество рядов в первом элементе.
// Параметр prevHi возвращает состояние старшего бита в целях последующего объединения рядов, идущих через границу между элементами.
template <class T>
static unsigned int getNumberOfRowsFirst(T x, int &prevHi)
{
prevHi = 1 - (x & 1);
return getNumberOfRowsNext(x, prevHi);
}
// Подсчитывает количество рядов в следующем элементе.
// Параметр prevHi используется для объединения рядов, идущих через границу между элементами.
template <class T>
static unsigned int getNumberOfRowsNext(T x, int &prevHi)
{
unsigned int uiRes = pop(static_cast<T>(x ^ ((x << 1) | prevHi)));
prevHi = x >> ((sizeof(T) * 8) - 1);
return uiRes; } </syntaxhighlight> |
Тестирование[править]
Для тестирования использовался неттоп на базе материнской платы N3160ND3V с процессором Intel(R) Celeron(R) CPU N3160 @ 1.60 GHz.
ОС: Ubuntu 20.04.4 LTS (Focal Fossa)
Тестирование скорости выполнения было проведено для версий алгоритма с использованием поисковых таблиц и без них, для элементов размером от 8 до 128 бит..
Использовался блок данных размером 1 мегабайт. Скорость выполнения усреднялась на протяжении 100 эпох.
Выяснилось, что с таблицами и без них скорость выполнения получается практически одинаковая. Отклонения варьировались от запуска к запуску в пределах ±1%.
На указанном оборудовании алгоритм быстрее всего работает с элементами размером 64 бита (uint64_t):<syntaxhighlight> >>>> Testing for elements of size 64 bits <<<< ... Test without tables: number of bit runs: 2097152 avg execution time: 1.49 uS Test with tables: number of bit runs: 2097152 avg execution time: 1.49 uS </syntaxhighlight>
См.также[править]
Литература[править]
- Генри Уоррен-мл Алгоритмические трюки для программистов Второе издание.