perl => pb11

Глава 11 Ссылки и записи


    * введение
    * 11.1. Ссылки на массивы
    * 11.2. Создание хэшей массивов
    * 11.3. Получение ссылок на хэши
    * 11.4. Получение ссылок па функции
    * 11.5. Получение ссылок на скаляры
    * 11.6. Создание массивов ссылок на скаляры
    * 11.7. Применение замыканий вместо объектов
    * 11.8. Создание ссылок на методы
    * 11.9. Конструирование записей
    * 11.10. Чтение и сохранение записей в текстовых файлах.
    * 11.11. Вывод структур данных
    * 11.12. Копирование структуры данных
    * 11.13. Сохранение структур данных па диске
    * 11.14. Устойчивые структуры данных
    * 11.15. Программа: бинарные деревья 

Ссылки и записи

Введение


В Perl существуют три основных типа данных: скалярные величины, массивы и хэши. Конечно, многие программы удается написать и без сложных структур данных, но обычно простых переменных и списков все же оказывается недостаточно. Три встроенные структуры данных Perl в сочетании со ссылками позволяю! строить сколь угодно сложные и функциональные структуры данных - те самыг записи, которых так отчаянно не хватало в ранних версиях Perl. Правильно выбирая структуру данных и алгоритм, вы иногда выбираете между элегантпои программой, которая быстро справляется со своей задачей, и убогой поделкой, ра ботающей с черепашьей скоростью и нещадно пожирающей системные ресурсы. Первая часть этой главы посвящена созданию и использованию простых ссылок. Во второй части рассказывается о применении ссылок для создания структур данных более высокого порядка.

Ссылки

Чтобы хорошо понять концепцию ссылок, сначала необходимо разобраться с тем. как в Perl хранятся значения переменных. С любой определенной переменной ассоциируется имя и адрес области памяти. Идея хранения адресов играет для ссылок особую роль, поскольку в ссылке хранятся данные о местонахождении другой величины. Скалярная величина, содержащая адрес области памяти, называется ссылкой. Значение, хранящееся в памяти по данному адресу, называется субъектом (referent) (рис. 11.1). Субъект может относиться к одному из встроенных типов данных (скалярная величина, массив, хэш, ссылка, код или глоб) или представлять собой пользовательский тип, основанный на одном из встроенных типов.

Субъекты в Perl типизованы. Это означает, что ссылку на массив нельзя интерпретировать как ссылку на хэш. При подобных попытках инициируется исключение. В Perl не предусмотрен механизм преобразования типов, и это было сделано намеренно. На первый взгляд кажется, что ссылка - обычный адрес с сильной типизацией. На самом деле это нечто большее. Perl берет на себя автоматическое выделение и освобождение памяти (сборку мусора) для ссылок так же, как и для всего остального. С каждым блоком памяти в Perl связан счетчик ссылок, который определяет количество ссылок па данный субъект. Память, используемая субъектом, возвращается в пул свободной памяти процесса лишь при обнулении счетчика ссылок. Тем самым гарантируется, что вы никогда не получите недопустимую ссылку - забудьте об аварийных завершениях и ошибках защиты, часто возникающих при неправильной работе с указателями в С. Освобожденная память передается Perl для последующего использования, но лишь немногие операционные системы возвращают ее себе. Это связано с тем, что в большинстве схем распределения памяти используется стек, а при освобождении памяти в середине стека операционная система не сможет вернуть ее без перемещения всех остальных блоков. Перемещение нарушит целостность указателей и прикончит вашу программу. Чтобы перейти от ссылки к субъекту, снабдите ссылку символом типа для тех данных, к которым вы обращаетесь. Например, если $sref является ссылкой на скалярную величину, возможна следующая запись:
print $$sref; # Выводится скалярная величина, на которую ссылается $sref $$sref =3; # Присваивается субъекту $sref

Для обращения к отдельному элементу массива или хэша, на который у вас имеется ссылка, используется ассоциативный оператор, оператор -> ("стрелка") - например, $rv->[37] или $rv->{"wilma"}. Помимо разыменования ссылок на массивы и хэши, стрелка также применяется при косвенном вызове функций через ссылки - например, $code_ref->("arg1", "arg2") (см. рецепт 11.4). Если вы работаете с объектами, то с помощью стрелки можно вызывать их методы, $object->methodname("arg1", "arg2"), как показано в главе 13 "Классы, объекты и связи". Правила синтаксиса Perl делают разыменование сложных выражений нетриви-1ьной задачей. Чередование правых и левых ассоциативных операторов не рекомендуется. Например, $$х[4] - то же самое, что и $х->[4]; иначе говоря, $х интерпретируется как ссылка на массив, после чего из массива извлекается четвертый элемент. То же самое записывается в виде ${$х}[4]. Если вы имели в виду "взять четвертый элемент @х и разыменовать его в скалярное выражение", воспользуйтесь ${$х[4]}. Старайтесь избегать смежных символов типов ($@%&) вез-.'-. кроме простых и однозначных ситуаций типа %hash = %$hashref. Приведенный выше пример с $$sref можно переписать в виде:
print ${$sref}; # Выводится скалярная величина, на которую ссылается
$sref ${$sref} =3; # Присваивается субъекту $srefНекоторые программисты для уверенности используют только эту форму. Функция ref получает ссылку и возвращает строку с описанием субъекта. Стро ка обычно принимает одно из значений SCALAR, ARRAY, HASH или CODE, хотя иног-да встречаются и другие встроенные типы GLOB, REF, 10, Regexp и LVALUE. Если re-вызывается для аргумента, не являющегося ссылкой, функция возвращает false При вызове ref для объекта (ссылки, для субъекта которой вызывалась функция bless) возвращается класс, к которому был приписан объект: CGI, IO::Socket или даже
ACME::Widget. Ссылки в Perl можно создавать для субъектов уже определенных или определяемых с помощью конструкций [ ], { } или sub { }. Использовать оператор \ очень просто: поставьте его перед субъектом, для которого создается ссылка. Например, ссылка на содержимое массива @аrrау создается следующим образом:

$rv = \@array;

Создавать ссылки можно даже для констант; при попытке изменить значенш субъекта происходит ошибка времени выполнения:

$р1 = \3.14159;
$$pi =4; # Ошибка

Анонимные данные

Ссылки на существующие данные часто применяются для передачи аргументов функции, но в динамическом программировании они бывают неудобны. Иногда ситуация требует создания нового массива, хэша, скалярной величины или функции, но вам не хочется возиться с именами. Анонимные массивы и хэши в Perl могут создаваться явно. При этом выделяется память для нового массива или хэша и возвращается ссылка на нее:

