Несмотря на то, что в большинстве этих примеров мы создавали экземпляры и просматривали списки, они представляют собой структуру данных, которая обеспечивает доступ только со сложностью O (N) при обходе списка; только добавление и удаление элемента из списка может быть выполнено за постоянное время.
Эрланг затем предоставляет другим абстракциям коллекции внутреннее представление, состоящее из деревьев и хеш-таблиц, классических решений для улучшения класса сложности операций, таких как поиск и проверка существования элемента.
В этой статье мы рассмотрим наборы и их упорядоченные варианты.
ETS примитивы
Erlang Term Storage — это инфраструктура, поставляемая с виртуальной машиной Erlang, которая позволяет создавать и легко манипулировать некоторыми структурами данных, одна из которых является наборами.
Давайте создадим набор фильмов и добавим в него несколько элементов:
sets_contain_only_a_single_element_for_each_key_test() ->
Movies = ets:new(movies, [set]),
ets:insert(Movies, {"Star Wars", 1978}),
ets:insert(Movies, {"Star Wars", 1977}),
[{_, Year}] = ets:lookup(Movies, "Star Wars"),
?assertEqual(1977, Year).
Наборы имеют свойство содержать только один элемент для каждого экземпляра своего ключа, который по умолчанию считается первым полем вставленных кортежей (здесь «Звездные войны»). Поэтому, когда мы вставляем новый кортеж с тем же ключом, мы фактически перезаписываем предыдущий. Затем ets: lookup / 2 возвращает список, состоящий только из одного элемента, тогда как в случае других структур данных элементов может быть много.
Ключи не являются жестко закодированными, чтобы быть первым полем кортежей, и они также могут быть атомами вместо строк или других типов:
sets_contain_only_a_single_element_for_each_key_test() ->
Movies = ets:new(movies, [set]),
ets:insert(Movies, {"Star Wars", 1978}),
ets:insert(Movies, {"Star Wars", 1977}),
[{_, Year}] = ets:lookup(Movies, "Star Wars"),
?assertEqual(1977, Year).
Если вы хотите установить какое-то глобальное состояние, вы можете разрешить ссылаться на таблицу по имени, а не передавать возвращаемое значение ets: new / 2. Лично я предпочитаю явно передавать зависимости в код, который нуждается в них, на любом языке программирования.
names_table_allow_later_referencing_test() ->
ets:new(movies, [set, named_table]),
ets:insert(movies, {"Star Wars", 1977}),
[{_, Year}] = ets:lookup(movies, "Star Wars"),
?assertEqual(1977, Year).
Обратите внимание, что примитивы ets: * действительно вносят некоторое глобальное состояние в приложение, поскольку именованные таблицы могут просматриваться процессами через жестко закодированные атомы (даже между выполнением различных автоматических тестов). Вы должны вызвать ets: delete / 1, чтобы освободить структуру данных ETS и лишить доступа к ней.
Однако структуры данных ETS не обеспечивают большую поддержку параллелизма: вы должны скрывать их внутри своих собственных процессов. Чтобы помочь вам в этом и избежать экранирования ссылок, Erlang позволяет вам определить частное хранилище:
private_sets_cannot_exit_the_current_process_test() ->
Movies = ets:new(movies, [set, private]),
process_flag(trap_exit, true),
spawn_link(fun() -> fill(Movies) end),
receive
{'EXIT', _, {badarg, [{Module, Function, _}, _]}} ->
?assertEqual(ets, Module),
?assertEqual(insert, Function)
end.
fill(Set) ->
ets:insert(Set, {"Star Wars", 1977}).
Здесь мы связали дочерний процесс с родительским, чтобы иметь возможность перехватить его выход как сообщение. Сообщение содержит описание проблемы: произошел сбой вызова ets: insert / 2 с ошибкой badarg , поскольку новый процесс не может получить доступ к закрытому набору.
Заказанные наборы
Наборы Orderet немного отличаются по своим возможностям от обычных наборов: как следует из названия, они могут перечислять ключи в своем лексическом порядке. Стоимость этой функции заключается в том, что доступ является логарифмическим по сложности, а не требует постоянного времени. В базовой реализации вместо хеш-таблицы создается дерево для вставки значений по порядку.
sets_can_be_ordered_test() ->
ets:new(ordered_movies, [ordered_set, named_table]),
ets:insert(ordered_movies, {"Terminator", 1984}),
ets:insert(ordered_movies, {"Star Wars", 1977}),
?assertEqual("Star Wars", ets:first(ordered_movies)),
?assertEqual("Terminator", ets:next(ordered_movies, "Star Wars")).
API работает, показывая для вас первый ключ упорядоченного набора (ets: first / 1) и сообщая вам следующий ключ относительно любого другого (ets: next / 2). Остальная часть API, такая как вставка и удаление, работает так же, как и для неупорядоченных наборов.
Запросы
Мы не могли бы говорить о таблицах и структурах данных, не говоря о том, чтобы запрашивать их по случаю. Опрос ETS включает в себя проекции (выбор только нескольких столбцов) и фильтрацию (выбор только некоторых элементов):
querying_is_possible_on_single_fields_test() ->
Movies = ets:new(movies, [set]),
ets:insert(Movies, {"Terminator", 1984, "Cameron"}),
ets:insert(Movies, {"Star Wars", 1977, "Lucas"}),
ets:insert(Movies, {"Name", 1999, "A"}),
?assertEqual([["Star Wars"]], ets:match(Movies, {'$0', 1977, '_'})).
Синтаксис ets: match / 2 содержит кортеж, состоящий из литеральных значений (1977) и специальных строк.
Специальные строки могут использоваться для указания выбора поля элементов (‘$ 0’) или для указания того, что мы не заботимся об одном из них (‘_’).
Результатом является список списков:
- Основной список состоит из всех элементов, которые соответствуют кортежу.
- Каждый элемент представлен в виде списка, поскольку его счетчик полей может управляться динамическими вызовами.
Соответствие также охватывает удаление и более сложную спецификацию соответствия, где операции могут быть оценены над полями для определения их включения. Взгляните на учебник для этого небольшого курса «Программирование О’Рейли Эрланга», который научил меня не только умению писать функции, но и знаниям уникальных функций Эрланга .