Глава 39. Битовая реализация числового множества

Идеи реализации
Класс как библиотечный модуль
Интерфейс класса BitSetSimple
Структура модуля
Данные объекта класса BitSetSimple
Манипуляции с отдельными битами в строке
Реализация методов класса BitSetSimple
Методы add и delete
Метод get
Метод set
Метод toString
Готовая программа (предварительная версия)
Дальнейшие улучшения класса BitSetSimple
Использование встроенной процедуры vec
Улучшения в конструкторе
Преобразование множества в список чисел
Создание копий
Минимальный и максимальный элементы, сумма
Проверка пустоты

Для хранения конечного множества значений в Perl имеется удобная встроенная структура: массив. Строго говоря, массив и множество не одно и то же. Во-первых, массив, в отличие от множества, может содержать одно и то же значение в нескольких экземплярах. Во-вторых, элементы в n-элементном множестве можно расположить n! способами, переставляя их. Таким образом, массив содержит, кроме списка элементов, избыточную информацию об их упорядочении. С учётом того, что имеется n! различных способов упорядочить множество, состоящее из n элементов, количество дополнительной информации равно согласно формуле Хартли log 2 n ! . Для множества из 10 элементов перерасход составит приблизительно 18,47 бит, для 100-элементного — 518,12, для 1000-элементного — 8519,43, для 10000-элементного — 118444,85, для 100000-элементного — 1516687,56, для 1000000-элементного — 18488864,88.

Кроме того, массивы в Perl устроены довольно сложно. На каждый элемент массива приходится много дополнительной информации.

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

Конечное множество неотрицательных чисел удобно реализовать на базе воображаемого массива битов. Присутствие числа i в множестве обозначается установкой i-го бита в массиве, отсутствие — очисткой соответствующего бита. Например, множество простых чисел, не превосходящих 32, то есть 2 3 5 7 11 13 17 19 23 29 31 , представляется в виде битового массива

Слово «воображаемый» применительно к битовому массиву означает, что в языке Perl бит не является допустимым типом, и поэтому отдельный бит не может быть ни скалярным значением, ни элементом массива. Бит — слишком мелкая порция информации. Однако подобие битового массива можно реализовать на базе строковой переменной, а строки в Perl реализованы. Строку можно рассматривать как массив байтов (октетов), а каждый октет — это восемь бит. К отдельным октетам в строке можно добраться по их номеру при помощи процедуры substr. Имеются также средства (мы их обсудим позднее), позволяющие проверить, установлен или сброшен бит с заданным номером в данном октете, а также позволяющие установить или сбросить нужный бит.

Таким образом, выстраивается иерархия структур данных: числовое множество реализуется на базе битового массива, а битовый массив — на базе строки. Такое иерархическое построение одних структур на базе других является довольно типичной задачей при программировании.

Применим технологию ООП и оформим битовое множество как объект класса BitSetSimple, для чего этот класс, естественно, нужно запрограммировать. Для испытания класса BitSetSimple в работе напишем пятую версию программы, ищущей простые числа. Эта программа (primes-eratosthenes-bitset.pl) будет основана на уже известном нам решете Эратосфена, которое представляет числовое множество. В начале работы программы множество содержит все числа, начиная с двойки, вплоть до некоторого заданного. В дальнейшем из этого множества будут удаляться (вычёркиваться) составные числа. Алгоритм будущей программы будет слегка отличаться, что список чисел (вычеркнутых и невычеркнутых) уже не будет сокращаться за счёт удаления из его начала уже рассмотренных чисел.

Поскольку класс BitSetSimple является общезначимым, то есть может найти применение не только в нашей программе, но и в других, было бы неразумно включать исходный текст класса в файл программы. В соответствии с принципом повторного использования кода поместим код класса в отдельный файл (имена таких файлов-библиотек должны иметь суффикс .pm — Perl Module). Логично было бы назвать нашу библиотеку BitSetSimple.pm. Использовать этот библиотечный модуль в программе можно, включив в начало программы команду

