Битовый параллелизм: шестьдесят четыре сравнения одной командой

Если ты посчитаешь расстояние Хэмминга двух двоичных строк через ^, заменишь таблицу достижимых сумм одним числом со сдвигом и объяснишь, почему от этого не меняется порядок роста, - листай до «Теперь сам».

Как думаешь, во сколько раз это ускоряется

Сорок строк по 48 символов, каждый символ - ноль или единица. Нужно найти две самые похожие: с наименьшим числом позиций, в которых они различаются. Пар 780, в каждой 48 сравнений.

Прежде чем читать дальше, прикинь: если заменить посимвольное сравнение одной побитовой операцией, выигрыш будет в два раза, в десять или больше? Замер - в 39 раз: 96 021 шаг против 2 470.

На что это похоже

Проверяющий сверяет два бланка с ответами на тест: в каждом сорок восемь клеток «да» или «нет». Можно идти по клеткам с карандашом. А можно напечатать бланки на прозрачной плёнке, наложить один на другой и посмотреть на просвет: несовпадения видны все сразу.

Наложение плёнок - побитовая операция. Она не быстрее сравнения одной клетки, но делает все сорок восемь за то же время.

Механизм: слово как ряд независимых вычислителей

Из первого урока главы: в побитовой операции разряды не влияют друг на друга. Значит одна команда над 64-битным словом - это 64 одинаковых однобитных действия, выполненных одновременно. Чтобы этим воспользоваться, нужны два условия: данные должны быть битами - ответами «да» или «нет», - и над всеми позициями должно делаться одно и то же.

Тогда работают три хода.

Сравнить и посчитать. a ^ b ставит единицу там, где слова различаются; число единиц в результате - число различий. a & b и счёт единиц - число позиций, где «да» у обоих.

Сдвинуть всё разом. Если бит s означает «сумму s набрать можно», то mozhno << w - это «каждую достижимую сумму увеличили на w». Один сдвиг заменяет проход по всей таблице.

Строка таблицы как слово. Если строка i матрицы - маска «куда можно попасть из i», то действие «всё, куда ведёт k, теперь достижимо и из i» - это stroka[i] | stroka[k]: одна команда вместо цикла по столбцам.

Расстояние Хэмминга между двумя строками равной длины - число позиций, в которых они различаются. Для двоичных строк это число единиц в a ^ b.

Правило

Если шаг алгоритма делает одно и то же действие «да или нет» над w позициями, эти позиции укладывают в слово и заменяют цикл одной побитовой командой. Время падает в w раз, где w - ширина слова; порядок роста не меняется. Данные длиннее слова хранят массивом слов, и команда над ними стоит длина / w.

Разбор: самые похожие строки

Посимвольно:

luchshee = len(stroki[0]) + 1
for i in range(len(stroki)):
    for j in range(i + 1, len(stroki)):
        raznyh = 0
        for k in range(len(stroki[i])):
            if stroki[i][k] != stroki[j][k]:
                raznyh = raznyh + 1
        if raznyh < luchshee:
            luchshee = raznyh
print(luchshee)

И то же после перевода каждой строки в число - int(s, 2) читает строку как двоичную запись:

chisla = []
for s in stroki:
    chisla.append(int(s, 2))
luchshee = len(stroki[0]) + 1
for i in range(len(chisla)):
    for j in range(i + 1, len(chisla)):
        raznyh = (chisla[i] ^ chisla[j]).bit_count()
        if raznyh < luchshee:
            luchshee = raznyh
print(luchshee)

                       ответ      шагов
посимвольно              13      96 021
через ^ и счёт единиц    13       2 470

Сорок строк получены генератором случайных чисел и в урок не поместились. Тройной цикл стал двойным: внутренний цикл на 48 кругов уместился в одну строку программы. Выигрыш - в 39 раз, а не в 48: тренажёр считает и строки двух внешних циклов, которые никуда не делись. Перевод строк в числа входит во вторую цифру: тренажёр берёт за него 81 шаг, по два на строку. Настоящий перевод читает все 48 символов каждой строки - это 1920 действий, но один раз на весь набор, а не на каждую пару.

Разбор: достижимые суммы, достижимые вершины и граница приёма

Есть грузы с весами 3, 5, 7, 11, 13. Какие суммы от 0 до 39 можно набрать, беря каждый груз не больше раза? В программах ves - список весов, S = 39. Таблица «да или нет» из раздела про динамическое программирование:

mozhno = [False] * (S + 1)
mozhno[0] = True
for w in ves:
    for s in range(S, w - 1, -1):
        if mozhno[s - w]:
            mozhno[s] = True

