Unix Review Column 11 -- Работа со списками

Randal Schwartz

Одной из самых сильных сторон Perl является работа со списками данных. В действительности, с введением ссылок в Perl версии 5.0, работа со списками стала даже еще легче. В этом разделе я покажу вам некоторые простые способы работы со списками, которые вы можете счесть полезными. Кроме того, нет необходимости заново изобретать колесо — кто-то иной, скорее всего уже выполнил этот тяжкий труд. (И чаще всего, когда вы заново изобретаете колесо, вы закончите работу браком).

Одной из самых частых задач при работе со списками является удаление повторяющихся элементов. Этот вопрос часто задается в группе новостей ``comp.lang.perl.misc''. Hаиболее эффективным (и даже наиболее простым для записи, смотрите пример), является использование хеша (ранее называвшегося ``ассоциативным массивом'') для отслеживания элементов списка, и удаления дополнительных копий этих элементов. Это может выглядеть примерно так:

        %temp = ();
        @list = grep ++$temp{$_} < 2, @list;

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

Сначала, я предполагаю, что данные которые я хочу уменьшить только до уникальных элементов, содержатся в массиве @list. Далее я выполняю операцию ``grep'' над текущим значением этого списка. Аналогично команде Unix, оператор grep выбирает и отклоняет элементы списка, основываясь на результате оценки выражения, возвращающего истинное или ложно значение. Однако в нашем случае, оцениваемым выражением является доступ к элементу хеша, используя в качестве ключа значение переменной $_. Оператор grep по одному присваивает переменной $_ значение каждого из элементов списка, и оценка ведется последовательно. Таким образом, первый раз, если значением $_ является, например строка ``fred'', то после выражения ++$temp{``fred''} значение увеличивается от неопределенного (поскольку элемент не может быть найден в хеше) до ``1''. Теперь, поскольку это значение меньше чем 2, то полное выражение возвращает истину и элемент включается в результат.

При следующих вхождениях строки ``fred'', при выполнении ++$temp{``fred''} значение равно 2 или больше. Поскольку это выражение затем возвращает ложное значение, то элемент отвергается. Результат выполнения оператора grep затем присваивается переменной @list, и у нас на руках выполненная задача.

Кто-то недавно спрашивал в группе новостей comp.unix.shell о том, как удалить дублирующиеся имена из списка почтовых адресов. Хотя в настоящее время, поскольку это может быть выполнено простой командой sort с ключом ``-u'', я решил попытаться решить эту проблему с помощью скрипта на Perl. А именно, проверка уникальности почтовых адресов должны быть ``регистро-независимой'', поскольку fred@BIG.COM является тем же самым адресом, что и fred@big.com.. Используя чуть большую программу, чем в предыдущем примере, мы можем решить эту задачу. Вот пример этого решения:

        @list = split /\n/, <<END;
        fred@big.com
        barney@little.com
        fred@BIG.COM
        barney@ivy.edu
        END
        # ... later in the program ...
        {
                my %temp;
                foreach (@list) {
                        $temp{lc} = $_;
                }
                @list = sort values %temp;
        }

В этом примере, первые несколько строк заполняют переменную @list. Блок из семи последних строк формирует временную область, в которой я создаю переменную %temp. Эта переменная гарантированно пустая, аналогично предыдущему примеру. Однако, выполняя объявление переменной внутри блока, переменная автоматически удалится при завершение блока, освобождая выделенную память, и если существует конфликт имен с существующей переменной, то новая переменная будет иметь превосходство. Красивый прием для временных переменных.

После того, как мы создали пустую локальную переменную %temp, выполняется цикл по значениям содержащимся в переменной @list. Каждая итерация цикла задает разное значение локальной переменной $_. Внутри цикла, выполняется простая установка значения элементов хеша, в качестве ключа которого используется значение $_ переведенное в нижний регистр (используя функцию lc), и значением элемента становится содержимое переменной $_ (оригинальный почтовый адрес). Выполняя это я делаю два почтовых адреса одинаковыми (за исключением разницы в регистрах) и они занимают один и тот же элемент ассоциативного списка. Поскольку это невозможно, то второй адрес становится на место первого и я получаю одно значение.

После выполнения цикла, я выделяю значения, отсортированные по алфавиту. Почему значения? Хорошо, ключи все были приведены к нижнему регистру, но значения будут сохранять по крайней мере одно значение с предпочтительным выделением букв в почтовом адресе. Достаточно удобно?

