Sotomajor.org.ua - PHP development: Использование битовых масок в веб-программировании

Как гласит боянистая шутка, в мире есть 10 категорий людей: те, кто знает двоичное исчисление, и те, кто не знает. Так вот, те кто знают и умеют выполнять простейшие побитовые операции, после прочтения статьи узнают как хранить несколько признаков в одном целом числе. А те, кто не знает двоичное исчисление – имеют хорошую возможность с ним познакомиться, а потом применить свои знания на примере.

corner icon

Использование битовых масок в веб-программировании

2008-04-10 10:01 // // Раздел:
битовые маски в PHP

Как гласит боянистая шутка, в мире есть 10 категорий людей: те, кто знает двоичное исчисление, и те, кто не знает. Так вот, те кто знают и умеют выполнять простейшие побитовые операции, после прочтения статьи узнают как хранить несколько признаков в одном целом числе. А те, кто не знает двоичное исчисление - имеют хорошую возможность с ним познакомиться, а потом применить свои знания на примере.

Дважды два четыре: битовая арифметика

Для того, чтобы понять о чем ведется речь в статье, читатель должен иметь хотя бы минимальные понятия о двоичной системе исчисления и уметь преобразовать десятичное число к двоичному и наоборот. Если это не так, то советую сперва прочитать статью Двоичная система счисления в Википедии.

Теперь нам понадобится понимание трех логических операций в их побитовой интерпретации: конъюнкции (логическое И), дизъюнкции (логическое ИЛИ) и отрицания (инвертирования). Здесь я приведу простые примеры каждой из этих операций, а более подробно можно прочитать в той же Википедии: Битовые операции

Пускай у нас есть 2 числа: a=3 и b=5. В двоичном представлении они будут выглядеть так:
a = 011
b = 101

Логическое И:

В PHP операция имеет вид:
$c = $a & $b;

Суть ее заключается в том, что в результате устанавливаются в 1 те и только те биты, которые есть и в первом и во втором входе. Т.е., результат будет 001, что в десятичной системе соответствует числу 1.

Логическое ИЛИ:

В PHP операция имеет вид:
$c = $a | $b;

В этом случае устанавливаются биты, которые есть или в первом или во втором входе. Результат будет 111, что соответствует 7 в десятичной системе.

Логическое НЕ (инвертирование):

В отличие от предыдущих двух, эта операция является унарной, тоесть имеет один вход.

В PHP операция имеет вид:
$c1 = ~$a;
$c2 = ~$b;

В этом случае устанавливаются биты, которые не установлены на входе. Т.е., в первом случае мы получим 100, а во втором - 010 - соответственно 4 и 2 в десятичной системе.

Лепим маски: постановка задачи

Здесь можно ненадолго отвлечься от битовых операций и представить себе следующую ситуацию. У нас имеется таблица пользователей, о которых нужно хранить такую информацию:

  • имя
  • год рождения
  • есть ли у него домашнее животное (не важно какое)
  • женат ли он (или замужем, если это она)
  • имеет ли доступ к Интернету

Самым очевидным решением такой задачи будет создание таблички из 6 полей: одного строкового и пяти целочисленных типов. Этот вариант вполне работоспособный, но...

... Но если внимательно посмотреть, то станет видно, что три последних аттрибута могут принимать только 2 значения: да или нет (0 или 1). Здесь и нужно вспомнить о том, что двоичная запись числа фактически представляет собой массив значений 0/1, при чём, как оказывается, с довольно удобным интерфейсом их изменения (через битовые операции). Зададим каждому свойству короткое имя и соответствующую степень двойки начиная с нуля. Для удобства, дальше будем называть это число степенью свойства. Кроме того, у каждого свойства будет двоичное и десятичное значение, которое будет равно двойке, возведенной в соответствующую ему степень.


Свойство Имя свойства Степень свойства Двоичное значение Десятичное значение
домашнее животное pet 0 001 1
женат ли он married 1 010 2
имеет ли доступ к Интернету internet_access 2 100 4

Получается, что человеку, у которого нету домашних животных, но он женат и имеет доступ в интернет - соответствует двоичное число 110 (или 6 в десятичной системе), а человеку, который неженат, сидит без инета, но с котом - 001 (1).

Что такое битовые маски?

Битовая маска — определённые данные, которые используются для выбора битов из двоичной строки или числа. Более подробное теоретическое описание можно получить в статье Mask (computing) английской Википедии, а практические примеры работы с ними показаны ниже в статье.

Битовые маски довольно широко используются в системном программированиие и компьютеной графике.

Самым наглядным примером неявного использования битовых масок является команда chmod.

Маскарад начинается: битовые маски в веб-программировании

Итак, мы можем составить десятичное число для каждого пользователя, назовём его status, которое содержит в себе информацию о наличии или отсутствии того или иного свойства. Чтобы установить в status свойство, нужно выполнить операцию побитового ИЛИ над статусом и десятичным представлением свойства и записать в статус результат. Чтобы исключить - нужно записать в статус результат операции логического И над статусом и инвертированным значением свойства.

