Perl. Библиотека программиста

Поиск элементов одного массива, отсутствующих в другом массиве

Проблема

Требуется найти элементы, которые присутствуют в одном массиве, но отсутствуют в другом.

Решение

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

# Предполагается,что @А и @В уже загружены
%seen = ();        # Хэш для проверки принадлежности элемента В
@aonly = ();       # Ответ

# Построить таблицу просмотра
foreach $item (@B) { $seen{$item} = 1 }
# Найти элементы @А, отсутствующие в @В
foreach $item (@A) {
  unless $item (@A) {
    # Отсутствует в %seen, поэтому добавить в @aonly
    push(@aonly, $item);
  }
}

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

my %seen;            # Таблица просмотра
my @aonly;           # Ответ
# Построить таблицу просмотра
@seen{(@В} = ();
foreach $item (@А) {
  push(@aonly, $item) unless exists $seen{$item);
}

Комментарий

Практически любая проблема, при которой требуется определить принадлежность скалярной величины к списку или массиву, решается в Perl с помощью хэшей. Сначала мы обрабатываем @В и регистрируем в кэше %seen все элементы @В, присваивая соответствующему элементу кэша значение 1. Затем мы последовательно перебираем все элементы @А и проверяем, присутствует ли данный элемент в хэше %seen (то есть в @В). В приведенном фрагменте ответ будет содержать дубликаты из массива @А. Ситуацию нетрудно исправить, для этого достаточно включать элементы @А в %seen по мере обработки:

foreach $item (@A) {
  push (@aonly, $item) unless $seen{$item);
  $seen{$item) = 1;       # Пометить как уже встречавшийся
}

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

$hash{"key1"} = 1;
$hash{"key2"} = 2;

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

@hash{"key1",   "key2"} = (1,2);

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

@seen{@B}  = ();

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

@seen{@B} = (1) x @B

Поиск элементов одного массива, отсутствующих в другом массиве

Проблема

Решение

Комментарий

См. также