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

Выборка уникальных элементов из списка

Проблема

Требуется удалить из списка повторяющиеся элементы — например, при построении списка из файла или на базе выходных данных некоей команды. Рецепт в равной мере относится как к удалению дубликатов при вводе, так и в уже заполненных массивах.

Решение

Хэш используется для сохранения встречавшихся ранее элементов, а функция keys — для их извлечения. Принятая в Perl концепция истинности позволит уменьшить объем программы и ускорить ее работу. Прямолинейно

%seen = ();
@uniq =();
foreach $item (@list) {
  unless ($seen{$item}) {
    # Если мы попали сюда, значит, элемент не встречался ранее
    $seen{$item} = 1;
    push(@uniq, $item);
  }
}

Быстро

%seen = ();
foreach $item (@list)   {
  push(@uniq, $item) unless $seen{$item}++;
}

Аналогично, но с пользовательской функцией

%seen = ();
foreach $item (@list) {
  some_func($item) unless $seen{$item}++;
}

Быстро, но по-другому

%seen = ();
foreach $item (@list) {
  $seen{$item}++;
}
@uniq = keys %seen;

Быстро и совсем по-другому

%seen = ();
@unique = grep { ! $seen{$_)++ } @list;

Комментарий

Суть сводится к простому вопросу — встречался ли данный элемент раньше? Хэши идеально подходят для подобного поиска. В первом варианте («Прямолинейно») массив уникальных значений строится по мере обработки исходного списка, а для регистрации встречавшихся значений используется хэш.

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

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

В следующем варианте («Быстро, но по-другому») уникальные ключи извлекаются из хэша %seen лишь после того, как он будет полностью построен. Иногда это удобно, но исходный порядок элементов утрачивается.

В последнем варианте («Быстро и совсем по-другому») построение хэша %seen объединяется с извлечением уникальных элементов. При этом сохраняется исходный порядок элементов.

Использование хэша для записи значения имеет два побочных эффекта: при обработке длинных списков расходуется много памяти, а список, возвращаемый keys, не отсортирован в алфавитном или числовом порядке и не сохраняет порядок вставки. Ниже показано, как обрабатывать данные по мере ввода. Мы используем 'who' для получения сведении о текущем списке пользователей, а перед обновлением хэша извлекаем из каждой строки имя пользователя:

# Построить список зарегистрированных пользователей с удалением дубликатов
%ucnt = ();
for ('who') {
  s/\s.*\n//;   # Стереть от первого пробела до конца строки
                # остается имя пользователя
  $ucnt{$_}++;  # Зафиксировать присутствие данного пользователя
}
# Извлечь и вывести уникальные ключи
@users = sort keys %ucnt;
print "users logged in: @users\n";

Выборка уникальных элементов из списка

Проблема

Решение

Комментарий

См. также