Чтобы проверить установлено ли то или иное свойство в данный status, нужно наложить битовую маску свойства на значение статуса: сравнить результат операции логического И над статусом и свойством со значением этого свойства.

В приведенном ниже примере мы инициализируем значение переменной $status нулём (отсутствие каких-либо свойств), затем добавим в него свойства pet, married, internet_access и уберем свойство married. После каждого действия будем "расшифровывать" статус.

php:
<?php
$status = 0;

$status = $status | 1;
print_status($status);
//Статус: 1 - имеет домашнее животное

$status = $status | 2;
print_status($status);
//Статус: 3 - имеет домашнее животное, женат

$status = $status | 4;
print_status($status);
//Статус: 7 - имеет домашнее животное, женат, имеет доступ к Интернету

$status = $status & ~2;
print_status($status);
//Статус: 5 - имеет домашнее животное, имеет доступ к Интернету

function print_status($s)
{
        $result = array();
        if ( ($s & 1) == 1)
                $result[] = 'имеет домашнее животное';
        if ( ($s & 2) == 2)
                $result[] = 'женат';
        if ( ($s & 4) == 4)
                $result[] = 'имеет доступ к Интернету';
       
        echo 'Статус: '.$s.' - '.(isset($result[0])?implode(', ', $result):'ни одно из свойств не установлено').'<br/>';
}

Занавес: переносим на CУБД

Стоит заметить, что в СУБД MySQL и PostgreSQL, аналогичные операции обозначаются точно так же, поэтому составить запросы на выборку пользователей, имеющих определенные свойства и запросы на изменение статуса не составляет труда.

Вернувшись к описанной ситуации, мы можем теперь построить таблицу не с пятью, а с тремя полями (здесь не указаны ключи, посколько внимание акцентируется совершенно на другом):

sql:
CREATE TABLE `test`.`users` (
  `name` VARCHAR(100),
  `birth_year` INTEGER(4) UNSIGNED,
  `status` INTEGER UNSIGNED
)

Тогда базовые запросы будут иметь такой вид:

  • Выборка всех пользователей, имеющих свойство married (степень 1) и не имеющих свойства pet (степень 0)
  • Установка пользователю с name = "vasya" свойства pet (степень 0) и сброс свойства internet_access (степень 2)
  • Добавление нового пользователя с именем "petya", у которого установлено свойство pet (степень 0) и свойство married (степень 1)
sql:
SELECT * FROM `test`.`users` WHERE (`status` & 2 = 2) AND (`status` & 1 != 1);
UPDATE `test`.`users` SET `status` = (`status` | 1) & ~4 WHERE `name` = "vasya";
INSERT INTO `test`.`users` (`name`, `birth_year`, `status`) VALUES ("petya", 1980, (1|2));

Ограничения

Как нетрудно догадаться, в одном значении можно хранить ограниченное количество признаков. Ограничено это количество типом переменной (или столбца таблицы БД). Если нам нужно хранить информацию о n различных свойствах, то "хранилище" должно иметь способность сохранять значения не меньше 2^n.

Например, в MySQL столбец BIGINT с параметром UNSIGNED может хранить числа до 18446744073709551615 (2^64 -1), что позволяет описать 63 свойства. Тем не менее, для нормальной работы с PHP рекомендуется назначать не более 31 свойства на одно значение, так как PHP не совсем корректно работает с целыми числами, которые превышают 32 бита. Если же такого количества свойств оказалось мало, можно использовать вторую колонку в таблице базы данных.

Второе ограничение - это индексирование по этим полям. По идее, индекс не должен влиять на скорость выполнения битовых операций. Однако, в силу природной "шустрости" этих операций, быстродействие не должно стать узким местом такого подхода. Собственно, лучший способ убедиться в этом - сделать тест производительности.

Кто быстрее?

Легенда примерно следующая: у нас список пользователей, каждый из которых имеет уникальный id, и 15 свойств (p1, p2 ... p15). Каждое из свойств может принимать значения 1 или 0. Список дублируется в двух таблицах, одну из которых будем называть "классической" - там свойства будут храниться каждое в своей колонке с типом BOOLEAN, который MySQL автоматически расценивает как TINYINT(1), а вторая "бм-таблица" будет содержать всего 2 столбца: автоинкрементный id и статус типа INTEGER. Пока обе таблицы не имеют индекса, потом индекс будет построен для обеих таблиц.

sql:
CREATE TABLE `test`.`users_classic` (
  `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
  `p1` BOOLEAN,
  `p2` BOOLEAN,
  `p3` BOOLEAN,
  `p4` BOOLEAN,
  `p5` BOOLEAN,
  `p6` BOOLEAN,
  `p7` BOOLEAN,
  `p8` BOOLEAN,
  `p9` BOOLEAN,
  `p10` BOOLEAN,
  `p11` BOOLEAN,
  `p12` BOOLEAN,
  `p13` BOOLEAN,
  `p14` BOOLEAN,
  `p15` BOOLEAN,
  PRIMARY KEY (`id`)
)
ENGINE = MyISAM;

CREATE TABLE `test`.`users_bm` (
  `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
  `status` INTEGER UNSIGNED,
  PRIMARY KEY (`id`)
)
ENGINE = MyISAM;

