Глава 39. Битовая реализация числового множества :: Дальнейшие улучшения класса BitSetSimple

Дальнейшие улучшения класса `BitSetSimple`
	Глава 39. Битовая реализация числового множества

Дальнейшие улучшения класса `BitSetSimple`

Нет предела совершенству, и нам есть в каком направлении улучшать класс BitSetSimple. Скопируем файл BitSetSimple.pm под именем BitSet.pm и станем вносить изменения в новый файл. Первая же правка состоит в замене строки

Perl
use BitSetSimple;

на

Perl
use BitSet;

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

Использование встроенной процедуры `vec`

Обсуждая класс 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 будет не $14 = 0 \cdot 2^{0} + 1 \cdot 2^{1} + 1 \cdot 2^{2} + 1 \cdot 2^{3}$ , как можно было бы ожидать, а $7 = 1 \cdot 2^{0} + 1 \cdot 2^{1} + 1 \cdot 2^{2} + 0 \cdot 2^{3}$ .

Примечание

Обратите внимание, что при вычислении числовых значений битовых групп, имеющих размер меньше восьми, порядок битов в каждой группе следует мысленно заменить на противоположный. Например, значением группы с индексом 5 будет не $14 = 0 \cdot 2^{0} + 1 \cdot 2^{1} + 1 \cdot 2^{2} + 1 \cdot 2^{3}$ , как можно было бы ожидать, а $7 = 1 \cdot 2^{0} + 1 \cdot 2^{1} + 1 \cdot 2^{2} + 0 \cdot 2^{3}$ .

Процедура 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 позволяет не только извлекать числовое значение битовой группы, но и заменять его. Эта процедура ― одна из немногих, которую можно использовать слева от оператора присваивания (при этом, конечно, требуется, чтобы сама битовая строка могла использоваться слева в присваивании):

Perl
vec('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, которые ответственны за манипуляции с битами:

Perl
sub 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, должны работать быстрее битовых выражений с масками.

Улучшения в конструкторе

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

Perl
my $sieve=BitSet->new;
for(my $i=2; $i<=$n; $i++)
{
	$sieve->add($i);
}

можно было бы просто написать

Perl
my $sieve=BitSet->new(2..$n);

Кроме того, ничего не мешает подправить определения методов add и delete таким образом, чтобы они могли добавлять или удалять не одно число, а сразу несколько. Начнём именно с этого. Изменения в коде совершенно очевидны:

Perl
sub add(@)
{
	my $self=shift;
	$self->set($_, 1) for(@_);
}

sub delete(@)
{
	my $self=shift;
	$self->set($_, 0) for(@_);
}

Обратите внимание на изменившийся прототип этих методов — (@) вместо ($). Этот прототип позволяет принимать вместо единственного дополнительного скалярного параметра список скаляров.

Теперь воспользуемся обновлённым методом add в обновлённом конструкторе:

Perl
sub new()
{
	my $class=shift;
	my $string='';
	my $self=bless \$string, $class;
	$self->add(@_);
	return $self;
}

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

Преобразование множества в список чисел

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

Perl
sub 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 и возвращает длину получившегося списка:

Perl
sub cardinality()
{
	return 0+shift->toArray;
}

Поскольку оператор return может работать и со скалярами, и со списками, следует принудительно поместить вызов toArray в скалярный (числовой) контекст при помощи маленькой хитрости 0+shift->toArray.

Создание копий

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

Perl
my $bitSet=BitSet->new(1, 2, 3);
my $bitSetCopy=$bitSet;		копируется ссылка на ту же самую битовую строку
$bitSetCopy->add(4, 5);		теперь и оригинал, и копия содержат (1, 2, 3, 4, 5)

Уместней было бы называть такой новый объект не копией, а клоном своего прототипа.

Если требуется получить настоящую копию, требуется создать новый объект-ссылку, указывающий на копию исходной битовой строки. Запрограммируем метод copy, который создаёт объект-копию. Вот пример использования этого метода:

Perl
my $bitSet=BitSet->new(1, 2, 3);
my $bitSetCopy=$bitSet->copy;	создаётся новый объект с той же самой битовой строкой
$bitSetCopy->add(4, 5);			теперь копия содержит (1, 2, 3, 4, 5),
								но оригинал остался без изменений

Один из способов сделать это — создать и возвратить новое множество, заполненное теми же числами, которые имеются на данный момент в множестве-оригинале:

Perl
sub copy()
{
	return BitSet->new(shift->toArray);
}

Однако такой подход связан с выполнением многих лишних действий: преобразование исходной битовой строки в список, и преобразование списка чисел в новую битовую строку. Мы поступим иначе: создадим новое пустое множество, и «пересадим» (хирургическим путём) копию исходной битовой строки на новое место:

Perl
sub copy()
{
	my $self=shift;
	my $copy=BitSet->new();
	$$copy=$$self;
	return $copy;
}

Минимальный и максимальный элементы, сумма

Реализация методов для определения минимального, максимального элемента и суммы всех элементов множества совершенно прямолинейна. При поиске минимума и максимума будет найден номер первого установленного бита, ближайшего соответственно к началу и к концу битовой строки. Из-за того, что при изменении множества мы всегда удаляем нулевые октеты, если они появятся, в конце строки, цикл для поиска максимума прокрутится не более восьми раз. По этой же причине цикл в min и max для непустого множества найдёт установленный бит и будет прерван оператором return. Но что же должны возвратить методы min и max для пустого множества? Можно возвращать неопределённое значение (undef), поскольку, строго говоря, минимум и максимум в числовом множестве — это элемент множества, который меньше или равен (соответственно, больше или равен) всех элементов множества. В пустом множестве элементов нет, поэтому возвращать как бы нечего.

Perl
sub 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, мы откажемся от его использования, чтобы избежать цикла. Есть гораздо более эффективное решение:

Perl
sub isEmpty()
{
	my $self=shift;
	return $$self eq '';
}


Готовая программа (предварительная версия)		Глава 40. Тетрис

Дальнейшие улучшения класса BitSetSimple

Использование встроенной процедуры vec