Примеры

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

Набор умений будет достаточно скромным. Животное может назвать себя и подать голос (процедура say). Конечно, объект «животное» должен содержать соответствующую информацию. Её разумно закладывать в каждое животное на этапе создания:

my $cat=Animal->new('Кошка', 'Мяу');
my $dog=Animal->new('Собака', 'Гав');
my $pig=Animal->new('Свинья', 'Хрю');
my $ram=Animal->new('Баран', 'Бее');
my $cow=Animal->new('Корова', 'Муу');
my $horse=Animal->new('Лошадь', 'И-го-го';)

после чего готовые к употреблению животные могут представиться:

$cat->say;
$dog->say;
$pig->say;
$ram->say;
$cow->say;
$horse->say;

На экране при этом должно появиться:

Первым делом необходимо обозначить, что все определяемые процедуры относятся к классу животных. Для этого поместим в программу команду package Animal;. Процедура new предназначена для создания новых животных; это так называемый конструктор объектов. Эта процедура должна получить в качестве параметра название класса (Animal). Второй и третий параметры, получаемые процедурой new, это название каждого конкретного животного, и звук, издаваемый им. Эти данные помещаются соответственно в поля name и sound безымянного ассоциативного массива, ссылка на который помещается в переменную $self. Эта ссылка и есть животное. Команда bless (встроенная в Perl) помечает, что это не просто ссылка на хэш, а объект класса Animal. Никаких других действий bless не совершает, только возвращает ссылку с пометкой, после чего та возвращается из конструктора оператором return.

package Animal;

sub new
{
	my $class=shift;
	my $self={name=>shift, sound=>shift};
	return bless $self, $class;
}

Следующая наша задача — определение процедуры say. Определение совсем простое:

sub say
{
	my $self=shift;
	print "Здравствуйте, я $self->{name}. $self->{sound}!\n";
}

На этом определение класса Animal завершено. При желании наших животных можно снабдить и другими навыками. Тут чувствуешь себя Творцом!

Позволим животным проявить себя. Но прежде нужно указать, что определение класса животных закончилось и далее идёт основная часть программы. Для этого помещаем команду

package main;

Класс main который подразумевается, если явным образом не указан другой. Поскольку другой в нашем случае указан, это строчка необходима.

package main;

my $cat=Animal->new('Кошка', 'Мяу');
my $dog=Animal->new('Собака', 'Гав');
my $pig=Animal->new('Свинья', 'Хрю');
my $ram=Animal->new('Баран', 'Бее');
my $cow=Animal->new('Корова', 'Муу');
my $horse=Animal->new('Лошадь', 'И-го-го');

$_->say for $cat, $dog, $pig, $ram, $cow, $horse;

Теперь зададимся вопросом: почему наша процедура say при вызове вроде бы не получает параметров, хотя определена в расчёте на один параметр (в её теле есть по одному вызову shift). Естественно, этот самый параметр — то, что стоит слева от стрелки в вызовах этих процедур, объект, к которому процедуры относятся. Объект при вызовах вроде $cow->say вставляется на первое место в список параметров процедуры, потеснив вправо другие (как будто он вставлен при помощи unshift). Таким образом, вызов $cow->say эквивалентен say($cow), но если мы напишем именно так, компилятор Perl будет в затруднении. Не найдя в классе main определённой процедуры say, компилятор поругается и завершит свою работу. И если нам так уж хочется писать в традиционном стиле, придётся указать явно, для какого класса вызывается say: Animal::say($cow).

Снова вернёмся к задаче поиска простых чисел.

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

Начнём работу с последовательностью. Возьмём из неё первое число — это двойка. Это простое число. Прикрутим к последовательности фильтр, который задерживает чётные числа, то есть делящиеся на два. Агрегат, состоящий из последовательности с прикрученным к ней фильтром, сам становится источником чисел, но теперь уже только нечётных. Первое число, которое пройдёт через фильтр, это тройка (простое). Прикрутим к агрегату добавочный фильтр, который станет пропускать все числа, кроме делящихся на три. Следующее число, которое выдаст агрегат с двумя фильтрами, это пять (простое!). Добавим новый фильтр, пропускающий числа, не делящиеся на пять.

Будем проделывать подобные действия до бесконечности, или же до тех пор, пока очередное найденное простое число не превысит некоторого порога. Движение нескольких первых чисел, получаемых из последовательности, показано на рисунке 38.1. «Прохождение простых и составных чисел через фильтры». Простые числа (показаны зелёным цветом) добавляют в цепочку новый фильтр, тот самый, на который указывает стрелка. Составные числа (красные) задерживаются фильтром (в соответствующем месте обозначен тупик).

Рисунок 38.1. Прохождение простых и составных чисел через фильтры

Приступаем к программированию. Ключевая роль в программе отведена последовательности чисел и фильтрам. Моделью последовательности будет класс «Последовательность» (Sequence), в программе он будет представлен единственным объектом. Для фильтров, которых будет много, запрограммируем класс «Фильтр» (Filter).