Наполняем

Теперь нужно наполнить таблицы тестовыми данными. Будем заполнять каждую из таблиц миллионом записей, которые аналогичны по своему значению. Наличие того или иного свойства у того или иного пользователя генерируется случайно.

Код примеров можно скачать здесь. Используются классы, описанные в следующей статье (BitMaskPackage - средство генерации SQL-запросов с использованием битовых масок).

Система:

Все запросы выполнялись на такой платформе:

ОС: Windows 2003 Server
PHP: 5.2.3
MySQL: 5.0.24

Описание запросов

Сначала приводится неформальное описание условий выбора, ниже запросы на языке SQL для таблиц users_classic и users_bm, ещё ниже - табличка с результатами эксперимента.

  • №1 - свойство p1 не установлено;
  • №2 - свойства p1, p2 не установлены И свойства p3, p4, p5 установлены;
  • №3 - (свойства p1, p2 не установлены И свойство p15 установлено) ИЛИ (свойства p4, p5, p6, p15 установлены);
  • №4 - свойства p1, p2, p3, p4, p5 установлены И (p6 или p7 не установлено ) И (p8 или p9 p10 или p11 не установлено) И (p12 или p13 установлено или (p14 установлено и p15 не установлено));

Запросы к таблице users_classic

sql:
/*Query 1*/
SELECT `id` FROM `users_classic` WHERE `p1` = 0;
/*Query 2*/
SELECT `id` FROM `users_classic` WHERE `p1` = 0 AND `p2` = 0 AND `p3` = 1 AND `p4` = 1 AND `p5` = 1;
/*Query 3*/
SELECT `id` FROM `users_classic` WHERE (`p1` = 0 AND `p2` = 0 AND `p3` = 0 AND `p15` = 1) OR (`p4` = 1 AND `p5` = 1 AND `p6` = 1 AND `p15` = 1);
/*Query 4*/
SELECT `id` FROM `users_classic` WHERE (`p1` = 1 AND `p2` = 1 AND `p3` = 1 AND `p4` = 1 AND `p5` = 1 AND (`p6` = 0 OR `p7` =0) AND (`p8` = 0 OR `p9` = 0 OR `p10` = 0 OR `p11` = 0) AND (`p12` = 1 OR `p13` = 1 OR (`p14` = 1 AND `p15` = 0)));

Запросы к таблице users_bm

Приведенные ниже запросы были сгенерированы с помощью класса BitCondition, который будет описан в следующей статье.

sql:
/*Query 1*/
SELECT `id` FROM `users_bm` WHERE `status` & 1 = 0;
/*Query 2*/
SELECT `id` FROM `users_bm` WHERE `status` & 28 = 28 AND `status` & 3 = 0;
/*Query 3*/
SELECT `id` FROM `users_bm` WHERE ((`status` & 16384 = 16384 AND `status` & 7 = 0) OR (`status` & 16440 = 16440));
/*Query 4*/
SELECT `id` FROM `users_bm` WHERE `status` & 31 = 31 AND ((((`status` & 32 = 0) OR (`status` & 64 = 0))) AND (((`status` & 128 = 0) OR (`status` & 256 = 0) OR (`status` & 512 = 0) OR (`status` & 1024 = 0))) AND (((`status` & 2048 = 2048) OR (`status` & 4096 = 4096) OR (`status` & 8192 = 8192 AND `status` & 16384 = 0))));

Результаты

А вот и результаты. Все запросы выполнялись из консольного клиента mysql. Обозначение (И) говорит о том, что на момент выполнения запросов для таблицы был построен индекс. Для каждого запроса указано время и количество возвращенных строк.


  users_bm users_bm (И) users_classic users_classic (И)
Запрос №1 4.26 (500110) 4.35 (500110) 4.25 (500110) 11.97 (500110)
Запрос №2 0.89 (31410) 0.89 (31410) 1.03 (31410) 0.80 (31410)
Запрос №3 1.91 (117258) 1.90 (117258) 2.13 (117258) 2.16 (117258)
Запрос №4 0.80 (17850) 0.72 (17850) 0.95 (17850) 0.70 (17850)

Таким образом, можно сделать вывод, что хранение свойств с помощью битовых масок очень даже оправдывает себя. В большинстве запросы к таблице users_bm оказались быстрее запросов к таблице users_classic.

Продолжение следует

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

В следующей статье (BitMaskPackage - средство генерации SQL-запросов с использованием битовых масок) представлен код и примеры использования классов BitPropertiesCollection, BitAction и BitCondition, которые позволяют строить SQL запросы типов INSERT, SELECT, UPDATE, используя битовые маски как в части задания условия, так и в части указания значения.

  • — Написал: Ivan Klishch · 2008-06-24 17:21 · #

    Дуже дякую за статтю ;)
    Подібний метод використовують в OpenAds (тепер OpenX) для зберігання прав користувачів.

  • — Написал: Деня · 2008-07-13 19:46 · #

    Да, битовые маски хорошо подходят для шифрования, кстати!

Добавить комментарий: