Комментарий

Практически любая проблема, при которой требуется определить принадлежность скалярпо!! величины к списку или [accнвy, решается в Perl с помоп1ЬЮ хэ-ше11. Сначала мы обрабатываем @В и регистрируем в хэше %seen псе элементы @В, присваивая соответствующему элементу хэша значение 1. Затем мы последовательно перебираем все элементы @А и проверяем, присутствует ли данный элемент в хэше %seen (то есть в @В).

В приведенном фрагменте ответ будет содержать дубликаты из массива @А. Ситуацию нетрудно исправить, для этого достаточно включать элементы @А в %seen по мере обработки:

foreach $item ((ЭД) {

push ((aaonly, Sitem) unless $seen{$itera},

$seen{$item} = 1 tt Пометить как уже встречавшийся

Эти решения в основном отличаются по способу построения хэша. В первом варианте перебирается содержимое @В. Во втором для инициализации хэша используется срез. Следующий пример наглядно демонстрирует срезы хэша. Фрагмент:

$hash{ keyl } = 1, $hash{ кеу2 } = 2,

эквивалентен следующему:

(a)hash{ keyl , кеу2 } = (1,2),

Список в фигурных скобках содержит ключи, а список справа - значет1я. В первом решении %seen инициализируется перебором всех элементов @В и присваиванием соответствующим элементам %seen значения 1. Во втором \н>1 просто говорим:

@seen{(aB} = ()

В этом случае элементы @В используются в качестве ключей для %seen, а с ними ассоциируется undef, поскольку количество значений в правой части меньше количества нозици!! для их размещения. Показанный вариант работает.

Идиоматическая версия

Imy %seen, # Таблица просмотра ray @аоп1у, # Ответ

й Построить таблицу просмотра (aseen{(aB} = ().

foreach $itera ((ЭА) {

push((aaonly, Sitem) unless exists $seen{$item},

4.8. Вычисление объединения, пересечения и разности уникальных списков 129

поскольку мы проверяем только факт существования ключа, а не его логическую пстиппость или определеипость. Но даже если с элементами @В потребуется ассоциировать истинные значения, срез все равно позволит сократить объем кода:

@8ееп{(аВ} = (1) х @В,

> Смотри также-

Описание срезов хэшей в perldata(l). Аналогичное применение хэшей проде-моистрировано в рецептах 4.7 и 4.8.

4.8. Вычисление объединения, пересечения и разности уникальных списков

Проблема

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

Решение

в приведенных ниже решениях списки иlпщпaJHIЗиpyютcя следующим образом:

(Эа = (1, 3, 5, 6, 7, 8), (ЭЬ = (2, 3, 5 7, 9),

@ип1оп = bisect = @diff = 0, %union = %isect = 0, %count = 0,

Простое решение для объединения и пересечения

foreach $е(@а) { $union{$e} = 1 }

foreach $е (№) {

If ( $union{$e} ) { $isect{$e} = 1 } $union {$e} = 1,

@union = keys %union, (Bisect = keys %isect,

Идиоматическое решение

foreach $e (@a, @b) { $union{$e}++ && $isect{$e}++ }

@union = keys %unions, (Bisect = keys %isect,

Объединение, пересечение и симметричная разность

foreach $е ((Эа, @Ь) { $count{$e}++ }

foreach $е (keys %count) { push(@union, $e), If ($count{$e} == 2) {

push @isect, $e, } else {

push @diff, $e,

Косвенное решение

@isect = @diff = @union = 0,

foreach $e (@a, @b) { $count{$e}++ }

foreach $e (keys %count) { push(@union, $e),

push @{ $count{$e} == 2 \@isect \(S)diff }, $e,

Комментарий

в первом решении происходит непосредственное вычисление объединения и пересечения двух списков, ни один из которых не содержит дубликатов. Для записи элементов, принадлежащих к объединению и пересечению, используются два разных хэша. Сначала мы заносим каждый элемент первого массива в хэш объединения и ассоциируем с ним истинное значение. Затем при последовательной обработке элементов второго массива мы проверяем, присутствует ли элемент в объединении. Если присутствует, он также включается и в хэш пересечения. В любом случае элемент заносится в хэш объединения. После завершения перебора мы извлекаем ключи обоих хэшей. Ассоциированные с ними значения не нужны.

Второе решение («Идиоматическое») в сущности делает то же самое, однако для него потребуется хорошее знание операторов Perl (а также awk. С, С-ы- и Java) -ы-и &&. Если ++ находится после неременной, то ее старое значение используется до приращения. Когда элемент встречается впервые, он еще отсутствует в объединении, поэтому первая часть && будет ложной, а вторая часть попросту игнорируется. Когда тот же элемент встретится во второй раз, он уже присутствует в объединении, поэтому мы заносим его и в пересечение.

В третьем решении использован всего один хэш для хранения информации о том, сколько раз встретился тот или иной элемент. Записав элементы обоих массивов в хэш, мы последовательно перебираем его ключи. Каждый ключ автоматически попадает в объединение. Ключи, с которыми ассоциировано значение 2, присутствуют в обоих массивах и потому заносятся в массив пересече-