Внутренний цикл делает одно и то же с каждой ячейкой: «если достижима сумма s − w, достижима и s». Это сдвиг всей таблицы на w и объединение со старой. Табличный цикл шёл по убыванию s, чтобы груз не взялся дважды; сдвиг считается целиком от старого значения, и та же защита получается сама:

mozhno = 1
for w in ves:
    mozhno = mozhno | mozhno << w
mozhno = mozhno & (1 << S + 1) - 1
print(mozhno.bit_count())

28

Достижимых сумм 28 из 40. Таблица стоила 400 шагов, число со сдвигом - 13.

Третий ход - матрица достижимости в графе. stroka[i] - маска вершин, в которые из i ведёт путь: бит j стоит, если из i можно попасть в j; в начале это рёбра графа и сама вершина i. Алгоритм Уоршелла из раздела про кратчайшие пути перебирает промежуточную вершину k:

n = len(stroka)
for k in range(n):
    for i in range(n):
        if stroka[i] >> k & 1:
            stroka[i] = stroka[i] | stroka[k]

На графе из 40 вершин тройной цикл по ячейкам таблицы - тот, что был в разделе про кратчайшие пути, - стоит 50 827 шагов, двойной по строкам-маскам - 3 712.

Теперь граница. Во всех трёх примерах убран внутренний цикл, но только потому, что данные поместились в слово. Для графа на 6400 вершин строка - сто слов, и stroka[i] | stroka[k] стоит сто команд, а не одну. Время - n³ / 64 вместо n³: в 64 раза меньше, но при удвоении n оно по-прежнему растёт в восемь раз. Битовый параллелизм не переводит алгоритм в другой класс; он сдвигает границу посильного размера: в восемь раз для квадратичного алгоритма, вчетверо для кубического.

В тренажёре целое точно до 2⁵³, поэтому примеры урока уложены в 52 бита. В настоящем Python длинное целое само хранится массивом кусков по 30 битов, и mozhno << w работает для суммы в миллион - со стоимостью, пропорциональной длине числа.

Что ломается без этого

Первое: число растёт без рамки. mozhno << w дописывает биты слева при каждом грузе. В Python число удлиняется, и каждая следующая операция дороже; в C старшие биты молча пропадают. Рамку ставят маской после каждого сдвига. В программе выше хватило одной маски в конце: сумма всех грузов равна S, и длиннее 40 битов число не становится.

Второе: порядок битов против порядка символов. int(s, 2) кладёт первый символ строки в старший бит. Символ с номером k слева - это бит длина − 1 − k. Пока считаешь число различий, это неважно; как только нужен номер позиции - ошибка на зеркальное отражение.

Третье: в ячейке больше, чем «да или нет». Таблицу «сколькими способами набирается сумма» или «наименьшее число грузов» сдвигом не заменить: в одном бите число не помещается. Приём годится для вопроса «можно ли», а не «сколько».

Четвёртое: счёт единиц циклом. Если после a ^ b единицы считать проходом по битам, внутренний цикл вернулся. Нужна быстрая операция счёта - в Python bit_count(), в процессоре отдельная команда.

Зачем это в работе

В C++ это тип bitset, и на нём решают задачи, где честному алгоритму не хватает времени в десятки раз: рюкзак на «можно ли», достижимость, пересечения множеств. В Java - BitSet.

Поиск похожих документов сворачивает каждый документ в отпечаток из 64 битов и сравнивает отпечатки расстоянием Хэмминга: одна команда ^ и одна команда счёта единиц на пару. Поиск подстроки с опечатками в утилите agrep построен так же: состояние поиска - одно слово, и символ текста обрабатывается сдвигом и маской.

Современные процессоры расширяют слово до 256 и 512 битов: набор команд AVX-512 делает побитовые операции над полукилобитными регистрами и умеет считать в них единицы. Битовые индексы баз данных пересекают миллионы записей именно так.

Теперь сам

1. Найди расстояние Хэмминга между 10110 и 00111 через ^.
2. mozhno = 1, грузы 2 и 3. Чему равно mozhno после обоих и какие суммы это?
3. Две строки клетчатого поля: a = 0b110101, b = 0b100111, единица - чёрная клетка. В скольких столбцах чёрные обе клетки? Сколько прямоугольников с чёрными углами лежит на этих двух строках?
4. Граф на 640 вершин. Сколько слов в строке матрицы достижимости и во сколько раз битовая версия алгоритма Уоршелла быстрее поклеточной?
5. Почему таблицу «наименьшее число монет для суммы» нельзя заменить одним числом со сдвигом?