Программирование на Athanor – 15 (словари и операции над ними)

Словари: их создание и основные операции над ними

Подобно спискам и массивам, словарь – это ещё один механизм агрегации данных. Он позволяет довольно эффективно обеспечивать доступ к (произвольным) элементам данных с помощью (произвольных) непустых значений ("ключей"). Таким образом, все данные в словаре всегда хранятся парами: Ключ + Значение. Каждую пару удобно представлять списком: (Ключ, Значение), или (Ключ::Значение).

Как ключи, так и значения могут иметь произвольные типы. Ключами в словаре может быть что угодно – чаще всего, это строки, но допустимы и числовые скаляры, и списки из произвольных элементов. При поиске нужного значения в словаре, к ключу применяется проверка на идентичность (точно так же, как и при выполнении switch: в статье 12 было рассказано, когда данные в языке считаются "идентичными", а когда – нет). При работе со словарями – применяются те же методы проверки. В принципе, словарь тоже можно рассматривать как некий готовый список вариантов для switch: однако, он работает намного эффективнее, к тому же его легко можно создавать и менять динамически.

Словари также ещё называются "хэшами". Эти понятия совершенно синонимичные. Для меня "словарь" звучит более интуитивно (а "хэш" выглядит, скорее, жаргонизмом). Но программисты на большинстве других языков, вроде Perl, уже привыкли к понятию "хэш". К тому же, и сама операция-конструктор для словарей называется hash, а прочие операции, работающие со словарями, начинаются с префикса "h_".

Итак, для начала работы со словарём/хэшем – его необходимо создать. Для этого в языке предусмотрен специальный функтор-конструктор:

Эта операция создаёт новый словарь, и имеет (необязательный) целочисленный аргумент Capacity (задающий начальную ёмкость внутренней хэш-таблицы). Как правило, этот параметр опущен, или равен нулю – тогда выбирается ёмкость по умолчанию. Для hash есть альтернативное имя: h_create. Независимо от аргументов, созданный словарь является пустым: ни одной пары ключ + значение изначально в нём нет.

Для того, чтобы в нём оказались какие-то значения, проще всего использовать h_elem:

Эта операция является операцией доступа, т.е. аксессором. Она возвращает ссылку (мутабельную) на значение в словаре Hash, связанное с ключом Key. Если ключа Key в словаре ещё не было – он автоматически создаётся (вместе с пустым значением). Это – единственная операция, связанная со словарями, имеющая более компактный ("операторный") синтаксис: Hash->Key.

Независимо от того, меняете вы значение, или нет – заданный ключ в Hash всегда создаётся! Что не всегда желательно, и иногда даже может привести к проблемам. Например, обращение в большому количеству несуществующих в словаре ключей – сделает их все "существующими" (что может основательно замусорить словарь, и память в целом). Однако, есть более безопасная операция доступа:

Аргументы совершенно те же, но в отличие от h_elem – h_lookup никогда не создаёт в словаре нового ключа! Только если ключ в словаре существует, возвращается связанное с ним значение (в противном случае – просто возвращается (), а в словаре ничего не меняется). Поскольку h_lookup никогда не меняет словарь – операция в этом отношении более безопасна.

Заметим, что когда вызов h_lookup возвращает (), то это может охначать, что нужного ключа нет в словаре, или же он там уже есть – но с ним связано значение (). С помощью только h_lookup – нельзя различить эти две ситуации. Если нужна полная уверенность, есть ли нужный ключ в словаре, то можно использовать h_exists:

Это – просто предикат: он возвращает 1, если в Hash есть ключ Key, и 0 – в противном случае.

Однажды добавленный в словарь ключ – остаётся в нём, как бы вы не меняли связанное с ним значение. Его можно явно удалить из словаря – для этого есть специальная операция:

Как результат, возвращается значение, которое было связано с ключом Key. Если такого ключа в словаре не было – возвращается (), и в словаре ничего не меняется. Осторожно, операция эта деструктивная.

