Нет предела совершенству, и нам есть в каком направлении улучшать класс
BitSetSimple
. Скопируем файл
BitSetSimple.pm
под именем BitSet.pm
и станем вносить изменения в новый файл. Первая же правка состоит в замене
строки
Perluse BitSetSimple;
на
Perluse BitSet;
Было бы неплохо добавить методы для вычисления мощности (количества элементов в множестве), для преобразования множества в массив, содержащий его элементы. Не помешали бы методы для вычисления объединения и пересечения с другим множеством.
Обсуждая класс BitSetSimple
, мы сознательно скрыли
от читателя страшную правду: можно было бы обойтись без масок, без побитовых
операций, без всех этих $byte|=(1<<$y)
и
$byte&=~(1<<$y)
. Потому что
в Perl есть встроенная процедура vec
. Процедура работает
с битовыми строками и рассматривает их как массив, состоящий из групп битов.
На размер группы накладываются следующие ограничения: он должен быть степенью
двойки от 1 до 32 (или 64, если компьютер, на котором будет работать Perl,
поддерживает такое). Процедура vec
, таким образом,
принимает три параметра: битовую строку, индекс в массиве и размер битовой
группы.
Поясним сказанное на примере. Для этого рассмотрим строку 'bit
set'
как битовую:
b
│i
│t
││
s
│e
│t
символы строки 0 │1 │2 │3 │4 │5 │6 номера байтов в строке 01000110│10010110│00101110│00000100│11001110│10100110│00101110 98 │105 │116 │32 │115 │101 │116 числовые значения байтов
Байты — это группы, состоящие из восьми бит каждая. Ту же самую строку можно рассмотреть как массив групп по 32 бита:
0 │1 номера битовых групп в строке 01000110100101100010111000000100│110011101010011000101110???????? 1651078164 │1936028672 числовые значения битовых групп
Последняя, неполная группа дополняется справа нулевыми битами до нужного размера в 32 бита.
При 4-битных группах получим следующее:
0 │1 │2 │3 │4 │5 │6 │7 │8 │9 │10 │11 │12 │13 номера битовых групп в строке 0100│0110│1001│0110│0010│1110│0000│0100│1100│1110│1010│0110│0010│1110 2 │6 │9 │6 │4 │7 │0 │2 │3 │7 │5 │6 │4 │7 числовые значения битовых групп
Примечание | |
---|---|
Обратите внимание, что при вычислении числовых значений битовых групп, имеющих размер меньше восьми, порядок битов в каждой группе следует мысленно заменить на противоположный. Например, значением группы с индексом 5 будет не , как можно было бы ожидать, а . |
Процедура vec
как раз позволяет извлечь из битовой строки
группу с заданным номером и заданного размера. Таким образом, выражение vec('bit set', 3, 8)
возвратит число
32
, vec('bit set', 2, 4)
—
9
, а vec('bit set', 0, 32)
даст 1651078164
. Если индекс группы слишком велик (группа
с таким номером отсутствует в битовой строке), vec
возвращает 0
, как если бы перед вызовом этой процедуры
битовая строка была бы дополнена нулевыми битами до необходимого размера. Так
будет, к примеру, при вызове vec('bit set', 12,
8)
, vec('bit set', 15, 4)
или vec('bit set', 56, 1)
.
Процедура vec
позволяет не только извлекать числовое
значение битовой группы, но и заменять его. Эта процедура ― одна из немногих,
которую можно использовать слева от оператора присваивания (при этом, конечно,
требуется, чтобы сама битовая строка могла использоваться слева
в присваивании):
Perlvec('bit set', 2, 8)=86; попытка получить строку'biT set'
завершилась неудачей: константу'bit set'
менять нельзя! $bitString='bit set'; так будет правильно, vec($bitString, 21, 1)=0; переменная$bitString
теперь содержит'biT set'
… vec($bitString, 53, 1)=0; …а теперь'biT seT'
Что особенно приятно, присваивание значения группе, отсутствующей в битовой строке (имеющей слишком большой индекс), не приводит к ошибке. Строка дополняется необходимым количеством нулевых байтов, чтобы группа с заданным индексом в неё поместилась.
Конечно, для наших нужд потребуется извлекать или заменять в битовой строке группы, состоящие из одного бита.
Учитывая всё сказанное, мы можем перепрограммировать методы
get
и set
, которые ответственны
за манипуляции с битами:
Perlsub get($) { my $self=shift; my $i=shift; return vec($$self, $i, 1); } sub set($$) { my $self=shift; my $i=shift; my $value=shift; vec($$self, $i, 1)=$value; chop $$self while length $$self and (substr $$self, -1) eq "\0"; }
Мы полагаем, что этим добились не только большей краткости и ясности, но и повысили быстродействие этих методов, поскольку встроенные процедуры языка Perl, реализованные на языке C, должны работать быстрее битовых выражений с масками.
Имеющийся у нас конструктор создаёт новое пустое множество. Можно его доработать, чтобы он принимал дополнительные параметры — список чисел, которые добавляются в множество сразу после его создания. Тогда вместо
Perlmy $sieve=BitSet->new; for(my $i=2; $i<=$n; $i++) { $sieve->add($i); }
можно было бы просто написать
Perlmy $sieve=BitSet->new(2..$n);
Кроме того, ничего не мешает подправить определения методов
add
и delete
таким образом, чтобы они
могли добавлять или удалять не одно число, а сразу несколько. Начнём именно
с этого. Изменения в коде совершенно очевидны:
Perlsub add(@) { my $self=shift; $self->set($_, 1) for(@_); } sub delete(@) { my $self=shift; $self->set($_, 0) for(@_); }
Обратите внимание на изменившийся прототип этих методов — (@) вместо ($). Этот прототип позволяет принимать вместо единственного дополнительного скалярного параметра список скаляров.
Теперь воспользуемся обновлённым методом add
в обновлённом
конструкторе:
Perlsub new() { my $class=shift; my $string=''; my $self=bless \$string, $class; $self->add(@_); return $self; }
Ссылка на битовую строку становится объектом только после вызова
bless
, и только с этого момента возможен вызов метода
для объекта. Нет противопоказаний к тому, чтобы вызывать методы для вновь
созданного объекта уже в конструкторе.
Дополним класс удобным методом toArray
, возвращающим
список элементов множества в порядке возрастания. За основу возьмём код
из старой версии метода toString
, после чего перепишем
определение toString
так, чтобы в нём использовался метод
toArray
:
Perlsub toArray() { my $self=shift; my @array; for(my $i=0; $i<8*length $$self; $i++) { push @array, $i if $self->get($i); } return @array; } sub toString() { return '{'.(join ',', shift->toArray).'}'; }
Использование join
в определении
toString
избавляет нас от необходимости хитрить
с последней запятой: запятые будут вставлены между числами.
Имея в распоряжении метод toArray
, несложно получить
мощность множества. Нужно лишь использовать вызов этого метода в скалярном
контексте, например, в присваивании значения скалярной переменной:
Perl$cardinality=$bitSet->toArray;
Ничего не стоит определить новый метод cardinality
,
который просто вызывает toArray
и возвращает длину
получившегося списка:
Perlsub cardinality() { return 0+shift->toArray; }
Поскольку оператор return
может работать и со скалярами, и
со списками, следует принудительно поместить вызов toArray
в скалярный (числовой) контекст при помощи маленькой хитрости 0+shift->toArray
.
Как мы знаем, копирование ссылки не приводит к копированию того значения, на которое ссылка указывает. Поэтому битовая строка, ссылка на которую была скопирована, остаётся той же самой, а объект-копия, полученный таким способом, продолжает жить жизнью своего оригинала:
Perlmy $bitSet=BitSet->new(1, 2, 3); my $bitSetCopy=$bitSet; копируется ссылка на ту же самую битовую строку $bitSetCopy->add(4, 5); теперь и оригинал, и копия содержат(1, 2, 3, 4, 5)
Уместней было бы называть такой новый объект не копией, а клоном своего прототипа.
Если требуется получить настоящую копию, требуется создать новый объект-ссылку,
указывающий на копию исходной битовой строки. Запрограммируем метод
copy
, который создаёт объект-копию. Вот пример
использования этого метода:
Perlmy $bitSet=BitSet->new(1, 2, 3); my $bitSetCopy=$bitSet->copy; создаётся новый объект с той же самой битовой строкой $bitSetCopy->add(4, 5); теперь копия содержит(1, 2, 3, 4, 5)
, но оригинал остался без изменений
Один из способов сделать это — создать и возвратить новое множество, заполненное теми же числами, которые имеются на данный момент в множестве-оригинале:
Perlsub copy() { return BitSet->new(shift->toArray); }
Однако такой подход связан с выполнением многих лишних действий: преобразование исходной битовой строки в список, и преобразование списка чисел в новую битовую строку. Мы поступим иначе: создадим новое пустое множество, и «пересадим» (хирургическим путём) копию исходной битовой строки на новое место:
Perlsub copy() { my $self=shift; my $copy=BitSet->new(); $$copy=$$self; return $copy; }
Реализация методов для определения минимального, максимального элемента и суммы
всех элементов множества совершенно прямолинейна. При поиске минимума
и максимума будет найден номер первого установленного бита, ближайшего
соответственно к началу и к концу битовой строки. Из-за того, что при изменении
множества мы всегда удаляем нулевые октеты, если они появятся, в конце строки,
цикл для поиска максимума прокрутится не более восьми раз. По этой же причине
цикл в min
и max
для непустого
множества найдёт установленный бит и будет прерван оператором
return
. Но что же должны возвратить методы
min
и max
для пустого множества?
Можно возвращать неопределённое значение (undef
),
поскольку, строго говоря, минимум и максимум в числовом множестве — это элемент
множества, который меньше или равен (соответственно, больше или равен) всех
элементов множества. В пустом множестве элементов нет, поэтому возвращать
как бы нечего.
Perlsub min() { my $self=shift; for(my $i=0; $i<8*length $$self; $i++) { return $i if $self->get($i); } } sub max() { my $self=shift; for(my $i=8*(length $$self)-1; $i>=0; $i--) { return $i if $self->get($i); } } sub sum() { my $self=shift; my $sum=0; $sum+=$_ for $self->toArray; return $sum; }
Метод isEmpty
, возвращающий логическое значение «да» или
«нет» в зависимости от пустоты/непустоты множества можно было бы реализовать
с помощью выражения $self->cardinality==0
.
Однако как только мы вспомним, как именно был запрограммирован метод
cardinality
, мы откажемся от его использования, чтобы
избежать цикла. Есть гораздо более эффективное решение:
Perlsub isEmpty() { my $self=shift; return $$self eq ''; }