use BitSetSimple;

Эта команда находит в одной из известных директорий файл BitSetSimple.pm и подключает его к программе. В число этих известных директорий входит и текущая, поэтому мы не ошибёмся, если поместим этот файл туда, откуда будет запускаться программа. Если попытаться запустить программу из какой-то другой директории, модуль может не найтись, что приведёт к фатальной ошибке, остановке компиляции программы и выводу сообщения об ошибке. Вот как это будет выглядеть в случае, если и программа primes-eratosthenes-bitset.pl, и модуль BitSetSimple.pm расположены в директории ./examples/perl, а программа запускается из текущей директории:

Длинный список директорий после слов @INC contains: и есть путь поиска модуля (он завершается, как видим, текущей директорией .).

Продумывая интерфейс класса, следует ответить на вопрос: какие методы должен предоставлять класс своим пользователям (то есть программистам, использующим класс). Объектами класса являются ограниченные множества целых неотрицательных чисел. С таким множеством можно делать следующие вещи: добавлять число, удалять число, проверять, является ли число элементом множества. Для целей отладки (да и учебных целях тоже) было бы полезно добавить метод, возвращающий human-readable (то есть понятное человеку) строковое представление множества. Для рассмотренного ранее множества простых чисел этот метод должен возвращать строку {2,3,5,7,11,13,17,19,23,29,31}.

Итак, для объекта класса BitSetSimple нужно определить следующие методы:

Поскольку добавление/удаление числа означает установку/очистку некоторого бита, есть резон реализовать соответствующие методы:

Тогда процедуры add и delete легко реализовать как вызовы процедуры set, при котором второй параметр равен соответственно 1 или 0.

Наконец, следует определить конструктор:

Библиотечные возможности языка Perl не требуют, чтобы библиотечный модуль содержал определение класса. Это может быть и набор определений переменных и процедур, не являющихся соответственно данными и методами некоторого класса. Однако раз уж мы выбрали объектно-ориентированный стиль программирования, нужно соответствовать.

Чтобы показать, что модуль содержит определения методов класса BitSetSimple, его текст нужно начать с команды

package BitSetSimple;

(package [ˈpækıdʒ] по английски — пакет).

Завершить текст модуля нужно командой

return 1;

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

Место между package и return заполняется определениями методов:

sub new()	{  }
sub get($)	{  }
sub set($$)	{  }
sub add($)	{  }
sub delete($)	{  }
sub toString()	{  }

Обратите внимание на доллары в скобках после имён методов. Это так называемые прототипы методов, которые указывают, сколько параметров может принимать метод и какого вида. Например, set($$) означает, что при вызове метода $bitSet->set должны передаваться два скалярных параметра (не считая скрытого параметра $bitSet), иначе программа не заработает. Использование прототипов делает программирование более строгим, а ошибки программирования, связанные с неверным использованием параметров метода, вскроются не во время выполнения программы, а во время компиляции (без прототипов такие ошибки могут и не открыться). Подробное изучение прототипов не входят в наши планы.

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

Конструктор класса, как и раньше, принимает в переменную $class имя класса, определяет переменную — пустую строку, затем возвращает ссылку на эту строку, «надписанную» при помощи bless:

sub new()
{
	my $class=shift;
	my $string='';
	my $self=\$string;
	return bless $self, $class;
}

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

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

Повлияет ли это на наши планы? Ничуть.

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

Сначала научимся по индексу i бита в битовом массиве определять номер x того байта в строке, который содержит i-й бит, и положение y бита в этом байте. Это несложно: x = i div 8 (целочисленное частное при делении i на 8), y = i mod 8 (остаток от деления i на 8).

Встроенная процедура substr поможет нам извлекать из строки символ под номером $x:

$char=substr($string, $x, 1);	в переменной $char окажется подстрока строки $string
								длины 1, начинающаяся с позиции $x,
								то есть как раз $x-й символ

Но символ в языке Perl — это ещё не байт. Превратить символ в байт можно с помощью оператора ord. Например,