Здесь как результат, возвращается целое число: сколько ключей (и, соответственно, значений) сейчас находится в словаре Hash. Наконец, словарь можно просто очистить:

Эта операция молча очищает словарь Hash, удаляя из него всё: как ключи, так и значения. (Понятно, что операция эта ОЧЕНЬ деструктивная, и применять её надо лишь тогда, когда содержимое Hash больше не актуально.)

Само собой, предусмотрены операции, позволяющие узнать, какие ключи и/или значения уже присутствуют в словаре:

Все эти операции выгружают данные из словаря Hash. При этом, h_keys – возвращает список из всех ключей словаря, h_values – список из всех значений словаря, наконец h_save – список из списков: пар вида (Ключ, Значение). Для всех этих операций, результаты – открытые списки, и количество элементов в каждом списке равно h_count (Hash). Насчёт порядка элементов – ничего не гарантируется: содержимое словаря выгружается в соответствии со внутренними хэш-таблицами. (Можно лишь быть уверенным, что порядок выгрузки во всех этих трёх функторах – будет одинаковый.)

Дополнительной и обратной операцией для h_save – является h_load:

Список аргументов для h_load – имеет формат, сходный с h_save. Он также должен быть открытым, и каждый его элемент должен быть парой (Ключ::Значение). Если значение с таким ключом уже имелось в словаре – оно молча замещается новым. Для массовой загрузки в словарь удобно использовать h_load – например:

		h_load (EngRusDict,
			"cat":: "кошка",
			"dog":: "собака",
			"bird":: "птица",
			"snake":: "змея",
			);

Наконец, для словарей – как и для всех нетривиальных структур данных – определён собственный итератор для циклического перебора его элементов:

Итератор выполняет своё тело (Loop) точно h_count раз. Относительно порядка выполнения (точно так же, как и для h_keys/h_values/h_save) – никаких гарантий нет! Таким образом, если порядок перебора элементов словаря действительно существенен – их сперва желательно как-то упорядочить (например, отсортировать). (Ниже мы приведём пример того, как это можно сделать, как с сортировкой по ключам, так и по значениям.)

Ну и разумеется, в языке есть предикат, позволяющий для своего операнда проверить: словарь это или нет?

Теперь рассмотрим практический пример использования словарей! Они могут быть полезны для решения многих задач: например, для выполнения частотного анализа входного текста. Приведём сперва полную программу:

` (split words: iterative/reverse ...) `
! split_words_rev (string cc_test) : [pos list] = {
	list = ();

	while ((pos = s_rspan_ex (string, cc_test)) ~= 0):: {
		string = string$[.. pos];
		pos = s_rspan_in (string, cc_test);
		list [<-] string$[pos ..];
		string = string$[.. pos];
		};

	` result is: `
	list };

` (read source stream ...) `
! read_input (dictionary) : [inline line_count word] = {
	line_count = 0;

	while (:> inline):: {
		l_loop (word, split_words_rev (s_lcase (inline), !cc_alpha), ++ dictionary->word);

		++ line_count;
		};

	line_count };

! word_counter : [dictionary total lines count word words_vec] = {
	dictionary = hash ();

	lines = read_input (dictionary);
	total = h_count (dictionary);

	words_vec = array (total);
	a_load (words_vec, h_keys (dictionary));

	! sorted_output (sort_name sort_method) : [index index_keys] = {
		<: ("Dictionary words, sorted by: ", sort_name, "\n");

		index_keys = l_sort_index (sort_method, total);
		l_loop (index, index_keys,
			<: ("\t", '[', words_vec{index}, " : ", dictionary->words_vec{index}, ']', "\n"));

		<: "\n";
		};	` -- sorted_output `

	sorted_output ("alphabetic",
		!(left right) = (s_cmp (words_vec {left}, words_vec {right})));
	sorted_output ("frequency",
		!(left right) = (cmp (dictionary->words_vec {left}, dictionary->words_vec {right})));

	` count everything ... `
	count = 0;
	a_loop (words_vec, word, count =+: dictionary->word);

	<: ("Total lines: ", lines, " / words: ", count, " / unique: ", total, ".\n");
	};	` -- word_counter `

