Множество в одном числе: пересечь, объединить и проверить за один шаг

Если ты запишешь множество {1, 3, 4, 8} одним числом, добавишь и уберёшь элемент, не трогая остальные, и проверишь одной строкой, что одно множество целиком лежит в другом, - листай до «Теперь сам».

Как думаешь, сколько шагов стоит пересечение

Есть два набора по 25 чисел, все числа от 0 до 49. Нужно узнать, сколько у них общих. Программа проходит по первому списку и каждое число ищет во втором.

Прежде чем читать дальше, прикинь число шагов и подумай, можно ли обойтись одним. Замер тренажёра - 591 шаг. И да, можно одним: если оба набора заранее записаны как два числа, ответ - число единиц в a & b.

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

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

Число как ряд битов - та же строка табеля. А процессор смотрит на все столбцы одновременно.

Механизм: бит на элемент

Пусть элементы - номера от 0 до n − 1. Множество записывается числом, в котором бит k стоит ровно тогда, когда k входит в множество:

элементы     9 8 7 6 5 4 3 2 1 0
{1, 3, 4, 8} 0 1 0 0 0 1 1 0 1 0     = 256 + 16 + 8 + 2 = 282
{3, 6, 8, 9} 1 1 0 1 0 0 1 0 0 0     = 512 + 256 + 64 + 8 = 840

Действия над множествами превращаются в действия над битами, потому что в каждом столбце решается отдельный вопрос про один элемент:

пересечение            a & b          элемент есть в обоих
объединение            a | b          есть хотя бы в одном
разность               a & ~b         есть в a и нет в b
симметрическая разность a ^ b         есть ровно в одном
дополнение             ~a & vse       vse = (1 << n) - 1, все n элементов

И действия с одним элементом k - через маску 1 << k, в которой стоит единственный бит:

входит ли k            a >> k & 1
добавить k             a | 1 << k
убрать k               a & ~(1 << k)
переключить k          a ^ 1 << k
пусто ли множество     a == 0
a целиком внутри b     a & b == a
размер                 a.bit_count()

Добавить элемент, который уже есть, - ничего не изменить; так же ведёт себя обычное множество. Метод bit_count() считает единицы; он есть с Python 3.10, раньше писали bin(a).count("1"). Как это делается без цикла по битам, разбирает следующая глава.

Правило

Множество чисел от 0 до n − 1 - целое, в котором бит k означает «k входит». Пересечение, объединение, разность и сравнение двух таких множеств - одна-две побитовые операции. Маска одного элемента - 1 << k; добавляют через |, убирают через & ~, проверяют через >> k & 1. Полное множество - (1 << n) - 1, дополнение берут только внутри него: ~a & vse.

Разбор: два множества и цена пересечения

def v_masku(spisok):
    m = 0
    for x in spisok:
        m = m | 1 << x
    return m

def iz_maski(m, n):
    spisok = []
    for i in range(n):
        if m >> i & 1:
            spisok.append(i)
    return spisok

a = v_masku([1, 3, 4, 8])
b = v_masku([3, 6, 8, 9])
print(a, bin(a))
print(iz_maski(a & b, 10), iz_maski(a | b, 10))
print(iz_maski(a & ~b, 10), iz_maski(a ^ b, 10))

282 0b100011010
[3, 8] [1, 3, 4, 6, 8, 9]
[1, 4] [1, 4, 6, 9]

Теперь действия с одним элементом - добавить 5, убрать 1, переключить 9:

a = a | 1 << 5
a = a & ~(1 << 1)
a = a ^ 1 << 9
print(iz_maski(a, 10), a.bit_count(), a >> 4 & 1)
vse = (1 << 10) - 1
print(iz_maski(~a & vse, 10), a & 264 == 264)

[3, 4, 5, 8, 9] 5 1
[0, 1, 2, 6, 7] True

264 = 256 + 8 - множество {3, 8}; оно целиком лежит в a, поэтому пересечение с a равно ему самому.

И замер из начала урока. Два набора по 25 разных чисел от 0 до 49, общих элементов восемь. Первый способ - цикл с поиском в списке:

obshih = 0
for x in a:
    if x in b:
        obshih = obshih + 1
print(obshih)