$byte=ord 'Q';	в переменной $byte окажется число 81

Обратное преобразование байтов в символы осуществляется оператором chr:

$char=chr 82;	в переменной $char окажется символ 'R'

Процедура substr позволяет также заменить заданную подстроку в строке на другую. Для этого при вызове нужно добавить четвёртый аргумент — строку, на которую следует заменить заданную подстроку:

substr($string, $x, 1, 'S');	теперь в строке $string на $x-ом месте
								будет символ 'S'

Теперь самое время выяснить, как проверить, установлен ли в данном байте $byte бит с данным номером или нет. Для этого имеется стандартный приём. Сначала подготовим вспомогательный байт $mask — так называемую маску. В маске должен быть установлен единственный бит — с номером $y, остальные биты очищены. Затем выполняем с байтами $byte и $mask операцию побитового «И». Результатом операции побитового «И» над двумя байтами будет байт, каждый бит в котором получается в результате операции «И» над битами с теми же номерами в байтах-операндах. В Perl оператор побитового «И» обозначается &. Если один из операндов операции побитового «И» является маской, в которой установлен лишь один бит с номером $y, в результате может получиться или байт, равный маске, или полностью нулевой. Нижеследующие примеры показывают, как проверить состояние битов №№ 3 и 4 в байте 01001010 с помощью масок:

Как же приготовить маску с единственным установленным битом № y? Можно взять выражение 2 y . Однако у нас есть большое подозрение, что это решение будет далеко не самым эффективным в смысле быстродействия. Оператор ** возведения в степень слишком универсален, и умеет возводить в различные (не только целые неотрицательные) степени различные числа, не только двойку. Лучше воспользоваться оператором << битового сдвига влево: выражение $byte<<$y возвращает байт, у которого все биты сдвинулись влево на $y позиций. Приводим иллюстрацию битового сдвига влево с байтом $byte, имеющим значение 01001010, на три позиции:

Если применить левый сдвиг на $y позиций к единичному байту (значение 00000001), получится как раз байт со значением 2 y . Это байт, в котором установлен лишь бит № y, что и требуется. Таким образом, выражение 1<<$y даёт более быстрый способ возвести двойку в неотрицательную степень $y, чем 2**$y.

Совершенно аналогично определяется операция >> правого сдвига. Проиллюстрируем её на примере всё того же байта 01001010 и правого сдвига на четыре позиции:

Операции левого и правого байтовых сдвигов дают альтернативный способ проверить состояние бита № y. Сначала сдвигаем байт вправо на y позиций, а затем влево на 7 позиций:

Или наоборот, сначала сдвигаем влево на 7 y позиций, а затем вправо на 7 позиций:

В обоих случаях значения выражений ($byte>>$y)<<7 или ($byte<<(7-$y))>>7 будет ненулевым (истинным) тогда и только тогда, когда $y-й бит в байте $byte установлен. Первый способ предпочтительней, так как не требует дополнительного вычитания.

Суммируем все наши соображения насчёт проверки состояния $y-го бита в байте $byte. Любое из выражений

истинно, только если бит установлен.

Теперь пора выяснить, как установить или очистить $y-й бит в байте $byte. Тут нам опять поможет битовая маска. Если с байтом и маской выполнить операцию | побитового «ИЛИ», бит будет установлен:

Для очистки бита следует выполнить операцию побитового «И», но не с исходной, а с дополнительной маской. Дополнительная маска — это маска, подвергнутая операции ~ побитовой инверсии. Операция побитовой инверсии меняет состояния всех битов в байте на противоположные:

Итак, приводим выражения, которые устанавливают

$byte=$byte|(1<<$y);

или очищают

$byte=$byte&~(1<<$y);

$y-й бит в байте $byte.

Имеются комбинированные операторы &= и |=, сочетающие соответственно операторы побитового «И» и «ИЛИ» с присваиванием. Поэтому приведённые команды можно записать короче:

$byte|=(1<<$y);

и

$byte&=~(1<<$y);

Информатика-54© А. Н. Швец