` --- Entry point: `
word_counter ();

Теперь немного комментариев: весь приведённый код – состоит из реализации трёх функторов. С помощью read_input построчно читается входной поток, и все найденные слова – записываются в операнд-словарь dictionary. В качестве результата – возвращается число входных строк (оно аккуратно подсчитывается, просто для статистики).

Всю основную работу по разбивке строк на отдельные слова (т.е. "токенизации") – выполняет split_words_rev, возвращающий в результате список слов. В реализации активно используются встроенные s_rspan_ex и s_rspan_in (про них подробнее было в статье 10), а также предикат cc_alpha (также рассмотрен там). И заметим, что этот предикат вызывается не напрямую, а через параметр-ссылку cc_test. Таким образом, поменять критерий, по которому из входного потока вырезаются "слова", будет очень легко: надо передать split_words_rev какой-нибудь другой предикат в качестве операнда (например, если передать !cc_digit – из входного потока будут извлекаться только десятичные числа, т.е. непрерывные последовательности десятичных цифр). Также заметим, что перед разбивкой строка также принудительно приводится к строчному регистру (s_lcase). (Для большинства реальных языков нужны более сложные проверки, чем просто cc_alpha: он правильно работает только с английским языком, поэтому мы только им и ограничимся.)

Ну и, наконец, word_counter – выполняет всю основную работу. Работа по считыванию и разбивке входного потока уже выполнена – но основная сложность теперь состоит в том, чтобы вывести результаты в удобочитаемой форме. Использовать итератор по словарю (h_loop) можно, но он выведет всё в совершенно непредсказуемом порядке – а нам хотелось бы иметь красиво отсортированный вывод! Специально для этого, мы (внутри word_counter) создадим отдельный функтор sorted_output – он не просто выводит элементы dictionary, но и сортирует их в порядке, заданный его вторым аргументом. Этот аргумент должен быть ссылкой на компаратор: произвольный бинарный функтор, возвращающий отрицательное значение (когда первый операнд "меньше" второго), положительное значение (когда первый операнд "больше" второго) или нуль (если оба сравниваемых значения считаются "равными"). В своей реализации sorted_output в основном использует встроенный функтор l_sort_index, который мы раньше не рассматривали. Но (если весьма кратко): вызов –

• l_sort_index (comparator, N)

– возвращает список индексов (целых чисел от 0 до N-1), но отсортированный таким образом, что для компаратора comparator он будет возрастающим (ну или, как минимум, неубывающим). Подготовив такой список, мы выводим содержимое словаря (в формате "слово : счётчик") в отсортированном порядке. И мы вызываем sorted_output дважды: с сортировкой (алфавитной, через s_cmp) по ключам словаря (т.е. самим словам), и с сортировкой (числовой, через cmp) по значениям (счетчикам этих слов). В конце, мы выводим финальную статистику: сколько строк прочитано, сколько слов всего, и сколько из них являются уникальными в данном тексте. Фактически последняя строка программного кода – это просто вызов word_counter, который делает всю работу.

Проверим программу в деле. Исходным текстом для неё – будет знаменитое стихотворение на английском языке из "The Hobbit" (песня гномов в доме у Бильбо, в переводе И. Комаровой – "За синие горы, за белый туман ..."):

Far over the misty mountains cold,
To dungeons deep and caverns old:
We must away ere break of day
To seek the pale enchanted gold.

The dwarves of yore made mighty spells,
While hammers fell like ringing bells.
In places deep, where dark things sleep,
In hollow halls beneath the fells.

For ancient king and elvish lord
There many a gloaming golden hoard
They shaped and wrought, and light they caught
To hide in gems on hilt of sword.

On silver necklaces they strung
The flowering stars, on crowns they hung
The dragon-fire, in twisted wire
They meshed the light of moon and sun.