Поиск x in b просматривает список до первого совпадения, поэтому точное число шагов зависит от порядка чисел.

способ                                       шагов
цикл по первому списку, поиск во втором        591
построить две маски и пересечь                 103
пересечь готовые маски и посчитать единицы       1

Последняя строка таблицы - одна строка программы, (ma & mb).bit_count(). Строить маску приходится один раз, а пользоваться - много. Когда пересечений нужна тысяча, первая строка превращается в шестьсот тысяч шагов, третья - в тысячу.

Разбор: клетка судоку, и где приём кончается

В клетку судоку можно поставить цифру, которой ещё нет ни в её строке, ни в столбце, ни в малом квадрате. Цифре d отведём бит d − 1. Пусть в строке уже стоят 1, 4, 7, в столбце - 2, 4, 9, в квадрате - 1, 3, 5.

строка    {1, 4, 7}    001001001  =  73
столбец   {2, 4, 9}    100001010  = 266
квадрат   {1, 3, 5}    000010101  =  21

занято    73 | 266 | 21          101011111  = 351
свободно  ~351 & 0x1FF           010100000  = 160     цифры 6 и 8

Два объединения, переворот и маска - четыре действия на клетку вместо трёх проходов по девяти клеткам. Решатель судоку перебором с возвратом делает такую проверку на каждом шаге поиска, и почти вся его работа - она.

Границы приёма две. Первая - диапазон. Маска хранит не сами элементы, а отметки напротив номеров, поэтому её длина равна наибольшему возможному номеру, а не числу элементов. Множество {5, 1000000} - это миллион битов ради двух единиц; обычное множество на хеш-таблице держит только то, что в нём есть. Маска выгодна, когда диапазон мал или заполнен плотно.

Вторая - ширина слова. Один шаг - это правда, пока маска помещается в машинное слово: 64 элемента (в тренажёре - 52, целые в нём точны до 2⁵³). При большем диапазоне множество хранят массивом слов, и операция стоит n / 64 шагов - по одному на слово. Это всё ещё в десятки раз быстрее поэлементного прохода, но уже не «один шаг». В Python длинное целое - такой массив и есть, и a & b над числами в тысячу битов честно проходит все их слова.

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

Первое: + вместо | при добавлении. a + (1 << k) добавляет элемент, только если его не было. Если был - перенос уходит в соседний разряд: к {1, 3} «добавили» 1 и получили {2, 3}. Симметрично a - (1 << k) портит множество, когда элемента нет.

Второе: дополнение без рамки. ~a в Python - отрицательное число: бесконечно много единиц слева. Его bit_count() считает единицы модуля и к размеру дополнения отношения не имеет. Сначала & vse.

Третье: номера с единицы. Элементы «от 1 до n» кладут в биты от 0 до n − 1, как цифры судоку выше, и забывают сдвиг в одном из двух мест - при записи или при чтении. Все ответы съезжают на единицу.

Четвёртое: проверка вхождения через ==. a & m при проверке одного бита равно не единице, а самой маске: 282 & 8 - это 8. Сравнивать надо с нулём или с m.

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

Расписание «по каким дням недели запускать» - семь битов; cron хранит поля расписания именно так. Шахматные программы держат доску как набор 64-битных чисел: «все белые пешки», «все атакованные поля» - и ходы считают сдвигами и пересечениями. Файловая система отмечает свободные блоки диска битовой картой.

В базах данных на масках построены битовые индексы: для каждого значения столбца - строка битов «в каких записях оно стоит». Условие цвет = красный AND размер = L превращается в & двух таких строк.

И в алгоритмах этого курса: множество посещённых городов в задаче коммивояжёра, уже занятые столбцы и диагонали в задаче о ферзях. Там маска - ещё и номер ячейки в таблице: множество стало числом, и его можно использовать как индекс.

Теперь сам

1. Запиши числом множество {0, 2, 5}.
2. Какое множество записано числом 100?
3. a = 0b101101, b = 0b011100. Найди a & b, a & ~b и скажи, лежит ли b целиком в a.
4. Одной строкой: убери из множества a все элементы с номерами меньше 3.
5. В строке судоку уже стоят цифры 2, 3, 5, 8, 9. Какое число получится в «свободно» и какие это цифры?