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

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

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

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

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

00110101000101000101000100000101
0       8       16      24		индексы битов в массиве

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

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

Perl
use BitSetSimple;

% 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.

Perl
package BitSetSimple;

Perl
return 1;

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

Perl
sub 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	номера битов в байтах

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

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

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

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

    ╭──────	проверяемый бит
    ▼
01001010	байт $byte
00001000	байт $mask
────────
00001000	результат операции $byte & $mask

   ╭───────	проверяемый бит
   ▼
01001010	байт $byte
00010000	байт $mask
────────
00000000	результат операции $byte & $mask

   01001010		исходный байт $byte
01001010◄◄◄		сдвигаем биты на три позиции влево
╳╳╳01010000		три самых левых бита (вышедшие за левую границу байта)
				отбрасываются, а три самых правых бита очищаются
───────────
   01010000		результат операции $byte<<3

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

   ╭───────	устанавливаемый бит
   ▼
01001010	байт $byte
00010000	байт $mask
────────
01011010	результат операции $byte|$mask

 ╭─────────	очищаемый бит
 ▼
01001010	байт $byte
10111111	байт ~$mask (дополнительная маска)
────────
00001010	результат операции $byte & ~$mask

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

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

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

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