Битсеты: как ускорить алгоритм в 64 раза одной заменой массива
Оптимизация битсетами: subset sum и Partition Equal Subset Sum, транзитивное замыкание, подсчёт треугольников, Python int и BigInt как битсет, std::bitset в C++. С замерами и кодом.
Коротко
| Параметр | Значение |
|---|---|
| Идея | хранить массив булевых значений по 64 штуки в одном машинном слове |
| Выигрыш | в w раз (w = 64) для операций над целыми строками битов |
| Типичная запись | вместо |
| Инструменты | std::bitset в C++, int в Python, BigInt в JavaScript |
- Если внутренний цикл алгоритма делает одно и то же с каждым элементом булева массива — «для всех j:
a[j] = a[j] or b[j]», — его можно заменить одной операцией над битсетом. - Классика: subset sum и рюкзак на достижимость, транзитивное замыкание графа, подсчёт треугольников, LCS для малых алфавитов.
- Асимптотика формально та же, но константа делится на 64. На практике это разница между «не проходит» и «проходит с запасом».
Откуда берутся 64 раза
Процессор выполняет a | b над 64-битными словами за один такт. Если положить в слово 64 булевых значения, одна инструкция обработает их все сразу. Это и есть битсет: массив слов, где бит j отвечает за элемент j.
Операции над битсетом длины S стоят , где w — размер машинного слова:
a | b,a & b,a ^ b— объединение, пересечение, симметрическая разность множеств;a << k— сдвинуть всё множество на k: каждый элементjпревращается вj + k;popcount— количество единиц, то есть размер множества.
Битовые операции на уровне отдельных чисел разобраны в статье о битовых манипуляциях. Здесь — следующий шаг: числа как множества большого размера.
Главный навык — увидеть в алгоритме цикл, который можно «свернуть» в одну битовую операцию. Разберём на примерах.
Subset sum: сумма подмножества
Задача: можно ли выбрать из массива nums подмножество с суммой ровно target? Её частный случай — LeetCode 416 Partition Equal Subset Sum: разбить массив на две части с равной суммой, то есть найти подмножество с суммой total / 2.
Обычный DP
Классическое решение — рюкзак на достижимость: dp[s] = True, если сумму s можно набрать.
def can_partition_dp(nums): total = sum(nums) if total % 2: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for x in nums: for s in range(target, x - 1, -1): if dp[s - x]: dp[s] = True return dp[target]
Время — , где S — целевая сумма.
Та же идея битсетом
Посмотрите на внутренний цикл. Для каждого s он делает dp[s] |= dp[s - x]. Если представить dp как битсет reach, это ровно reach |= reach << x: сдвиг на x превращает каждую достижимую сумму s в s + x.
def can_partition(nums): total = sum(nums) if total % 2: return False reach = 1 # бит 0 = сумма 0 достижима for x in nums: reach |= reach << x return (reach >> (total // 2)) & 1 == 1
Пять строк вместо десяти и никакого обратного цикла — сдвиг сам по себе гарантирует, что каждый элемент используется один раз: мы берём старое значение reach целиком.
Я сравнил обе версии на 200 случайных числах от 1 до 1000 (сумма около 110 000): DP на списке работал около 0,4 секунды, версия с int — около 0,4 миллисекунды. Разница в тысячу раз, и это больше, чем 64: в Python к выигрышу от битового параллелизма добавляется то, что весь цикл уходит из интерпретатора в C-код длинной арифметики.
Обрезка лишних битов
reach растёт до суммы всех чисел. Если нас интересуют только суммы до limit, лишние биты стоит отрезать маской — иначе число раздувается и операции замедляются:
def subset_sums(nums, limit): mask = (1 << (limit + 1)) - 1 reach = 1 for x in nums: reach = (reach | (reach << x)) & mask # обрезаем лишние биты return reach r = subset_sums([3, 5, 7], 15) print([s for s in range(16) if r >> s & 1]) # [0, 3, 5, 7, 8, 10, 12, 15]
На C++ и JavaScript
В C++ для этого есть std::bitset. Его размер — константа времени компиляции, поэтому берут с запасом под максимальную сумму из ограничений:
#include <bitset> #include <vector> using namespace std; const int MAXS = 100001; // размер должен быть известен на этапе компиляции bool canPartition(const vector<int>& nums) { int total = 0; for (int x : nums) total += x; if (total % 2) return false; bitset<MAXS> reach; reach[0] = 1; for (int x : nums) reach |= reach << x; return reach[total / 2]; }
В JavaScript роль длинного битсета играет BigInt:
function canPartition(nums) { const total = nums.reduce((a, b) => a + b, 0) if (total % 2) return false let reach = 1n for (const x of nums) reach |= reach << BigInt(x) return ((reach >> BigInt(total / 2)) & 1n) === 1n }
Нюанс: BigInt и int в Python неизменяемы, каждая операция создаёт новое число. На очень больших S это заметно медленнее std::bitset, который меняет слова на месте. Но для задач уровня собеседования хватает с большим запасом.
Coin Change через битсет
Задача Coin Change: минимальное число монет, чтобы набрать сумму amount. Обычно её решают DP за , где k — число номиналов. Но можно посмотреть на неё как на BFS по суммам: слой steps — все суммы, набираемые не более чем steps монетами. Переход к следующему слою — это сдвиги на каждый номинал.
def coin_change(coins, amount): if amount == 0: return 0 mask = (1 << (amount + 1)) - 1 reach = 1 for steps in range(1, amount + 1): nxt = reach for c in coins: nxt |= reach << c nxt &= mask if nxt >> amount & 1: return steps if nxt == reach: return -1 # новых сумм не появилось reach = nxt return -1
Каждый слой стоит , а слоёв не больше ответа. Когда ответ маленький по сравнению с суммой — например, крупные номиналы, — это может быть заметно быстрее обычного DP. Я сверил эту версию с классическим DP на пятистах случайных наборах монет.
Транзитивное замыкание графа
Задача: для каждой пары вершин (i, j) ориентированного графа узнать, есть ли путь из i в j. Стандартное решение — алгоритм Уоршелла, родственник Флойда — Уоршелла:
for k in range(n): for i in range(n): if r[i][k]: for j in range(n): if r[k][j]: r[i][j] = True
Это . Но внутренний цикл по j — это r[i] |= r[k] для строк матрицы. Храним каждую строку как битсет:
def transitive_closure(n, edges): # reach[v] — битсет вершин, достижимых из v reach = [1 << v for v in range(n)] for u, v in edges: reach[u] |= 1 << v for k in range(n): bit = 1 << k rk = reach[k] for i in range(n): if reach[i] & bit: reach[i] |= rk return reach
Сложность — . На случайном графе из 600 вершин версия со списками работала 0,75 секунды, с битсетами — 0,02. Граф на 2000 вершин замыкается битсетами за 0,3 секунды в Python и примерно за 15 миллисекунд на C++:
const int MAXN = 2000; void transitiveClosure(vector<bitset<MAXN>>& reach, int n) { for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) if (reach[i][k]) reach[i] |= reach[k]; }
Зачем это на практике: проверка зависимостей (может ли модуль A косвенно зависеть от B), иерархии ролей и прав, запросы «достижима ли вершина» к фиксированному графу — после замыкания каждый отвечается за O(1). Для DAG есть вариант ещё проще: обходим вершины в обратном топологическом порядке и делаем reach[v] |= reach[u] для каждого ребра v → u — это .
Подсчёт треугольников
Сколько в неориентированном графе треугольников? Для каждого ребра (u, v) нужно посчитать общих соседей u и v. С битсетами смежности это пересечение и popcount:
def count_triangles(n, edges): adj = [0] * n for u, v in edges: adj[u] |= 1 << v adj[v] |= 1 << u total = 0 for u, v in edges: total += (adj[u] & adj[v]).bit_count() return total // 3
Каждый треугольник посчитан трижды — по разу на каждое ребро, отсюда деление. Сложность . Метод int.bit_count() есть в Python 3.10+, в более старых версиях — bin(x).count('1'). Код предполагает граф без петель и кратных рёбер.
Как найти место для битсета
Признаки, что алгоритм можно ускорить:
- Булев DP с переходом «сдвиг».
dp[j] |= dp[j - x]— этоdp |= dp << x. Сюда попадают рюкзак на достижимость, суммы подмножеств, задачи «какие значения можно получить». - Операции над строками булевой матрицы.
row_i |= row_k,row_i & row_j— замыкания, треугольники, пересечения множеств соседей. - Множества из небольшого универсума. Если элементы — числа до 10⁵ и нужно много объединений и пересечений, битсет быстрее
set.
Не путайте с ДП по маскам: там маска — это состояние (подмножество из 20 элементов), а здесь битсет — способ хранить массив и обрабатывать его пачками по 64.
Ограничения
Работает только для булевых значений. Если DP хранит минимум, количество или сумму, битсет не поможет: в одном бите не уместить число. Для подсчёта количества способов в subset sum по-прежнему нужен обычный массив.
Асимптотика не меняется. — это всё ещё псевдополиномиальный алгоритм. Если S = 10⁹, битсет не спасёт.
Размер std::bitset фиксирован. Его нельзя задать во время выполнения. Для динамического размера — vector<uint64_t> со своими операциями, boost::dynamic_bitset или шаблонный трюк с выбором размера из нескольких степеней двойки.
Неизменяемые числа в Python и JS. Каждая операция копирует всё число. В плотном цикле со множеством мелких изменений одного бита это медленнее, чем bytearray.
Python-специфика. Отрицательные числа в Python бесконечно продолжаются единицами слева, поэтому ~reach даёт отрицательное число, а не «инверсию в пределах S бит». Инвертируйте через XOR с маской: reach ^ mask.
Частые ошибки
Забыли сдвинуть от старого значения. reach |= reach << x берёт старое reach целиком и корректен. А если переписать это побитово в цикле по возрастанию суммы, один элемент будет использован многократно — получится рюкзак с неограниченным числом предметов.
Бит 0 не установлен. Начальное reach = 0 означает «ни одна сумма не достижима», и всё останется нулём. Нужно reach = 1.
Переполнение размера std::bitset. Сдвиг за пределы размера молча теряет биты. Если сумма может превысить MAXS, ответ будет неверным без всякой ошибки.
Лишние биты без маски. В Python число растёт до суммы всех элементов. Если S маленький, а числа большие, без & mask операции работают с огромными числами.
На собеседовании
Битсет редко бывает ожидаемым решением на собеседовании, зато хорошо работает как follow-up. Решили Partition Equal Subset Sum обычным DP — можно добавить: «внутренний цикл — это сдвиг и OR, на битсете будет в 64 раза быстрее», и показать пятистрочную версию. Это демонстрирует понимание того, как алгоритм ложится на железо.
В спортивном программировании битсеты — стандартный приём, чтобы протащить при n порядка нескольких тысяч или при S около 10⁶. Подробнее о таких приёмах — в обзоре техник спортивного программирования.
Что запомнить
- Битсет хранит 64 булевых значения в одном слове, и
|,&,<<обрабатывают их разом. dp[j] |= dp[j - x]для всех j — этоreach |= reach << x.- Транзитивное замыкание:
reach[i] |= reach[k], итого . - В Python и JS роль битсета играют
intиBigInt, в C++ —std::bitsetфиксированного размера. - Работает только для булевых DP; суммы, минимумы и количества так не ускорить.