Теперь, немного отличная задача. Другой частой задачей является удаление списка объектов из другого списка объектов. Это может быть названо ``вычитанием множеств'' или получением ``разницы между множествами'', если вы предпочитаете этот тип названий. Хорошо, нам снова на помощь приходит ассоциативный список. В действительность, когда вы думаете о наборе ``каких-то вещей'', то вы почти всегда можете сразу думать о том, что ``множество является ключами ассоциативного массива'' и это близко к истине. Так что перед вами код для проведения вычитания между списками @list и @stoplist:

        %temp = ();
        @temp{@list} = ();
        foreach (@stoplist) {
                delete $temp{$_};
        }
        @list = sort keys %temp;

Снова у меня есть временный ассоциативный массив %temp, я очищаю его, так что я могу работать с ним с нуля. Следующий шаг создает элементы внутри %temp для всех ключей @list, используя оператор среза (slice) для ассоциативного массива. Значения для данных ключей будут не определены, но это неважно для данного решения. Цикл foreach удаляет каждый элемент находящийся в массиве @stoplist из ассоциативного массива %temp. Все нормально, даже если некоторые элементы не присутствуют в ассоциативном массив -- оператор delete просто игнорирует их.

Одно время среди разработчиков Perl обсуждался синтаксис:

        delete @temp{@stoplist};

что позволило бы исключить цикл, но это не было реализовано. Возможно это будет сделано в Perl 6.0?

В заключение, новый список собирается из оставшихся ключей %temp, сортируемых в алфавитном порядке. В результате мы получаем содержимое @list, без элементов @stoplist. Побочным эффектом будет то, что также будут удалены дублированные элементы @list.

Мы можем оформить данный код в виде подпрограммы, например вот так:

        sub remove {
                my($listref,$stopref) = @_;
                my(%temp);
                
                @temp{@$listref} = ();
                foreach (@$stopref) {
                        delete $temp{$_};
                }
                sort keys %temp;
        }

Заметьте, что первые два параметра являются ссылками на списки, а не просто списками. Это позволяет использовать более эффективную передачу списков в подпрограмму. Первый параметр сохраняется в переменной $listref, а второй в $stopref и %temp создается как пустой, локальный ассоциативный массив.

В следующем выражении производится обращение к содержимому $listref, используя запись @$listref, что позволяет обратиться к списку, ссылка на который хранится в переменной $listref. Аналогичным образом производится обращение к содержимому массива, ссылка на который хранится в $stopref. Последнее выражение, вычисляемое в этой подпрограмме (sort keys %temp) становится возвращаемым значением подпрограммы.

Вот простой пример обращения к данной подпрограмме:

        @input = qw(fred barney betty);
        @guys = remove(
                \@input,
                [qw(betty wilma pebbles)]
        );

В массиве @input хранится несколько разных имен, и мы запускам подпрограмму ``remove'', передавая в нее ссылку (созданную оператором обратный слэш) на переменную @input и создается анонимный список из трех имен. Результат, сохраняемый в массиве @guys будет содержать разницу между массивами.

Как мы можем выполнить пересечение множеств, где каждый элемент находится в обоих списках? Это будет выглядеть примерно так:

        %temp = ();
        @temp{@list_one} = (1) x @list_one;
        @result = grep $temp{$_}, @list_two;

Hа первом шаге создается хорошо известный нам хеш %temp. (Или, если бы это была по настоящему временная переменная, то мы не нуждались бы в этом коде). Следующий шаг создает срез хеша %temp, с одним интересным свойством. Левая часть является списком относящимся к @list_one -- правая часть является списком из единиц, который повторяется (с помощью оператора x) настолько, чтобы его длина была точно равна длине списка на левой стороне. В результате этого, все элементы %temp с ключами из списка @list_one получают значение равное 1.

Результат вычисляется поиском тех элементов списка @list_two, которые имеют соответствующие элементы из списка @list_one, используя элементы из %temp, которые были установлены в предыдущем выражении.

Я надеюсь, что данный обзор даст вам некоторый набор идей о работе со списками. Между прочим, данная статься, вместе с остальными статьями о Perl доступна по адресу http://www.teleport.com/~merlyn/UnixReview/. Регистр букв в адресе важен. Hаслаждайтесь!