$aref = [ 3, 4, 5 ]; # Новый анонимный массив
$href = { "how" => "Now", "Brown" => "Cow" }; # Новый анонимный хэш

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

undef $aref;
@$aref = (1, 2, 3);
print $aref;
ARRAY(Ox80c04fO)

Обратите внимание: от undef мы переходим к ссылке на массив, не выполняя фактического присваивания. Perl автоматически создает субъект неопределенной ссылки. Благодаря этому свойству программа может начинаться так:

$а[4][23][53][21] = "fred";
print $a[4][23][53][21];
fred print $a[4][23][53];
ARRAY(Ox81e2494) print $a[4][23];
ARRAY(Ox81e0748) print $a[4];
ARRAY(Ox822cd40)

В следующей таблице перечислены способы создания ссылок для именованных и анонимных скалярных величин, массивов, хэшей и функций. Анонимные тип-глобы выглядят слишком страшно и практически никогда не используются. Вместо них следует применять 10: :Handle->new().

Скалярная величина Массив Хэш Функция
\$scalar \@аггау \%hash \&function
	
\do{my $anon} { СПИСОК } { СПИСОК } sub { КОД }

Отличия именованных субъектов от анонимных поясняются на приведенных далее рисунках. На рис. 11.2 изображены именованные субъекты, а на рис. 11.3 - анонимные. Иначе говоря, в результате присваивания $а = \$Ь переменные $$а и $Ь занимают одну и ту же область памяти. Если вы напишете $$а = 3, значение $Ь станет равно 3.
Все ссылки по определению оцениваются как true, поэтому, если ваша функция возвращает ссылку, в случае ошибки можно вернуть undef и проверить возвращаемое значение следующим 
образом:

$op_cit = cite($ibid) or die "couldn't make a reference"

Оператор undef может использоваться с любой переменной или функцией Perl для освобождения занимаемой ей памяти. Однако не следует полагать, что при вызове undef всегда освобождается память, вызываются деструкторы объектов и т. д. В действительности оператор всего лишь уменьшает счетчик ссылок на 1. Без аргумента undef дает неопределенное значение.

Записи

Ссылки традиционно применялись в Perl для обхода ограничения, согласно которому массивы и хэши могут содержать только скаляры. Ссылки являются скалярами, поэтому для создания массива массивов следует создать массив ссылок на массивы. Аналогично, хэши хэшей реализуются как хэши со ссылками на хэши: массивы хэшей - как массивы ссылок на хэши; хэши массивов - как хэши ссылок на массивы и т. д. Имея в своем распоряжении эти сложные структуры, можно воспользоваться ими для реализации записей. Запись представляет собой отдельную логическую единицу, состоящую из различных атрибутов. Например, запись, описывающая человека, может содержать имя, адрес и дату рождения. В С подобные вещи называются структурами (structs), а в Pascal - записями (RECORDs). В Perl для них не существует специального термина, поскольку эта концепция может быть реализована разными способами. Наиболее распространенный подход в Perl заключается в том, чтобы интерпретировать хэш как запись, где ключи хэша представляют собой имена полей записи, а ассоциированные величины - значения этих полей. Например, запись "человек" может выглядеть так:

$Nat = { "name" => "Leonhard Euler",
"Address" => "1729 Ramanujan Lane\nMathworld, PI 31416",
"Birthday" => Ox5bb5580,

Поскольку ссылка $NAT является скалярной величиной, ее можно сохранить с элементе хэша или массива с информацией о целой группе людей и далее использовать приемы сортировки, объединения хэшей, выбора случайных записей и т,д" рассмотренные в главах 4 и 5. Атрибуты записи, в том числе и "человека" из нашего примера, всегда являются скалярами. Конечно, вместо строк можно использовать числа, но это банально. Настоящие возможности открываются в том случае, если атрибуты записи также представляют собой ссылки. Например, атрибут "Birthday" может храниться в виде анонимного массива, состоящего из трех элементов: день, месяц и год. Выражение $person->{"BIrthday"}->[0] выделяет из даты рождения поле "день". Дата также может быть представлена в виде хэша, для доступа к полям которого применяются выражения вида $person->{ "Birthday" }->{"day"}. После включения ссылок в коллекцию приемов перед вами откроются многие нетривиальные и полезные стратегии программирования. На этом этапе мы концептуально выходим за пределы простых записей и переходим к созданию сложных структур, которые представляют запутанные отношения между хранящимися в них данных. Хотя они могут использоваться для реализации традиционных структур данных (например, связанных списков), рецепты второй части этой главы не связаны ни с какими конкретными структурами. В них описываются обобщенные приемы загрузки, печати, копирования и сохранения обобщенных структур данных. Завершающая программа этой главы демонстрирует работу с бинарными деревьями.

11.1. Ссылки на массивы

Проблема

Требуется работать с массивом через ссылку.

Решение

Ссылка на массив создается следующим образом:

$aref = \@аrrау;
$anon_array = [1, 3, 5, 7, 9];
$anon_copy = [ @аrrау ];
@$implicit_creation = (2, 4, 6, 8, 10);
Чтобы разыменовать ссылку на массив, поставьте перед ней символ @: push(@$anon_array, 11); Или воспользуйтесь стрелкой с указанием индекса конкретного элемента в квадратных скобках:
$two = $implicit_creation->[0];
Для получения индекса последнего элемента массива по ссылке или определения количества элементов в массиве применяется следующая запись:
$last_idx = $#$aref;
$num_items = @$aref;
Дополнительные фигурные скобки повышают надежность и форсируют ну/к ный контекст:
$last_idx = $#{ $aref };
$num_items = scalar @{ $aref };
Комментарий
Рассмотрим примеры использования ссылок на массивы: # Проверить, содержит ли $someref ссылку на массив
if (ref($someref) ne 'ARRAY') {
die "Expected an array reference, not $someref\n";
}
print "@{$array_ref}\n"; # Вывести исходные данные
@order = sort @{ $array_ref }; # Отсортировать их
push @{ $array_ref }, $item; # Добавить в массив новый элемент

Если вы не можете выбрать между использованием ссылки на именованпыи массив и созданием нового массива, существует простое правило, которое в большинстве случаев оказывается верным. Получение ссылки на существующий массив используется либо для возврата ссылки за пределы области действия, либо при передаче массива функции по ссылке. Практически во всех остальных случаях используется [@аrrау], что приводит к созданию ссылки на новый массив с копиями старых значений. Автоматический подсчет ссылок в сочетании с оператором \ обладает большими возможностями:

sub array_ref {
my @array;
return \@array:
$aref1 = array_ref();
$aref2 = array_ref();

При каждом вызове array_ref функция выделяет для array новый блок памяти. Если бы мы не вернули ссылку на @аrrау, то занимаемая массивом память была бы возвращена при выходе из блока, то есть при завершении подпрограммы. Однако ссылка на @аrrау продолжает существовать, поэтому Perl не освобождает намять, и мы получаем ссылку на блок памяти, недоступный через таблицу символов. Такие блоки памяти называются анонимными, поскольку с ними не связано никакое имя. К определенному элементу массива, на который указывает ссылка $aref, можно обратиться в форме $$aref[4], но $aref->[4] делает то же самое и обладает большей наглядностью.

print $array_ref->[$N], # Обращение к М-му элементу (лучший вариант)
print $$array_ref[$N]; # To же, но менее наглядно
print ${$array_ref}[$N]; # To же, но непонятно и уродливо
Имея ссылку на массив, можно получить срез субъектного массива:
(@$pie[3. .5]; # Срез массива, но читается плохо
@{$pie}[3..5]; # Срез массива, читается лучше (?)

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


@{$pie}[3..5] = ("blackberry", "blueberry", "pumpkin");

Срез массива полностью идентичен списку отдельных элементов. Поскольку o сылку на список получить нельзя, вам не удастся получить ссылку на срез массива:

$sliceref = \@{$pie}[3.,5]; # НЕВЕРНО! Для перебора в массиве применяется цикл
foreach или for:
foreach $item ( @{$array_ref} ) { # Данные в $item
}
for ($idx = 0; $idx <= $@{ $array_ref }; $idx++) {# Данные в $array_ref->[$idx]
}

> Смотри также
perlref{1) и perllol(1); рецепты 2.14; 4.5.

11.2. Создание хэшей массивов

Проблема

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

Решение

Сохраните в элементе хэша ссылку на массив. Используйте push для присоединения новых элементов:

push(@{ $hash{"KEYNAME"} }, "new value");

Затем при выводе хэша разыменуйте значение как ссылку на массив:

foreach $string (keys %hash) {
print "$string: @{$hash{$string}}\n";

Комментарий

В хэше могут храниться только скалярные величины. Впрочем, ссылки и являются скалярными величинами. Они помогают решить проблему сохранения не- скольких ассоциированных значений с одним ключом - в $hash{$key} помещается ссылка на массив, содержащий значения $key. Все стандартные операции с хэшами (вставка, удаление, перебор и проверка существования) могут комбинироваться с операциями массивов (push, splice и foreach). Присвоение ключу нескольких значений осуществляется следующим образом:

$hash{"a key"} = [ 3, 4, 5 ];

# Анонимный массив Ключ с ассоциированным массивом используется так:

lvalues = @{ $hash{"a key"} };

Для присоединения новых значений к массиву, ассоциированному с конкретным ключом, используется функция push:

push @{ $hash{"a key"} }, $value;

Классическое применение этой структуры данных - инвертирование хэша, в котором одно значение ассоциируется с несколькими ключами. В хэше, полученном после инвертирования, один ключ ассоциирован с несколькими значениями. Эта проблема рассматривается в рецепте 5.8. Учтите, что запись вида:

Presidents = @{ $phone2name{$number} };

при действующей директиве use st rict вызовет исключение, поскольку вы пы та-етесь разыменовать неопределенную ссылку без автоматического создания. Приходится использовать другую формулировку:


@residents = exists( $phone2name{$number} ) ? @{ $phone2name{$number} } : О;}

> Смотри также ------------------------------
Раздел "Hashes of Arrays" perldsc(1); рецепт 5.8; пример "Хэш с автоматическим дополнением" из рецепта 13.15.

11.3. Получение ссылок на хэши

Проблема

Требуется работать с хэшем по ссылке. Например, ссылка может передаваться ф} ции или входить во внешнюю структуру данных.

Решение

Получение ссылки на хэш:

$href = \%hash;
$anon_hash = { "key1" => "valuel", "key2" => "value2 ..." };
$anon_hash_copy = { %hash };

Разыменование ссылки на хэш:

%hash = %$href;
$value = $href->{$key};
@slice = @$href{$key1, $key2, $key3}; # Обратите внимание: стрелки нет!
@keys = keys %$hash;

Проверка того, является ли переменная ссылкой на хэш:

if (ref($someref) ne 'HASH') {
die "Expected a hash reference, not $someref\n";
}

Комментарий
Следующий пример выводит все ключи и значения двух заранее определенных хэшей:

foreach $href ( \%ENV, \%INC ) { # ИЛИ:
for $href ( \(%ENV,%INC) ) { foreach $key ( keys %$href ) {
print "$key => $href->{$key}\n";
}
}

Операции со срезами хэшей по ссылке выполняются так же, как со срезами массивов. Например:


@values = @$hash_ref{"key1", "key2", "key3"};
for $val (@$hash_ref{"key1", "key2", "key3"}) {
$val += 7; # Прибавить 7 к каждому значению в срезе хэша
}

Смотри также: Глава 5 "Хэши"; perlref(1), рецепт 11.9.

11.4. Получение ссылок на функции

Проблема

Требуется создать ссылку для вызова подпрограммы. Такая задача возникает при создании обработчиков сигналов, косвенно-вызываемых функций Tk и указателей па хэши функций.

Решение

Получение ссылки на функцию:

$cref = \&func;
$cref = sub { ... };
Вызов функции по ссылке:
@returned = $cref->(@arguments);
@oreturned = &$cref(@arguments);

Комментарий

Чтобы получить ссылку на функцию, достаточно снабдить ее имя префиксом Кроме того, формулировка sub {} позволяет создавать анонимные функции. Ссылка на анонимную функцию может быть сохранена так же, как и любая другая. В Perl 5.004 появилась постфиксная запись для разыменования ссылок на функции. Чтобы вызвать функцию по ссылке, раньше приходилось писать &$funcname (@ARGS), где $funcname - имя функции. Возможность сохранить имя функции в переменной осталась и сейчас:

$funcname = "thefunc";
&$funcname();

однако подобное решение нежелательно по нескольким причинам. Во-первых, в нем используются символические, а не настоящие (жесткие) ссылки, поэтому при действующей директиве use st rict ' refs' оно отпадает. Символические ссылки обычно не рекомендуются, поскольку они не могут обращаться к лексическим, а только к глобальным переменным, и для них не ведется подсчет ссылок. Во-вторых, оно не содержит данных о пакете, поэтому выполнение фрагмента в другом пакете может привести к вызову неверной функции. Наконец, если функция была в какой-то момент переопределена (хотя это происходит нечасто), символическая ссылка будет обращаться к текущему определению функции, а жесткая ссылка сохранит старое определение. Вместо того чтобы сохранять имя функции в переменной, создайте ссылку на нее с помощью оператора \. Именно так следует сохранять функцию в переменной или передавать ее другой функции. Ссылки на именованные функции можно комбинировать со ссылками на анонимные функции:

my %commands = (
"happy" => \&joy,
"sad" => \&sullen,
"done" => sub { die "See ya!" },
"mad" => \&angry, );
print "How are you? ";
chomp($string = );
if ($commands{$string}) {
$comroands{$string}->();
} else {
print "No such command: $string\n";
}

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

sub counter_maker { my $start = 0;
return sub {
return $start++;
# Замыкание
# Лексическая переменная
# из вмещающей области действия
};
}
$counter = counter_maker();
for ($i = 0; $i < 5; $i ++) { print &$counter, "\n";
}

Даже несмотря на то что функция counter_maker завершилась, а переменная $start вышла из области действия, Perl не освобождает ее, поскольку анонимная подпрограмма (на которую ссылается $counter) все еще содержит ссылку на $stan. Если повторно вызвать counter_maker, функция вернет ссылку на другую анонимную подпрограмму, использующую другое значение $start:

$counter1 = counter_maker();
$counter2 = counter_maker();
for ($i =0; $i < 5; $i ++) { print &$counter1, "\n":
}
print &$counter1, " ", &$counter2, "\n";
0
1
2
3
4
5 0

Замыкания часто используются в косвенно-вызываемых функциях (callbacks). В графических интерфейсах и вообще в программировании, основанном на событиях, определенные фрагменты кода связываются с событиями нажатий клавиш, щелчков мышью, отображения окон и т. д. Этот код вызывается много позже, возможно, из совсем другой области действия. Переменные, используемые л замыкании, должны быть доступными к моменту вызова. Для нормальной работы они должны быть лексическими, а не глобальными. Замыкания также используются в генераторах функций, то есть в функциях которые создают и возвращают другие функции. Функция counter_maker является генератором. Приведем еще один простой пример:

sub timestamp {
my $start_time = time();
return sub { return time() - $start_time };
}
$early = timestamp();
sleep 20;
$later = timestampo;
sleep 10;
printf "It's been %d seconds since early.\n", $early->();
printf "It's been %d seconds since later.\n", $later->();
It's been 30 seconds since early. It's been 10 seconds since later.

Каждый вызов timestamp генерирует и возвращает новую функцию. Функция timestamp создает лексическую переменную $start_time, которая содержит текущее время (в секундах с начала эпохи). При каждом вызове замыкания оно возвращает количество прошедших секунд, которое определяется вычитанием начального времени из текущего.

> Смотри также -------------------------------
Описание замыканий в perlref(1); рецепты 10.11; 11.4.

11.5. Получение ссылок на скаляры

Проблема

Требуется создать ссылку на скалярную величину и работать с ней.

Решение

Для создания ссылки на скалярную величину воспользуйтесь оператором \:

$scalar_ref = \$scalar; # Получение ссылки на именованный скаляр

Чтобы создать ссылку на анонимную скалярную величину (то есть скаляр, не являющийся переменной), присвойте нужное значение через разыменование неопределенной переменной:

undef $anon_scalar_ref;
$$anon_scalar_ref = 15;

Ссылка на скалярную константу создается следующим образом:

$anon_scalar_ref = \15;

Разыменование выполняется конструкцией ${...}:

print ${ $scalar_ref }; # Разыменовать
${ $scalar_ref } .= "string"; # Изменить значение субъекта

Комментарий

Если вам понадобилось создать много новых анонимных скаляров, воспользуйтесь функцией, возвращающей ссылку на лексическую переменную вне области действия, как объяснялось во введении:

sub new_anon_scalar {
my $temp;
return \$temp;
}

Perl почти никогда не выполняет косвенного разыменования. Исключение составляют ссылки на 4)айловые манипуляторы, программные ссылки на sort И ссылочный аргумент функции bless. Из-за этого для разыменования скалярнов переменной следует снабдить ее префиксом $, чтобы получить все ее содержимое;!

$sref = new_anon_scalar();
$$sref = 3;
print "Three = $$sref\n";
@array_of_srefs = ( new_anon_scalar(), new_anon_scalar() );
${ $array[0] } = 6,02е23;
${ $аrrау[1] } = "avocado";
print "\@аrrау contains: ", join(", ", map { $$_ } @аrrау ), "\n";

Обратите внимание на фигурные скобки вокруг $аrrау[0] и $аrrау[1]. Если бы мы попытались ограничиться простым $$аrrау[0], то в процессе разыменования получили бы $аrrау->[0]. Переменная $аrrау интерпретировалась бы как ссылка на массив, поэтому в результате был бы возвращен элемент с нулевым индексом. Приведем другие примеры, в которых фигурные скобки необязательны:

$var = 'uptime'; # $var содержит текст
$vref = \$var; # $vref "указывает на"
$var if ($$vref =~ /load/) {} # Косвенное обращение к
$var chomp $$vref; # Косвенное изменение $varКак упоминалось во введении, для определения типа субъекта по ссылке применяется встроенная функция ref. При вызове ref для ссылки на скаляр возвращается строка "SCALAR": # Проверить, содержит ли $someref ссылку на скаляр
if (ref($someref) ne 'SCALAR') {
die "Expected a scalar reference, not $someref\n";

Смотри также: perlref(1).

11.6. Создание массивов ссылок на скаляры

Проблема

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

Решение

Чтобы создать массив, либо снабдите префиксом \ каждый скаляр в списке:


@array_of_scalar_refs = ( \$а, \$b );

либо просто поставьте \ перед всем списком, используя свойство дистрибутивности оператора \:


@array_of_scalar_refs = \( $а, $b );

Чтобы получить или задать значение элемента списка, воспользуйтесь конструкцией ${...}:

${ $array_of_scalar_refs[1] } = 12; # $b = 12

Комментарий

В следующих примерах предполагается, что @аrrау - простой массив, содержащий ссылки на скаляры (не путайте массив ссылок со ссылкой на массив). При косвенных обращениях к данным необходимы фигурные скобки.

($а, $b, $c, $d) = (1 .. 4); # Инициализировать
@аrrау = (\$а, \$b, \$c, \$d); # Ссылки на все скаляры
@array = \( $а, $b, $c, $d); # То же самое!
${ $аrrау[2] } += 9; # $c = 12
${ $array[ $#аrrау ] } *= 5; # $d = 20
${ $аrrау[-1] } *= 5; # То же; $d = 100
$tmp = $array[-1]; # Использование временной переменной
$$tmp *= 5; #$d = 500

Две формы присваивания @аrray эквивалентны - оператор \ обладает свойством дистрибутивности. Следовательно, \ перед списком (но не массивом!) эквивалентно применению \ к каждому элементу списка. Следующий фрагмент изменяет значения переменных, ссылки на которые хранятся в массиве. А вот как работать с массивом без явного индексирования.

use Math::Trig qw(pi); # Загрузить константу pi
foreach $sref (@array) { # Подготовиться к изменению $a,$b,$c,$d
($$sref **= 3) *= (4/3 * pi); # Заменить объемом сферы
}

В этом фрагменте используется формула вычисления объема сферы:

V = 4/3pir

Переменная цикла $s ref перебирает все ссылки @а г гау, а в $$s ref заносятся сами числа, то есть исходные переменные $а, $Ь, $с и $d. Изменение $$sref в цикле приводит к изменению этих переменных. Сначала мы возводим $$sref в куб, а затем умножаем полученный результат на 4/Зтс. При этом используется то обстоятельство, что присваивание в Perl возвращает левостороннее выражение. Это позволяет сцеплять операторы присваивания, как это делается с операторами **= и -. Вообще говоря, анонимные скаляры обычно бесполезны - ведь скалярная b( -личина занимает столько же места, что и ссылка на нее. По этой причине не предусмотрены и специальные конструкции для их создания. Скалярные ссылки существуют только для поддержки синонимов, которые могут быть реализованы и другими способами.

11.7. Применение замыканий вместо объектов

Проблема

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

Решение

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

Комментарий

Поскольку замыкание представляет собой совокупность кода и данных, одна из реализации позволяет имитировать поведение объекта. Следующий пример создает и возвращает хэш анонимных функций. Функция mkcounter получает начальное значение счетчика и возвращает ссылку, позволяющую косвенно оперировать им.

$с1 = inkcounter(20);

$с2 = mkcounter(77);

printf "next c1: %d\n",

$c1->{NEXT}->();
	

# 21

printf "next c2: %d\n",

$c2->{NEXT}->();

# 78

printf "next c1: %d\n",
	
$c1->{NEXT}->();
	
# 22

printf "last c1: %d\n",

$c1->{PREV}->();

#

printf "old c2: %d\n",
	
$c2->{RESET}->();
	
# 77
Каждая ссылка на хэш, $с1 и $с2, отдельно хранит информацию о своем состоянии. Реализация выглядит так:

sub mkcounter {
my $count = shift;
my $start = $count;
my $bundle = {
          "NEXT" => sub { [ return ++$count
          "PREV" => sub { [ return --$count
          "GET"  => sub { [ return $count
          "SET"  => sub { [ $count = shift
          "BUMP" => sub { [ $count += shift
          "RESET" => sub { [ $count = $start
$bundle->{"LAST"}=$bundle->{"PREV"};
return $bundle;

Поскольку лексические переменные, используемые замыканиями в ссылке на хэш $bundle, используются функцией, они не освобождаются. При следующем вызове mkcounter замыкания получают другой набор привязок переменных для того же кода. Никто не сможет обратиться к этим двум переменным за пределами замыканий, поэтому полная инкапсуляция гарантирована. В результате присваивания, расположенного непосредственно перед return, значения "prev" и "last" будут ссылаться на одно и то же замыкание. Если вы разбираетесь в объектно-ориентированном программировании, можете считать их двумя разными сообщениями, реализованными с применением одного метода. Возвращаемая нами совокупность не является полноценным объектом, поскольку не поддерживает наследования и полиморфизма (пока). Однако она несомненно обладает собственным состоянием, поведением и идентификацией, а таkже обеспечивает инкапсуляцию.

> Смотри также -------------------------------
Замыкания рассматриваются perlref(1). Также см. главу 13, рецепты 10.11; ll,4

11.8. Создание ссылок на методы

Проблема

Требуется сохранить ссылку на метод.

Решение

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

Комментарий

Ссылка на метод - это нечто большее, чем простой указатель на функцию. Вам также придется определить, для какого объекта вызывается метод, поскольку исходные данные для работы метода содержатся в объекте. Оптимальным решением будет использование замыкания. Если переменная $obj имеет лексическую область действия, воспользуйтесь следующим фрагментом:

$mref = sub { $obj->meth(@_) };
# Позднее...
$mref->("args", "go", "here");

Даже когда переменная $obj выходит из области действия, она остается в замыкании, хранящемся в Smref. Позднее при косвенном вызове метода будет использован правильный объект. Учтите, что формулировка: $sref = \$obj->meth;работает не так, как можно предположить. Сначала она вызывает метод объекта, а затем дает ссылку либо на возвращаемое значение, либо на последнее из возвращаемых значений, если метод возвращает список. Метод can из базового класса UNIVERSAL выглядит заманчиво, но вряд ли делает именно то, что вы хотите:

$cref = $obj->can("meth");

Он дает ссылку на код соответствующего метода (если он будет найден), не несущую информации об объекте. В сущности, вы получаете обычный указатель на функцию. Информация об объекте теряется. Из-за этого и понадобилось замыкание, запоминающее как состояние объекта, так и вызываемый метод.

11.9. Конструирование записей

Проблема

Требуется создать тип данных для хранения атрибутов (запись).

Решение

Воспользуйтесь ссылкой на анонимный хэш.

Комментарий

Предположим, вам захотелось создать тип данных, содержащий различные атрибуты - аналог структур С или записей Pascal. Проще всего сделать это с помощью анонимного хэша. Следующий пример демонстрирует процесс инициализации и применения записи, содержащей информацию о работнике фирмы:

$record = {
NAME => "Jason",
EMPNO => 132,
TITLE => "deputy peon",
AGE => 23,
SALARY => 37_000,
PALS => [ "Norbert", "Rhys", "Phineas""!
printf "I am %s, and my pals are %s.\n",
$record->{NAME}, join(", ", @{$record->{PALS}}):

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

# Сохранить запись
$byname{ $record->{NAME} } = $record;
# Позднее искать по имени
if ($rp = $byname{"aron"}) {
# false, если отсутствует missing
printf "Aron is employee %d.\n", $rp->{EMPNO};
}
# Дать Джейсону нового друга push
@{$byname{"Jason"}->{PALS}}, "Theodore";
printf "Jason now has %d pals\n", scalar @{$byname{"Jason"}->{PALS}};

В результате %byname превращается в хэш хэшей, поскольку хранящиеся в нем значения представляют собой ссылки на хэши. Поиск работника по имени с применением такой структуры оказывается простой задачей. Если значение найдено в хэше, мы сохраняем ссылку на запись во временной переменной $гр, с помощью которой далее можно получить любое нужное поле. Для операций с %byname можно использовать стандартные средства работы с хэшами. Например, итератор each организует перебор элементов в произвольном порядке:

# Перебор всех записей
while (($name, $record) = each %byname) {
printf "%s is employee number %d\n", $name, $record->{EMPNO};
}

А как насчет поиска работников по номеру? Достаточно построить друг',: структуру данных - массив хэшей employees. Если работники нумеруются нег следовательно (скажем, после 1 следует номер 159997), выбор массива окажете неудачным. Вместо этого следует воспользоваться хэшем, в котором номер }', ботника ассоциируется с записью. Для последовательной нумерации подойдет массив:

# Сохранить запись
$employees[ $record->{EMPNO} ] = $record;
# Поиск по номеру
if ($rp = $employee[132]) {
printf "employee number 132 is %s\n", $rp->{NAME};
}

При работе с подобными структурами данных обновление записи в одном месп обновляет ее везде. Например, следующая команда повышает жалование Джейсо-нана3,5%: $byname{"Jason"}->{SALARY} *= 1.035;Внесенные изменения отражаются во всех представлениях этих записей. Помните о том, что $byname{" Jason"} и $employees[132] ссылаются на одну и ту же запись, поскольку хранящиеся в них ссылки относятся к одному анонимному хэш\. Как отобрать все записи, удовлетворяющие некоторому критерию? Для этого и была создана функция дгер. Например, в следующем фрагменте отбирo .i два подмножества записей - работников, чья должность содержит слово ^ и тех, чей возраст равен 27 годам.
@peons = grер { $_->{TITLE} =~ /peon/i } @employees; @tsevens = grер { $_->{AGE} == 27 } @employees;
Каждый элемент @peons и @tsevens представляет собой ссылку на запись, поэтому они, как и @employees, являются массивами хэшей. Вывод записей в определенном порядке (например, по возрасту) выполняется так:

# Перебрать все записи foreach
$rp (sort { $a->{AGE} <=> $b->{AGE} } values %byname) {
printf "%s is age %d.\n", $rp->{NAME}, $rp->{AGE};
# или со срезом хэша через ссылку
printf "%s is employee number %d,\n", @$rp{'NAME','EMPNO'};
}

Вместо того чтобы тратить время на сортировку по возрасту, можно просто создать для этих записей другое представление, @byage. Каждый элемент м:', riii!:i (например, $byage[27]) является массивом всех записей с данным возрш ";ом, Фактически мы получаем массив массивов хэшей. Он строится так:

# Используем @byage, массив массивов записей
push @{ $byage[ $record->{AGE} ] }, $record:

Далее отбор осуществляется следующим образом:

for ($age = 0; $age <= $#byage; $age++)
{ next unless $byage[$age], print "Age Sage: ";
foreach $rp (@{$byage[$age]}) { print $rp->{NAME}, " ";
} print "\n";

Аналогичное решение заключается в применении map, что позволяет избежать цикла foreach:

for ($age = 0; $age <= $#byage; $age++) {
next unless $byage[$age];
printf "Age %d: %s\n", Sage,
join(", ", map {$_->{NAME}} @{$byage[$age]});
}

> Смотри также -Рецепты 4.13; 11.3.

11.10. Чтение и сохранение записей $ текстовых файлах

Проблема

Требуется прочитать или сохранить хэш записи в текстовом файле.

Решение

Воспользуйтесь простым форматом, при котором каждое поле занимает отдельную строку вида: ИмяПоля: Значение и разделяйте записи пустыми строками.

Kомментарий

Если у вас имеется массив записей, которые должны сохраняться в текстовом файле и читаться из него, воспользуйтесь простым форматом, основанным на заголовках почтовых сообщений. Из-за простоты формата ключи не могут быть двоеточиями и переводами строк, а значения - переводами строк. Следующий фрагмент записывает данные в файл:

foreach $record (@Array_of_Records) { for $key (sort keys %$record) {
print "$key: $record->{$key}\n";
} print "\n":

Прочитать записи из файла тоже несложно:

$/=""; # Режим чтения абзацев
while (<>) {
my @fields = { split /"([":]+):\s*/m };
shift @fields; # Удалить начальное пустое поле
push(@Array_of_Records, { (@fields });
}

Функция split работает с $_, своим вторым аргументом по умолчанию, в кч' ром находится прочитанный абзац. Шаблон ищет начало строки (не просто n;i ло записи благодаря /т), за которым следует один или более символов, не являющихся двоеточиями, затем двоеточие и необязательный пропуск. Если шаб.чон split содержит скобки, они возвращаются вместе со значениями. Возвращаемые значения заносятся в Ofileds в порядке "ключ/значение"; пустое поле в нач: убирается. Фигурные скобки в вызове push создают ссылку на новый анонимн хэш, куда копируется содержимое #fields. Поскольку в массиве сохранился по, док "ключ/значение", мы получаем правильно упорядоченное содержимое x;)i Все происходящее сводится к операциям чтения и записи простого текстовою файла, поэтому вы можете воспользоваться другими рецептами. Рецепт 7.11 поможет правильно организовать параллельный доступ. В рецепте 1.13 рассказано о сохранении в ключах и значениях двоеточий и переводов строк, а в рецепте 11.3 -о сохранении более сложных структур. Если вы готовы пожертвовать элегантностью простого текстового файла в пользу быстрой базы данных с произвольным доступом, воспользуйтесь DBM-фай-лом (см. рецепт 11.14).

> Смотри также ------------------------------
Описание функции split в perlfunc(1) рецепты 11.9, 11.13-11.14.

11.11. Вывод структур данных

Проблема

Требуется вывести содержимое структуры данных.

Решение

Если важна наглядность вывода, напишите нестандартную процедуру вывода. В отладчике Perl воспользуйтесь командой х:

DB<1> $reference = [ { "too" => "bar" }, 3,
sub { print "hello, world\n" } ]; DB<2> x Sreference
0 ARRAY(Ox1d033c)
0 HASH(Ox7b390)
'foo' = 'bar'>
1 3
2 CODE(Ox21e3e4) - & in ???>

В программе воспользуйтесь функцией Dumper модуля Data::Dumper от CPAN:

use Data::Dumper;
print Dumper($reference);

Комментарий

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

D<1> x \@INC
О ARRAY(Ox807dOa8)
О '/nome/tchrist/perllib'
1 'usr/lib/perl5/i686-linux/5.00403'
2 '/usr/lib/perl5'
3 'usr/lib/perl5/site_perl/i686-linux'
4 '/usr/lib/perl5/site_perl'
5 '.'

Эти команды используют библиотеку dumpvar.pl. Рассмотрим пример: { package main; require "dumpvar.pl" }

*dumpvar = \&main::dumpvar if _ _package_ _ ne 'main';
dumpvar("main", "INC"); # Выводит и @INC, и %INC

Библиотека dumpvar.pl не является модулем, но мы хотим использовать ее как модуль и поэтому заставляем импортировать функцию dumpvar. Первые две строки форсируют импортирование функции main: :dumpvar из пакета main в текущий пакет, предполагая, что эти функции отличаются. Выходные данные будут выглядеть так:


@INC = (
О '/home/tenrist/perllib/i686-linux'
1 '/home/tchrist/perllib'
2 'usr/lib/perl5/i686-linux/5.00404'
3 'usr/lib/perl5'
4 'usr/lib/perl5/site_perl/i686-linux"
5 'usr/lib/perl5/site_perl'
6 ' . '
}
%INC = (
'dumpvar.pl' = 'usr/lib/perl5/i686-linux/5.00404/dumpvar.pi'
'strict.pm' = 'usr/lib/perl5/i686-linux/5.00404/strict.pm'
)

Модуль Data::Dumper, доступный на СРАМ, предоставляет более гибкое решение. Входящая в него функция Dumper получает список ссылок и возвращает строку с выводимой (и пригодной для eval) формой этих ссылок.

use Data::Dumper;
print Duniper(\@INC);
$VAR1 = [
'/home/tchrist/perllib',
'/usr/lib/perl5/i686-linux/5.00403',
'/usr/lib/perl5',
'/usr/lib/perl5/site_perl/i686-linux',
'/usr/lib/perl5/site_perl',
];

Data::Dumper поддерживает разнообразные форматы вывода. За подробностями обращайтесь к документации.

> Смотри также -------------------------------
Документация по модулю Data::Dumper с CPAN; раздел "The Perl Debugger perldebug(1).

11.12. Копирование структуры данных

Проблема

Требуется скопировать сложную структуру данных.

Решение

Воспользуйтесь функцией dclone модуля Storable от CPAN:

use Storable;
$r2 = dclone($r1);

Комментарий

Существуют два типа копирования, которые иногда путают. Поверхностно ' пирование (surface copy) ограничивается копированием ссылок без создания копии данных, на которые они ссылаются:


@original = ( \@а, \@b, \@>с );
@surface = @origlnal;

Глубокое копирование (deep copy) создает абсолютно новую структуру без перскры-вающихся ссылок. Следующий фрагмент копирует ссылки на один уровень вглубь:


@deep = map { [ @$_ ] } @original;

Если переменные @а, @b и @с сами содержат ссылки, вызов-тар не решит i.a'x проблем. Написание специального кода для глубокого копирования структур -дело трудоемкое и быстро надоедающее. Модуль Storable, доступный на CPAN, содержит функцию dclone, которая обеспечивает рекурсивное копирование своего аргумента:

use Storable qw(dclone);
$r2= dclone($r1);

Функция работает только со ссылками или приписанными к конкретному пакету (blessed) объектами типа SCALAR, ARRAY и HASH; ссылки на CODE, GLOB и 10 и другие экзотические типы не поддерживаются. Функция safeFreeze модуля FreezeThaw обеспечивает такую возможность для одного адресного пространства посредством использования кэша ссылок, который при некоторых обстоятельствах вмешивается в процесс сборки мусора и работу деструкторов объектов. Поскольку dclone принимает и возвращает ссылки, при копировании хэша ссылок в нее приходится включать дополнительные символы:

%newhash = %{ dclone(\%oldhash) };

> Смотри также
Документация по модулям Storable, Data::Dumper и FreezeThaw с CPAN.

11.13. Сохранение структур данных на диске

Проблема

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

Решение

Воспользуйтесь функциями store и retrieve модуля Storable с CPAN:

use Storable;
store(\%hash, "filename");
# later on...
$href = retrieve("filename"); # По ссылке
%hash = %{ retrieve("filename") }; # Прямо в хэш

Комментарий

Модуль Storable использует функции С и двоичный формат для обхода внутренних структур данных Perl и описания данных. По сравнению со строковой реализацией сохранения записей в Perl такой вариант работает эффективнее, однако он менее надежен. Функции store и retrieve предполагают, что в передаваемых двоичных данных используется порядок байтов, стандартный для данного компьютера. Это означает, что созданные этими функциями файлы нельзя передавать между различными архитектурами. Функция nstore делает то же, что и store, но сохраняет данные в каноническом (сетевом) порядке. Быстродействие при этом несколько снижается:

use Storable qw(nstore);
nstore(\%hash, "filename");
# Позднее
$href = retrieve("filename");

Независимо от того, какая функция сохраняла данные - store или nstore, для их восстановления в памяти используется одна и та же функция ret rieve. О переносимости должен заботиться создатель данных, а не их потребитель. Если создатель изменит свое решение, ему достаточно изменить программу всего в одном месте. Тем самым обеспечивается последовательный интерфейс со стороны потребителя, который ничего не знает об этих изменениях. Функции store и nstore не блокируют файлы, с которыми они работают. Если вас беспокоят проблемы параллельного доступа, откройте файл самостоятельно, заблокируйте его (см. рецепт 7.11) и воспользуйтесь функцией store_fd или более медленной, но независимой от платформы версией, nstore_fd. Следующий фрагмент сохраняет хэш в файле с установкой блокировки. При открытии файла не используется флаг O.TRUNC, поскольку до стирания содержимого нам приходится ждать получения блокировки.

use Storable qw(nstore_fd);
use Fcnti qw(:DEFAULT :flock);
sysopen(DF, "/tmp/datafile", 0_RDWR|0_CREAT, 0666)
or die "can't open /tmp/datafile: $!";
flock(DF, LOCK_EX) or die "can't lock /tmp/datafile: $!";
nstore_fd(\%hash, *DF)
or die "can't store hash\n";
truncate(DF, tell(DF));
close(DF);

Другой фрагмент восстанавливает хэш из файла, также с применением блокировки:

use Storable;
use Fcnti qw(:DEFAULT :flock);
open(DF, "< /tmp/datafile") or die "can't open /tmp/datafile: $!";
flock(DF, LOCK_SH) or die "can't lock /tmp/datafile: $!";
$href = retrieve(*df);
close(DF);

Внимательное применение этой стратегии позволяет эффективно передавать большие объекты данных между процессами, поскольку файловый манипулятор канала или сокета представляет собой байтовый поток, похожий на обычный фжч. В отличие от связей с различными реализациями DBM, модуль Storable не ограничивается одними хэшами (или массивами, как DB_File). На диске могут сохраняться произвольные структуры данных. Вся структура должна читаться или записываться полностью.

> Смотри также -------------------------------
Рецепт 11.14.

11.14. Устойчивые структуры данных

Проблема

Существует сложная структура данных, которую требуется сделать устойчивой (persistent)'.

Решение

Воспользуйтесь модулем MLDBM и либо DB_File (предпочтительно), либо GDBM_File:

use MLDBM qw(DB_File);
use Fcnti;
tie(%hash, 'MLDBM', 'testfile.db', 0_CREAT|0_RDWR, 0666)
or die "can't open tie to testfile.db: $!";
# ... Операции с %hash untie %hash;

Комментарий

Конечно, построение хэша из 100000 элементов займет немало времени. Сохранение его на диске (вручную или с помощью Storable) также потребует немалых расходов памяти и вычислительных ресурсов. Модули DBM решают эту проблему посредством связывания хэшей с файлами баз данных на диске. Вместо того чтобы читать всю структуру сразу, они извлекают данные лишь при необходимости. Для пользователя все выглядит так, словно состояние хэша сохраняется между вызовами программы. К сожалению, значения устойчивого хэша должны представлять собой простые строки. Вам не удастся легко использовать базу данных для хранения хэша хэшей, хэша массивов и т. д. - только хэши строк. Однако модуль MLDBM с CPAN позволяет сохранять ссылки в базе данных. Преобразование ссылок в строки для внешнего хранения осуществляется с помощью Data::Dumper:

use MLDBM qw(DB_File);
use Fcnti;
tie(%hash, 'MLDBM', otestfile.db', 0_CREAT|0_RDWR, 0666)
or die "can't open tie to
testfile.db: $!";

Теперь %hash может использоваться для выборки или сохранения сложных записей на диске. Единственный недостаток заключается в том, что к ссылкам нельзя обращаться напрямую. Приходится извлекать ссылку из базы, работать с ней, а затем снова сохранять в базе.

# He будет работать!
$hash{"some key"}[4] = "fred";

Термин "устойчивость" означает сохранение состояния между запусками программы. Также встреча-'oя термин "перманентность". - Примеч. перев.

# ПРАВИЛЬНО
$aref = $hash{"some key"};
$aref->[4] = "fred";
$hash{"some key"} = $aref;

> Смотри также ------
Документация по модулю MLDBM с СРАМ; рецепты 14.1; 14.7; 14.11.

11.15. Программа: бинарные деревья

Встроенные типы данных Perl представляют собой мощные, динамические структуры. В большинстве программ этих стандартных возможностей оказывается вполне достаточно. Для выполнения простого поиска почти всегда следует использовать простые хэши. Как выразился Ларри, "Весь фокус в том, чтобы использовать сильные, а не слабые стороны Perl". Однако хэши не обладают внутренним упорядочиванием элементов. Чтобы перебрать элементы хэша в определенном порядке, необходимо сначала извлечь ключи, а затем отсортировать их. При многократном выполнении это может отразиться на быстродействии программы, что, однако, вряд ли оправдывает затраты времени на разработку хитроумного алгоритма. Древовидные структуры обеспечивают упорядоченный перебор. Как реализовать дерево на Perl? Для начала загляните в свой любимый учебник по структурам данных. Воспользуйтесь анонимным хэшем для представления каждого узла дерева и переведите алгоритмы, изложенные в книге, на Perl. Обычно это задача оказывается проще, чем кажется. Программа в примере 11.1 демонстрирует простую реализацию бинарного дерс--ва, построенную на базе анонимных хэшей. Каждый узел состоит из трех полеи: левый потомок, правый потомок и значение. Важнейшее свойство упорядоченных бинарных деревьев заключается в том, что значение левого потомка всегда меньше, чем значение текущего узла, а значение правого потомка всегда больше. Основная программа выполняет три операции. Сначала она создает дерево с 20 случайными узлами, затем выводит три варианта обхода узлов дерева и, наконец, запрашивает у пользователя ключ и сообщает, присутствует ли этот ключ в дереве. Функция insert использует механизм неявной передачи скаляров по ссылке для инициализации пустого дерева при вставке пустого узла. Присваивание $_[0] созданного узла приводит к изменению значения на вызывающей стороне. Хотя такая структура данных занимает гораздо больше памяти, чем простой хэш, и обычный перебор элементов в пей происходит медленнее, упорядоченные перемещения выполняются быстрее. Исходный текст программы приведен в примере 11.1. Пример 11.1. bintree

#!/usr/bin/perl -w
# bintree - пример работы с бинарным деревом
use strict;
my($root, $n);
# Сгенерировать 20 случайных узлов
while ($n++ < 20) { insert($root, int(rand(1000)) }
Вывести узлы дерева в трех разных порядках
print "Pre order: "; pre_order($root); print "\n";
print "In order: "; in_order($root); print "\n";
print "Post order: ": post_order($root); print "\n":
# Запрашивав до получения EOF
for (print "Search? "; <>; print "Search? ") {
chomp;
my $found = search($root, $_);
if ($found) { print "Found $_ at $found, $found->{VALUE}\n" }
else { print "No $_ in tree\n" }
}
exit;
# Функция вставляет передаваемое значение в правильную позицию
# передаваемого дерева. Если дерево не передается,
# для @_ используется механизм косвенной передачи по ссылке,
# что приводит к созданию дерева на вызывающей стороне.
sub insert {
my($tree, $value) = @_;
unless ($tree) {
$tree = {}; # Создать новый узел
$tree->{VALUE} = $value;
$tree->{LEFT} = undef;
$tree->{RIGHT} = undef;
$_[0] = $tree; # $_[0] - ссылочный параметр!
return;
}
if ($tree->{VALUE} > $value) {
insert($tree->{LEFT}, $value) }
elsif ($tree->{VALUE} < $value)
{ insert($tree->{RIGHT}, $value) } else
{ warn "dup insert of $value\n" }
# XXX: узлы не должны повторяться
}
# Рекурсия по левому потомку,
вывод текущего значения
и рекурсия по правому потомку.
sub in_order {
my($tree) = @>_;
return unless $tree;
in_order($tree->{LEFT});
print $tree->{VALUE}, " ";
in_order($tree->{RIGHT});
}
# Вывод текущего значения,
# рекурсия по левому потомку " и рекурсия по правому потомку,
sub pre_order { my($tree) = @_;
return unless $tree;
print $tree->{VALUE}, " ";
pre_order($tree->{LEFT});
pre_order($tree->{RIGHT});
}
# Рекурсия по левому потомку,
# рекурсия по правому потомку
# и вывод текущего значения,
sub post_order { my($tree) = @_;
return unless $tree;
post_order($tree->{LEFT});
post_order($tree->{RIGHT});
print $tree->{VALUE}, " ";
}
# Функция определяет, присутствует ли передаваемое значение в дереве.
# Если значение присутствует, функция возвращает соответствующий узел.
# Поиск ускоряется за счет ограничения перебора нужной ветвью.
sub search {
my($tree, $value) = @>_;
return unless $tree;
if ($tree->{VALUE} == $value) { return $tree;
}
search($tree->{ ($value < $tree->{VALUE}) '? "LEFT" : "RIGHT"}, $value)
}