Far over the misty mountains cold
To dungeons deep and caverns old
We must away, ere break of day,
To claim our long-forgotten gold.

Goblets they carved there for themselves
And harps of gold; where no man delves
There lay they long, and many a song
Was sung unheard by men or elves.

The pines were roaring on the height,
The winds were moaning in the night.
The fire was red, it flaming spread;
The trees like torches blazed with light,

The bells were ringing in the dale
And men looked up with faces pale;
The dragon's ire more fierce than fire
Laid low their towers and houses frail.

The mountain smoked beneath the moon;
The dwarves, they heard the tramp of doom.
They fled their hall to dying -fall
Beneath his feet, beneath the moon.

Far over the misty mountains grim
To dungeons deep and caverns dim
We must away, ere break of day,
To win our harps and gold from him!

Вот вывод нашей программы для заданного текста:

Dictionary words, sorted by: alphabetic
	[a : 2]
	[ancient : 1]
	[and : 12]
	[away : 3]
	[bells : 2]
	[beneath : 4]
	[blazed : 1]
	[break : 3]
	[by : 1]
	[carved : 1]
	[caught : 1]
	[caverns : 3]
	[claim : 1]
	[cold : 2]
	[crowns : 1]
	[dale : 1]
	[dark : 1]
	[day : 3]
	[deep : 4]
	[delves : 1]
	[dim : 1]
	[doom : 1]
	[dragon : 2]
	[dungeons : 3]
	[dwarves : 2]
	[dying : 1]
	[elves : 1]
	[elvish : 1]
	[enchanted : 1]
	[ere : 3]
	[faces : 1]
	[fall : 1]
	[far : 3]
	[feet : 1]
	[fell : 1]
	[fells : 1]
	[fierce : 1]
	[fire : 3]
	[flaming : 1]
	[fled : 1]
	[flowering : 1]
	[for : 2]
	[forgotten : 1]
	[frail : 1]
	[from : 1]
	[gems : 1]
	[gloaming : 1]
	[goblets : 1]
	[gold : 4]
	[golden : 1]
	[grim : 1]
	[hall : 1]
	[halls : 1]
	[hammers : 1]
	[harps : 2]
	[heard : 1]
	[height : 1]
	[hide : 1]
	[hilt : 1]
	[him : 1]
	[his : 1]
	[hoard : 1]
	[hollow : 1]
	[houses : 1]
	[hung : 1]
	[in : 6]
	[ire : 1]
	[it : 1]
	[king : 1]
	[laid : 1]
	[lay : 1]
	[light : 3]
	[like : 2]
	[long : 2]
	[looked : 1]
	[lord : 1]
	[low : 1]
	[made : 1]
	[man : 1]
	[many : 2]
	[men : 2]
	[meshed : 1]
	[mighty : 1]
	[misty : 3]
	[moaning : 1]
	[moon : 3]
	[more : 1]
	[mountain : 1]
	[mountains : 3]
	[must : 3]
	[necklaces : 1]
	[night : 1]
	[no : 1]
	[of : 8]
	[old : 2]
	[on : 4]
	[or : 1]
	[our : 2]
	[over : 3]
	[pale : 2]
	[pines : 1]
	[places : 1]
	[red : 1]
	[ringing : 2]
	[roaring : 1]
	[s : 1]
	[seek : 1]
	[shaped : 1]
	[silver : 1]
	[sleep : 1]
	[smoked : 1]
	[song : 1]
	[spells : 1]
	[spread : 1]
	[stars : 1]
	[strung : 1]
	[sun : 1]
	[sung : 1]
	[sword : 1]
	[than : 1]
	[the : 23]
	[their : 2]
	[themselves : 1]
	[there : 3]
	[they : 9]
	[things : 1]
	[to : 8]
	[torches : 1]
	[towers : 1]
	[tramp : 1]
	[trees : 1]
	[twisted : 1]
	[unheard : 1]
	[up : 1]
	[was : 2]
	[we : 3]
	[were : 3]
	[where : 2]
	[while : 1]
	[win : 1]
	[winds : 1]
	[wire : 1]
	[with : 2]
	[wrought : 1]
	[yore : 1]

