Поиск

Практическое применение хэшей

Хэши часто используются в Perl не только для хранения записей, доступ к которым выполняется по значению ключей. Основные преимущества хэшей — быстрый доступ к отдельному ключу и уникальность ключей. Эти особенности неоценимы при обработке данных. Из-за сходства с массивами хэши будут особенно полезны для преобразования массивов данных.

Определение частоты появления слов

На 6-м занятии, "Поиск по шаблону", вы узнали, как разделить строку текста на отдельные слова. Посмотрите на следующий фрагмент кода:

Проведем анализ этого кода. В первой строке выполняется чтение информации со стандартного устройства ввода. При этом введенные значения поочередно присваиваются переменной $_. Следующий цикл while совершает итерацию по всем словам, находящимся в переменной $_. Из 6-го занятия, "Поиск по шаблону", вы должны помнить, что оператор поиска по шаблону (//) в скалярном контексте и с модификатором g возвращает истинное значение до тех пор, пока не будут найдены все совпадения с шаблоном. Шаблон состоит из текстового символа \w, за которым может следовать любое количество (включая нуль) текстовых символов или дефисов [\w-]*. Для того чтобы запомнить совпадение в специальной переменной , весь шаблон взят в скобки.

В следующей короткой строке кода происходят интересные вещи. Переменной поочередно присваивается каждое слово, соответствующее шаблону из второй строки кода. Слова используются в качестве ключей хэша %Words. Первоначально значение пары ключ-значение не определено. Инкремент неопределенного значения, соответствующего впервые встреченному слову, помещает в элемент хэша значение 1. Если слово встречается во второй раз, ключ хэша уже существует и соответствующее ему значение увеличивается на 1, т.е. становится равным 2. Этот процесс продолжается, пока не закончатся входные данные.

После окончания работы кода в хэше %Words будет содержаться частота появления вводимых вами слов. Для того чтобы просмотреть полученное распределение, можно воспользоваться следующим кодом:

Нахождение уникальных элементов массива

Описанную выше методику можно использовать для нахождения тех элементов массива, которые встречаются в нем только один раз. Предположим, вы извлекли все слова из введенных данных и поместили их не в хэш, а в массив. Допустим также, что проверка наличия в массиве данного слова перед его помещением туда не выполнялась. В этом случае в полученном списке могут содержаться повторяющиеся слова.

Предположим, что во вводимой строке будет содержаться следующий список слов:

При помощи хэша данный список слов может быть проверен на наличие уникальных элементов, как показано в листинге 7.1.

Проведем анализ программы.

  • Строка I. В этой строке инициализируется временный хэш %seen, предназначенный для хранения слов.
  • Строка 2. В этой строке совершается итерация по списку слов, переменной $_ поочередно присваиваются все слова.
  • Строка 3. Здесь создается элемент хэша %seen, ключ которого хранится в переменной $ , а значение равно 1.
  • Строка 5. Все ключи извлекаются из хэша и помешаются в массив @uniquewords. Все повторяющиеся слова, например fish, записываются в хэш поверх друг друга, поэтому в итоге они будут представлены там только одним ключом.
Вычисление пересечения и разности массивов

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

Код для поиска пересечения этих массивов приведен в листинге 7.2.

Проведем анализ программы.

  • Строка 1. Инициализируется хэш %seen, предназначенный для хранения имен кинозвезд.
  • Строка 2. В этой строке происходит итерация по списку кинозвезд с поочередным присваиванием каждого имени переменной $_ .
  • Строка 3. Здесь создаются новые элементы хэша,% 5ееп с именами кинозвезд в качестве ключей и значением 1, вместо которого можно использовать любое истинное значение.
  • Строка 5. Эта строка выглядит сложнее, чем она есть на самом деле. Функция grep совершает итерацию по списку политиков Gpols, поочередно присваивая имя каждого политика переменной $_. Затем проверяется наличие этого имени в хэше %seen. Если имя там существует, связанное с ним значение истинно. Если значение выражения истинно, $_ поступает в массив @intersection. Процесс продолжается до тех пор, пока grep не проверит каждый элемент массива gpols. После окончания выполнения этого кода в массиве intersection будут содержаться имена, встречающиеся и в @stars,и в @pols.

Код для нахождения разности двух массивов, т.е. элементов, которые есть только в одном из массивов, практически идентичен предыдущему и приведен в листинге 7.3.

Изменения коснулись лишь пятой строки программы. В ней по-прежнему проверяются все имена политиков на наличие в хэши %seen, но выражение функции grep получает ложное значение, если имя найдено, и истинное — если имя не найдено. Все имена политиков, содержащиеся в %seen, не возвращаются массиву @difference. Для нахождения всех кинозвезд, не являющихся политиками, используется почти тот же код, лишь меняются местами массивы @stars и @pols.

Сортировка хэшей

Часто ключи хэша нужно вывести в определенном порядке, а не в том, в котором они там хранятся. Скажем, вы хотите вывести частоту появления слов в алфавитном порядке или в порядке увеличения частоты. Так как функция keys возвращает список, к нему можно применить функцию sort для упорядочивания исходного списка:

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

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