Единственное умение и последовательности, и фильтра — выдавать по запросу следующее число. В обоих классах, таким образом, следует определить методы get, точнее говоря, Sequence::get и Filter::get. Разумеется, нужны будут и конструкторы new.

Теперь пора подумать, какие данные будут заключены в объектах обоих классов.

Последовательность должна помнить то число, которое будет выдано при следующем запросе get. Никакой другой информации не потребуется. Но мы не можем сделать числовую скалярную переменную объектом: Perl требует, чтобы объект был ссылкой на что-то. Пускай объект класса Sequence будет ссылкой на анонимную скалярную переменную, в которой хранится очередное число.

Что касается объектов Filter, они должны знать, откуда в них будут поступать числа, подлежащие фильтрации. Кроме того, фильтр помнит то самое число, кратные которого он не должен пропускать. Объект Filter полностью описывается двумя свойствами. Назовём их source (источник) и p (число). Если объект задаётся набором именованных свойств, подходящей моделью для него будет ссылка на анонимный ассоциативный массив.

Начнём программу с определения класса Sequence и его конструктора:

package Sequence;

sub new
{
	my $n=2;
	return bless \$n, shift;
}

Здесь нет ничего принципиально нового по сравнению с конструктором класса Animal, разве что этот конструктор без параметров, и что создаваемый объект будет ссылкой на скалярную переменную. Чуть раньше мы упоминали ссылку на анонимную переменную, но здесь это переменная $n, и она отнюдь не анонимная. Однако переменная $n объявлена как локальная, и её имя будет забыто сразу же, как только завершится вызов конструктора, после чего переменная станет по-настоящему анонимной. Анонимность не сделает переменную недоступной, доступ к ней будет осуществляться по ссылке, возвращаемой из конструктора.

Определение метода get завершит работу над классом Sequence. Нам кажется, что комментарии будут лишними:

sub get
{
	my $self=shift;
	return $$self++;
}

Конструктор класса Filter не сулит ничего нового по сравнению с конструктором Animal::new. Он принимает два параметра (не считая скрытого, имени класса), и создаёт ссылку на ассоциативный массив, в котором эти два параметра станут значениями, соответствующими ключам source и p:

package Filter;

sub new($)
{
	my $class=shift;
	return bless {source=>shift, p=>shift}, $class;
}

Метод get, несмотря на лаконичность определения, заслуживает более подробного разговора. Можно обращаться за очередным числом в цикле к предыдущему фильтру в цепочке (вызывая $self->{source}->get) до тех пор, пока полученное число не перестанет делиться на $self->{p}. Как только такое число будет получено, оно тут же возвращается:

sub get
{
	my $self=shift;
	while()
	{
		my $n=$self->{source}->get;
		return $n if $n % $self->{p};
	}
}

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

Если наше утверждение верно, перепишем метод get по-новому:

sub get
{
	my $self=shift;
	my $n=$self->{source}->get;
	return ($n % $self->{p})? $n: $self->{source}->get;
}

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

Метод Filter::get — рекурсивный. Для всех фильтров, за исключением самого первого, добавленного в цепочку (того, который пропускает лишь нечётные числа) вызов этого метода приводит к вызову того же самого метода, но для предыдущего фильтра (для самого первого вызывается Sequence::get. Глубина рекурсии растёт по мере добавления фильтров. Perl, как мы знаем (см. раздел «Рекурсия»), не любит, когда глубина рекурсии достигает 100, и выдаёт предупреждение при каждом вызове, где глубина превышает этот порог. Это произойдёт после первой сотни найденных простых чисел, и, следовательно, после первой сотни созданных и соединённых в цепочку фильтров:

% ./primes-filtering.pl 600 2 3 5 7 11 13 17 19 23 29 31 37 521 523 541 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 38. Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 547 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 557 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 563 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 569 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 571 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 577 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 587 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 593 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37. 599 Deep recursion on subroutine "Filter::get" at ./primes-filtering.pl line 37.

Несмотря на предупреждения, программа сохранит работоспособность ещё долго: простые числа не настолько часто встречаются, и мы за разумное время вряд ли сумеем выстроить слишком длинную цепочку. Предупреждения появятся при использовании команды use warnings; или в самом начале файла с программой, или внутри определения класса, где имеется рекурсивная процедура. Иными словами, область действия команды use warnings; распространяется или на всю программу, или на определение класса, в зависимости от места её размещения. Если мы начнём программу с инструкции use warnings;, можно затем выборочно отключить предупреждения, связанные с рекурсией, командой no:

Perl
use warnings; no warnings 'recursion';

Именно так мы и поступим.

Мы не распрощались с поиском простых чисел. В этом разделе разобран рекурсивный алгоритм поиска, использующий объектно-ориентированное программирование. В главе 39. «Битовая реализация числового множества» появится ещё одна программа, решающая ту же самую задачу. В основе программы будет уже известный алгоритм — решето Эратосфена, однако вместо массива для представления решета будет использован особый объект — битовое множество. Новый подход сулит значительную экономию памяти для хранения решета не в ущерб быстродействию программы, и, главное, даёт повод поговорить о многих важных вещах.

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