Dictionary words, sorted by: frequency
	[meshed : 1]
	[unheard : 1]
	[yore : 1]
	[mighty : 1]
	[places : 1]
	[or : 1]
	[than : 1]
	[gems : 1]
	[necklaces : 1]
	[it : 1]
	[trees : 1]
	[faces : 1]
	[more : 1]
	[houses : 1]
	[spread : 1]
	[golden : 1]
	[laid : 1]
	[forgotten : 1]
	[heard : 1]
	[stars : 1]
	[claim : 1]
	[spells : 1]
	[fierce : 1]
	[doom : 1]
	[grim : 1]
	[from : 1]
	[hammers : 1]
	[fled : 1]
	[fell : 1]
	[ancient : 1]
	[wrought : 1]
	[hollow : 1]
	[caught : 1]
	[sword : 1]
	[carved : 1]
	[height : 1]
	[night : 1]
	[red : 1]
	[blazed : 1]
	[looked : 1]
	[frail : 1]
	[smoked : 1]
	[hall : 1]
	[fall : 1]
	[feet : 1]
	[dark : 1]
	[halls : 1]
	[fells : 1]
	[made : 1]
	[while : 1]
	[crowns : 1]
	[hide : 1]
	[themselves : 1]
	[delves : 1]
	[by : 1]
	[elves : 1]
	[pines : 1]
	[torches : 1]
	[dale : 1]
	[his : 1]
	[goblets : 1]
	[winds : 1]
	[towers : 1]
	[silver : 1]
	[sun : 1]
	[man : 1]
	[dim : 1]
	[mountain : 1]
	[win : 1]
	[him : 1]
	[king : 1]
	[low : 1]
	[gloaming : 1]
	[strung : 1]
	[flowering : 1]
	[hung : 1]
	[lay : 1]
	[song : 1]
	[sung : 1]
	[roaring : 1]
	[moaning : 1]
	[flaming : 1]
	[dying : 1]
	[enchanted : 1]
	[sleep : 1]
	[no : 1]
	[lord : 1]
	[up : 1]
	[tramp : 1]
	[hoard : 1]
	[seek : 1]
	[things : 1]
	[wire : 1]
	[shaped : 1]
	[hilt : 1]
	[s : 1]
	[ire : 1]
	[twisted : 1]
	[elvish : 1]
	[their : 2]
	[where : 2]
	[like : 2]
	[our : 2]
	[harps : 2]
	[bells : 2]
	[cold : 2]
	[pale : 2]
	[dwarves : 2]
	[many : 2]
	[old : 2]
	[men : 2]
	[ringing : 2]
	[a : 2]
	[long : 2]
	[with : 2]
	[was : 2]
	[for : 2]
	[dragon : 2]
	[break : 3]
	[fire : 3]
	[must : 3–
	[day : 3]
	[away : 3]
	[far : 3]
	[ere : 3]
	[over : 3]
	[were : 3]
	[light : 3]
	[mountains : 3]
	[moon : 3]
	[there : 3]
	[dungeons : 3]
	[caverns : 3]
	[we : 3]
	[misty : 3]
	[deep : 4]
	[gold : 4]
	[on : 4]
	[beneath : 4]
	[in : 6]
	[to : 8]
	[of : 8]
	[they : 9]
	[and : 12]
	[the : 23]

Total lines: 49 / words: 270 / unique: 145.

В данном тексте всего 49 строк и 270 слов (из них уникальных только 145), а самое популярное (предсказуемо) – определённый артикль "the" (далее, по убыванию, идут "and", "they", "of", "to" и "in"). Для более объёмных художественных текстов (вроде рассказов Эдгара По, или А. Конан Дойля) – статистика примерно такая же: возможны вариации, но определённый артикль всегда лидирует с уверенным перевесом.