Для хранения конечного множества значений в Perl имеется удобная встроенная структура: массив. Строго говоря, массив и множество не одно и то же. Во-первых, массив, в отличие от множества, может содержать одно и то же значение в нескольких экземплярах. Во-вторых, элементы в -элементном множестве можно расположить способами, переставляя их. Таким образом, массив содержит, кроме списка элементов, избыточную информацию об их упорядочении. С учётом того, что имеется различных способов упорядочить множество, состоящее из элементов, количество дополнительной информации равно согласно формуле Хартли . Для множества из 10 элементов перерасход составит приблизительно бит, для 100-элементного — , для 1000-элементного — , для 10000-элементного — , для 100000-элементного — , для 1000000-элементного — .
Кроме того, массивы в Perl устроены довольно сложно. На каждый элемент массива приходится много дополнительной информации.
Мы обсудим реализацию конечного множества неотрицательных чисел, не использующую массивов и лишённую перечисленных недостатков. Это битовая реализация числового множества.
Конечное множество неотрицательных чисел удобно реализовать на базе воображаемого массива битов. Присутствие числа в множестве обозначается установкой -го бита в массиве, отсутствие — очисткой соответствующего бита. Например, множество простых чисел, не превосходящих , то есть , представляется в виде битового массива
00110101000101000101000100000101
0 8 16 24 индексы битов в массиве
Слово «воображаемый» применительно к битовому массиву означает, что в языке
Perl бит не является допустимым типом, и поэтому отдельный бит не может быть ни
скалярным значением, ни элементом массива. Бит — слишком мелкая порция
информации. Однако подобие битового массива можно реализовать на базе строковой
переменной, а строки в Perl реализованы. Строку можно рассматривать как массив
байтов (октетов), а каждый октет — это восемь бит. К отдельным октетам в строке
можно добраться по их номеру при помощи процедуры substr
.
Имеются также средства (мы их обсудим позднее), позволяющие проверить,
установлен или сброшен бит с заданным номером в данном октете, а также
позволяющие установить или сбросить нужный бит.
Таким образом, выстраивается иерархия структур данных: числовое множество реализуется на базе битового массива, а битовый массив — на базе строки. Такое иерархическое построение одних структур на базе других является довольно типичной задачей при программировании.
Применим технологию ООП и оформим битовое множество как
объект класса BitSetSimple
, для чего этот класс,
естественно, нужно запрограммировать. Для испытания класса
BitSetSimple
в работе напишем пятую версию программы,
ищущей простые числа. Эта программа
(primes-eratosthenes-bitset.pl) будет основана на уже
известном нам решете Эратосфена, которое представляет числовое множество.
В начале работы программы множество содержит все числа, начиная с двойки,
вплоть до некоторого заданного. В дальнейшем из этого множества будут удаляться
(вычёркиваться) составные числа. Алгоритм будущей программы будет слегка
отличаться, что список чисел (вычеркнутых и невычеркнутых) уже не будет
сокращаться за счёт удаления из его начала уже рассмотренных чисел.
Поскольку класс BitSetSimple
является общезначимым, то
есть может найти применение не только в нашей программе, но и в других, было бы
неразумно включать исходный текст класса в файл программы. В соответствии
с принципом повторного использования кода поместим код класса в отдельный файл
(имена таких файлов-библиотек должны иметь суффикс .pm
—
Perl Module). Логично было бы назвать
нашу библиотеку BitSetSimple.pm
. Использовать этот
библиотечный модуль в программе можно, включив в начало программы команду
Perluse BitSetSimple;
Эта команда находит в одной из известных директорий файл
BitSetSimple.pm
и подключает его к программе. В число этих
известных директорий входит и текущая, поэтому мы не ошибёмся, если поместим
этот файл туда, откуда будет запускаться программа. Если попытаться запустить
программу из какой-то другой директории, модуль может не найтись, что приведёт
к фатальной ошибке, остановке компиляции программы и выводу сообщения
об ошибке. Вот как это будет выглядеть в случае, если и программа
primes-eratosthenes-bitset.pl
, и модуль
BitSetSimple.pm
расположены в директории ./examples/perl
, а программа запускается
из текущей директории:
%
examples/perl/primes-eratosthenes-bitset-simple.pl 100
Can't locate BitSetSimple.pm in @INC (you may need to install the BitSetSimple module) (@INC contains: /usr/lib/perl5/site_perl/5.20.1/x86_64-linux-thread-multi /usr/lib/perl5/site_perl/5.20.1 /usr/lib/perl5/vendor_perl/5.20.1/x86_64-linux-thread-multi /usr/lib/perl5/vendor_perl/5.20.1 /usr/lib/perl5/5.20.1/x86_64-linux-thread-multi /usr/lib/perl5/5.20.1 /usr/lib/perl5/site_perl .) at examples/perl/primes-eratosthenes-bitset-simple.pl line 4. BEGIN failed--compilation aborted at examples/perl/primes-eratosthenes-bitset-simple.pl line 4.
Длинный список директорий после слов @INC contains:
и есть
путь поиска модуля (он завершается, как видим, текущей директорией
.
).
Продумывая интерфейс класса, следует ответить на вопрос: какие методы должен
предоставлять класс своим пользователям (то есть программистам, использующим
класс). Объектами класса являются ограниченные множества целых неотрицательных
чисел. С таким множеством можно делать следующие вещи: добавлять число,
удалять число, проверять, является ли число элементом множества. Для целей
отладки (да и учебных целях тоже) было бы полезно добавить метод, возвращающий
human-readable (то есть понятное
человеку) строковое представление множества. Для рассмотренного ранее множества
простых чисел этот метод должен возвращать строку
{2,3,5,7,11,13,17,19,23,29,31}
.
Итак, для объекта класса BitSetSimple
нужно определить
следующие методы:
add($number
)
Добавляет в множество число
.
$number
delete($number
)
Удаляет из множества число
.
$number
toString()
Возвращает human-readable строковое представление множества.
get($number
)
Возвращает истинное значение, если число
принадлежит множеству, иначе
возвращает ложное значение.
$number
Поскольку добавление/удаление числа означает установку/очистку некоторого бита, есть резон реализовать соответствующие методы:
set($bitNumber
, $value
)
Устанавливает или очищает бит с номером
в зависимости
от логического значения $bitNumber
.
Английское слово set в имени метода
употребляется не в значении «множество», а в значении «установить» (это слово
имеет очень много значений).
$value
Тогда процедуры add
и delete
легко
реализовать как вызовы процедуры set
, при котором второй
параметр равен соответственно 1
или
0
.
Наконец, следует определить конструктор:
new()
Создаёт и возвращает новый объект — пустое множество.
Библиотечные возможности языка Perl не требуют, чтобы библиотечный модуль содержал определение класса. Это может быть и набор определений переменных и процедур, не являющихся соответственно данными и методами некоторого класса. Однако раз уж мы выбрали объектно-ориентированный стиль программирования, нужно соответствовать.
Чтобы показать, что модуль содержит определения методов класса
BitSetSimple
, его текст нужно начать с команды
Perlpackage BitSetSimple;
(package [ˈpækıdʒ] по английски — пакет).
Завершить текст модуля нужно командой
Perlreturn 1;
Значение, возвращаемое оператором return
, означает
успешность или неуспешность загрузки пакета. В некоторых случаях при загрузке
пакета могут произойти неполадки, и таким образом пакет может сообщить
загружающей программе об этом, возвратив значение 0
.
В нашем простом случае неполадок не предвидится, поэтому мы возвращаем истинное
значение.
Место между package и return заполняется определениями методов:
Perlsub new() { … } sub get($) { … } sub set($$) { … } sub add($) { … } sub delete($) { … } sub toString() { … }
Обратите внимание на доллары в скобках после имён методов. Это так называемые
прототипы методов, которые указывают, сколько параметров может принимать метод
и какого вида. Например, set($$)
означает, что
при вызове метода $bitSet->set
должны передаваться два
скалярных параметра (не считая скрытого параметра
), иначе программа не
заработает. Использование прототипов делает программирование более строгим,
а ошибки программирования, связанные с неверным использованием параметров
метода, вскроются не во время выполнения программы, а во время компиляции
(без прототипов такие ошибки могут и не открыться). Подробное изучение
прототипов не входят в наши планы.
$bitSet
В примере с классом Animal
объект имел сложную
внутреннюю структуру, поэтому уместно было представлять его как ссылку
на ассоциативный массив. Поскольку множество будет представляться с помощью
всего лишь одной строки, естественно было бы считать объект ссылкой на такую
строку. Сразу после создания объекта эта строка пустая.
Конструктор класса, как и раньше, принимает в переменную
$class
имя класса, определяет переменную — пустую строку,
затем возвращает ссылку на эту строку, «надписанную» при помощи
bless
:
Perlsub new() { my $class=shift; my $string=''; my $self=\$string; return bless $self, $class; }
Мы, русскоязычные люди, привыкли считать, что символы (байты) в строках нумеруются слева направо, так, как мы их пишем. Биты в байтах, напротив, принято нумеровать справа налево, так же, как и разряды в десятичных числах (в сущности, байты и есть восьмизначные двоичные числа). Но все эти традиции — всего лишь условность. Будь нашим родным языком арабский или иврит, наше представление о порядке символов в строках было бы иным. Порядок битов в байте тоже вещь относительная: стоит перевернуть системный блок компьютера, или же самому встать на голову (попробуйте!), как биты в каждом байте изменят нумерацию на противоположную.
Однако это наблюдение вынуждает нас скорректировать представления о битовом массиве. Следует отразить каждый байт относительно его середины, и тогда следующая четырёхбайтная строка будет представлять собой рассмотренное ранее множество первых одиннадцати простых чисел:
0 │1 │2 │3 номера байтов в строке 10101100│00101000│10001010│10100000 76543210│76543210│76543210│76543210 номера битов в байтах
Повлияет ли это на наши планы? Ничуть.
Особенностью реализации битового массива на базе строки является то, что общее количество бит кратно восьми, и с этим ничего поделать нельзя. Это не проблема: лишние биты будут всё равно очищены. По мере добавления чисел в множество в строку справа будут добавляться байты, при удалении чисел последние (правые) байты будут удаляться, если они полностью обнулятся. Таким способом автоматически будет поддерживаться минимально необходимая длина строки, что сократит расход памяти за счёт некоторого замедления работы.
Сначала научимся по индексу бита в битовом массиве определять номер того байта в строке, который содержит -й бит, и положение бита в этом байте. Это несложно: (целочисленное частное при делении на ), (остаток от деления на ).
Встроенная процедура substr
поможет нам извлекать
из строки символ под номером $x
:
Perl$char=substr($string, $x, 1); в переменной$char
окажется подстрока строки$string
длины1
, начинающаяся с позиции$x
, то есть как раз$x
-й символ
Но символ в языке Perl — это ещё не байт. Превратить символ в байт можно
с помощью оператора ord
. Например,
Perl$byte=ord 'Q'; в переменной$byte
окажется число81
Обратное преобразование байтов в символы осуществляется оператором
chr
:
Perl$char=chr 82; в переменной$char
окажется символ'R'
Процедура substr
позволяет также заменить заданную
подстроку в строке на другую. Для этого при вызове нужно добавить четвёртый
аргумент — строку, на которую следует заменить заданную подстроку:
Perlsubstr($string, $x, 1, 'S'); теперь в строке$string
на$x
-ом месте будет символ'S'
Теперь самое время выяснить, как проверить, установлен ли в данном байте
$byte
бит с данным номером или нет. Для этого имеется
стандартный приём. Сначала подготовим вспомогательный байт
$mask
— так называемую маску. В маске должен быть установлен
единственный бит — с номером $y
, остальные биты очищены.
Затем выполняем с байтами $byte
и $mask
операцию побитового «И». Результатом операции побитового «И» над двумя байтами
будет байт, каждый бит в котором получается в результате операции «И»
над битами с теми же номерами в байтах-операндах. В Perl оператор побитового
«И» обозначается &. Если один из операндов операции
побитового «И» является маской, в которой установлен лишь один бит с номером
$y
, в результате может получиться или байт, равный маске,
или полностью нулевой. Нижеследующие примеры показывают, как проверить
состояние битов №№ 3 и 4 в байте 01001010
с помощью масок:
╭────── проверяемый бит ▼ 01001010 байт$byte
00001000 байт$mask
──────── 00001000 результат операции$byte & $mask
╭─────── проверяемый бит ▼ 01001010 байт$byte
00010000 байт$mask
──────── 00000000 результат операции$byte & $mask
Как же приготовить маску с единственным установленным битом № ? Можно взять выражение
.
Однако у нас есть большое подозрение, что это решение будет далеко не самым
эффективным в смысле быстродействия. Оператор ** возведения
в степень слишком универсален, и умеет возводить в различные (не только целые
неотрицательные) степени различные числа, не только двойку. Лучше
воспользоваться оператором <<
битового сдвига влево: выражение $byte<<$y
возвращает байт, у которого все биты сдвинулись влево на $y
позиций. Приводим иллюстрацию битового сдвига влево с байтом
$byte
, имеющим значение 01001010
, на три
позиции:
01001010 исходный байт$byte
01001010◄◄◄ сдвигаем биты на три позиции влево ╳╳╳01010000 три самых левых бита (вышедшие за левую границу байта) отбрасываются, а три самых правых бита очищаются ─────────── 01010000 результат операции$byte<<3
Если применить левый сдвиг на $y
позиций к единичному байту
(значение 00000001
), получится как раз байт со значением
.
Это байт, в котором установлен лишь бит № , что и требуется. Таким образом, выражение
1<<$y
даёт более быстрый способ возвести
двойку в неотрицательную степень $y
, чем 2**$y
.
Совершенно аналогично определяется операция >>
правого сдвига. Проиллюстрируем её на примере всё того же байта
01001010
и правого сдвига на четыре позиции:
01001010 исходный байт$byte
►►►►01001010 сдвигаем биты на четыре позиции вправо 00000100╳╳╳╳ четыре самых правых бита (вышедшие за правую границу байта) отбрасываются, а четыре самых левых бита очищаются ──────────── 00000100 результат операции$byte>>4
Операции левого и правого байтовых сдвигов дают альтернативный способ проверить состояние бита № . Сначала сдвигаем байт вправо на позиций, а затем влево на позиций:
╭────── проверяемый бит №$y
▼ 01001010 исходный байт$byte
╭─── проверяемый бит ►►► ▼ 00001001 результат операции$byte>>$y
╭────────── проверяемый бит ▼◄◄◄◄◄◄◄ 10000000 результат операции($byte>>$y)<<7
Или наоборот, сначала сдвигаем влево на позиций, а затем вправо на позиций:
╭────── проверяемый бит №$y
▼ 01001010 исходный байт$byte
╭────────── проверяемый бит ▼ ◄◄◄◄ 10100000 результат операции$byte<<(7-$y)
╭─── проверяемый бит ►►►►►►►▼ 00000001 результат операции($byte<<(7-$y))>>7
В обоих случаях значения выражений ($byte>>$y)<<7
или ($byte<<(7-$y))>>7
будет ненулевым
(истинным) тогда и только тогда, когда $y
-й бит в байте
$byte
установлен. Первый способ предпочтительней, так как не
требует дополнительного вычитания.
Суммируем все наши соображения насчёт проверки состояния
$y
-го бита в байте $byte
. Любое
из выражений
$byte&(1<<$y)
($byte>>$y)<<7
($byte<<(7-$y))>>7
истинно, только если бит установлен.
Теперь пора выяснить, как установить или очистить $y
-й бит
в байте $byte
. Тут нам опять поможет битовая маска. Если
с байтом и маской выполнить операцию |
побитового «ИЛИ», бит будет установлен:
╭─────── устанавливаемый бит ▼ 01001010 байт$byte
00010000 байт$mask
──────── 01011010 результат операции$byte|$mask
Для очистки бита следует выполнить операцию побитового «И», но не с исходной, а с дополнительной маской. Дополнительная маска — это маска, подвергнутая операции ~ побитовой инверсии. Операция побитовой инверсии меняет состояния всех битов в байте на противоположные:
╭───────── очищаемый бит ▼ 01001010 байт$byte
10111111 байт~$mask
(дополнительная маска) ──────── 00001010 результат операции$byte & ~$mask
Итак, приводим выражения, которые устанавливают
Perl$byte=$byte|(1<<$y);
или очищают
Perl$byte=$byte&~(1<<$y);
$y
-й бит в байте $byte
.
Имеются комбинированные операторы &= и |=, сочетающие соответственно операторы побитового «И» и «ИЛИ» с присваиванием. Поэтому приведённые команды можно записать короче:
Perl$byte|=(1<<$y);
и
Perl$byte&=~(1<<$y);