Карта

Карта — терм, реализующий интерфейс ассоциативного массива, то есть позволяет хранить данные в виде (КЛЮЧ, ЗНАЧЕНИЕ). То же: хеш-таблица, ассоциативный массив, map.

Карты, как новый тип данных в Эрланге, появились относительно недавно, в версии 17 Erlang/OTP — в 2014 г.

1> Age = #{"Alex" => 18, "Bob" => 21}.
#{"Alex" => 18,"Bob" => 21}
2> maps:put("Alex", 19, Age).
#{"Alex" => 19,"Bob" => 21}
3> maps:put("Ivan", 33, Age).
#{"Alex" => 18,"Bob" => 21,"Ivan" => 33}
4> Age.
#{"Alex" => 18,"Bob" => 21}

В первой строке мы создали карту и привязали её к переменной Age. Подразумевается, что мы в этой карте храним возраст неких людей. Во второй команде мы использовали put/3 из модуля maps, предназначенного для работы с картами, которые по-английски называют maps — карты. maps:put/3 “положила” новое значение. Но раз уже есть пара с ключом “Alex”, она просто перезаписалась, и теперь Алексу 19 лет. В третьей команде мы опять использовали maps:put/3. Но Ивана в нашей карте ещё не было, поэтому появилась третья пара.

Если вы внимательны, то заметили, что после 3-й команды мы получили значение выражения, в котором Алексу почему-то снова 18 лет. Далее мы просим выдать значение, какое сейчас у Age. И оказывается, что в нашей карте по-прежнему два значения, а не три, и Алексу правда всё ещё 18 лет.

Всё правильно, карту, как и любой другой тип данных мы, конечно, можем трансформировать во что-то другое. Но переменные в Эрланге иммутабельны. В 1-й строке левая и правая часть с помощью знака равенства сопоставляются, и поскольку к переменной Age ещё не привязано какое-то иное значение, значит, будет намертво привязано это: #{"Alex" => 18, "Bob" => 21}.

5> Age2 = maps:put(“Ivan”, 33, Age). #{“Alex” => 18,“Bob” => 21,“Ivan” => 33} 6> Age2. #{“Alex” => 18,“Bob” => 21,“Ivan” => 33}

Здесь мы вводим переменную Age2, и ей уже присваивается значение выражения, в котором три записи. За основу берётся переменная Age, к которой привязана исходная карта.

Элементы-пары в карте хранятся в определённом порядке. Если ключи — целые числа, сортировка будет по ним.

1> Users = #{2=>boris,3=>carl,1=>alex}.
#{1 => alex,2 => boris,3 => carl}

Если мы зададим две карты с одинаковым набором элементов, но расположенными в разной последовательности, карты будут равны друг другу. Что интересно, порядок в одной создаваемой карте влияет на порядок в следующих картах. Делается это для того, чтобы карты можно было быстро сравнивать.

2> Men = #{boris=>2,carl=>3,alex=>1}.
#{boris => 2,carl => 3,alex => 1}
3> Husbands = #{alex=>1,boris=>2,carl=>3}.
#{boris => 2,carl => 3,alex => 1}
4> Men = Husbands.
#{boris => 2,carl => 3,alex => 1}
5> Guests = #{boris=>2,carl=>3,dima=>4,alex=>1}.
#{boris => 2,carl => 3,alex => 1,dima => 4}

Для создания карт с большим количеством элементов-пар, в которых ключ и/или значение должны быть вычислены, можно использовать задание карты, которое работает аналогично заданию списка. Особенно это полезно для карт с гомогенными (одинаковыми по происхождению) элементами.

Оператор :=

Создавать из одной карты другую можно, как говорилось выше, с помощью функции maps:put/3. Но этого же можно добиться и штатными возможностями языка. Для этого есть следующая форма:

NewMap = OldMap#{K1 Op V1, ... , Kn Op Vn}

Вместо Op может быть или уже знакомый нам оператор =>, или оператор :=.

При создании одной карты из другой возможно две ситуации:

• ключ задаваемого элемента уже есть в предшественнице,
• такого ключа нет.

Оператор => сработает в обоих случаях. Есть ключ или его нет, в новой карте появится новый элемент. Оператор := сработает только в том случае, если ключ задаваемого элемента есть в предшественнице. В противном случае будет крах.

1> Guests = #{boris=>2,carl=>3,dima=>4,alex=>1}.
#{boris => 2,carl => 3,dima => 4,alex => 1}
2> Guests#{alex=>0, egor=>5}.
#{boris => 2,carl => 3,dima => 4,alex => 0,egor => 5}
3> Guests#{alex:=0}.
#{boris => 2,carl => 3,dima => 4,alex => 0}
4> Guests#{egor:=5}.
** exception error: bad key: egor

Если мы создаём карту, используя предшественницу, при этом набор ключей останется таким же, то хорошей практикой будет всегда использовать := для обновления. Во-первых, это хорошее средство против опечаток в коде. Если случайно мы вместо username используем ключ user_name, при обновлении будет крах, который укажет нам на ошибку. Во-вторых, это отличная гарантия тому, что в разных картах (а в Эрланге может быть, например, список из миллиона карт) имеется один и тот же набор ключей. Значит, этот набор можно хранить в одной переменной.

Сравнение скорости списков и карт

Упорядоченные данные можно хранить как в списках, так и картах. В списке мы просто храним цепочку данных: ['А','Б','В','Г','Д']. Каждый элемент доступен по его индексу, в нашем примере у атома 'В' индекс — 3. Элементы списка удобно перебирать. Карты тоже можно использовать для хранения упорядоченных данных. Просто в качестве ключей используем натуральные числа: #{1 => 'А', 2 => 'Б', 3 => 'В', 4 => 'Г', 5 => 'Д'}.

Может показаться, что использование списков быстрее и удобнее. Но всегда ли это так? Дело в том, что в Эрланге динаамическая типизация, то есть на этапе компиляции неизвестно, какими типами данных будет заполнен список. В списке могут быть элементы разных типов, не говоря уже про то, что объём, занимаемый каждым элементом в памяти, невозможно предугадать. Если бы каждый элемент обладал стандартной для данного списка длиной, было бы очень легко перескочить на то место в памяти, где хранится элемент, чтобы прочитать его.

Рассмотрим практическую задачу. Допустим, мы прямо в терме решили хранить какую-то свою элементарную базу данных. У нас, скажем, есть идентификаторы пользователей (1, 2, 3…) и никнеймы, и нам надо как можно быстрее узнать по номеру ник. Попробуем это реализовать с помощью списка и посмотрим, с какой скоростью происходит чтение из списка, если он имеет миллион элементов.

$ erl +pc unicode
1> L = [ [1039+rand:uniform(64) || _ <- lists:seq(1,rand:uniform(10))] || _ <- lists:seq(1,1_000_000)].
["въЙеъд","Кщ","ХшНЩмзЬ","МШ","жоЩъИуЪя","ГНкЗЙрИЮз","УыФф",
 "ЫшвНПВЦ","к","нййлИЛЮЖ","з","ИЫАэсла","ЕлзЭлшБГъв",
 "ДДМвЪяЪф","окХМяРЭл","РсЪпТьЖ","ЩЮФъКТ","ИЦЗАйЕвц","ЯжХъ",
 "п","КГУ","хЭЮББМмЮД","кЫЛапКек","РМцщюЖнб","мтЬрИкУЦй","С",
 "ЭЧРРпр","чдйчФтейЖК",
 [...]|...]

Одной командой мы создали “базу данных” из миллиона ячеек, заполненную бессмысленными никами. Теперь, воспользовавшись уже имеющимся списком, создадим карту “номер => ник”.

2> M = maps:from_list(lists:enumerate(L)).
#{672555 => "вэКД",772479 => "ыЦл",700098 => "ГНзЧЕ",
  796802 => "НЩШКЦЫЪьчР",610181 => "яШТШ",38649 => "иИ",
  749010 => "утШЙЭ",192053 => "ХЗпйЙОЦ",408054 => "лЮЖяЬЧщб",
  907633 => "йзмТЭИшМТт",715382 => "ххю",714221 => "Ж",
  767474 => "ЬТиШяячШфК",3399 => "РУЭутщц",
  70024 => "вэПЬОРНкч",243673 => "сР",628534 => "ИаХшаШяпъ",
  697262 => "ЩЮбШЯШФЙ",682801 => "юэЪкОАКВйЗ",
  542361 => "йчУЩЦ",929332 => "п",945491 => "щР",
  111693 => "ТгЩпЬЙШчм",980377 => "чИ",959424 => "ЛъЭбЙЪсЧ",
  778976 => "ЙЙЯ",309144 => "дЫмДшэТАц",313508 => "ЖуГ",
  734060 => "С",...}

И теперь будем проверять скорость поиска элементов. Поскольку, скорее всего, элементы в начале списка будут находиться быстрее, будем искать в разных местах.

20> timer:tc(lists, nth, [1,L]).
{0,"въЙеъд"}
21> timer:tc(maps, get, [1,M]).
{3,"въЙеъд"}
22> timer:tc(lists, nth, [10,L]).
{1,"нййлИЛЮЖ"}
23> timer:tc(maps, get, [10,M]).
{2,"нййлИЛЮЖ"}
24> timer:tc(lists, nth, [100,L]).
{2,"фыКХлРН"}
25> timer:tc(maps, get, [100,M]).
{1,"фыКХлРН"}
26> timer:tc(lists, nth, [1_000,L]).
{11,"Н"}
27> timer:tc(maps, get, [1_000,M]).
{2,"Н"}
28> timer:tc(lists, nth, [10_000,L]).
{105,"дЪвБъвЯш"}
29> timer:tc(maps, get, [10_000,M]).
{2,"дЪвБъвЯш"}
30> timer:tc(lists, nth, [100_000,L]).
{961,"ЫдТЕЯШХГЮК"}
31> timer:tc(maps, get, [100_000,M]).
{2,"ЫдТЕЯШХГЮК"}
32> timer:tc(lists, nth, [1_000_000,L]).
{7689,"РбнРнЮЛЩбЯ"}
33> timer:tc(maps, get, [1_000_000,M]).
{2,"РбнРнЮЛЩбЯ"}

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

BEAM использует хорошо оптимизированные алгоритмы для поиска в картах — методы, аналогичные бинарному поиску. В принципе, время поиска в карте должно возрастать пропорционально логарифму размера карты. Если бы дольше проводили свой эксперимент и измеряли время в наносекундах, эту закономерность, наверно, увидели бы.

Хорошо оптимизирован также поиск в ETS (тип таблицы ordered_set). Нет такого резкого возрастания времени поиска при увеличении массива данных. Но и здесь карты показывают себя быстрее, они ищут, по моим данным, в 2-3 раза быстрее.

Тоже хорошо оптимизирован поиск в словаре актора. Как показал мой эксперимент, аналогичный вышеизложенному, поиск в словаре даже быстрее (примерно в полтора раза), чем поиск в карте. Однако словарь это не терм, используя его, мы тут же допускаем сторонний эффект, что чревато многими неожиданными проблемами, поэтому использование карты для хранение пар “ключ-значение” будет более правильным.

Использование карты для хранения состояния актора

Карту удобно использовать в качестве единого терма для сохранения состояния актора. В обобщённых поведениях (gen_statem, gen_server, gen_event) при передаче состояния от вызова к вызову используется только один терм. Колбэки, например, могут выглядеть так:

handle_call(Mess, From, State) ->

В большинстве случаев стоит сразу заложить использование карты: в одной паре “ключ-значение” будет, например, число — счётчик каких-то событий, в другой паре, скажем, список нод, откуда приходили сообщения.

Если при перезапуске Системы важно сохранить состояние актора, в Эрланге это очень легко реализовать с помощью сохранения в специальный бинарник (во “внешнем формате”).

$ erl
1> M = maps:from_list([{X,erlang:phash2(X)} || X <- lists:seq(1,1_000_000)]).
#{672555 => 93648087,772479 => 99612589,700098 => 122196403,
  ...
  313508 => 115584889,734060 => 28610461,...}
2> file:write_file("/path/to/file.bin", term_to_binary(M)).
ok
3> q().
ok
$ erl
1> {ok,Bin} = file:read_file("/path/to/file.bin").
{ok,<<131,116,0,15,66,64,98,0,12,167,226,98,2,80,19,94,
      98,0,4,228,20,98,5,31,123,141,98,...>>}
2> M = binary_to_term(Bin).
#{672555 => 93648087,772479 => 99612589,700098 => 122196403,
  ...
  313508 => 115584889,734060 => 28610461,...}

Сначала мы создали карту, содержащую миллион пар “ключ-значение”. С помощью term_to_binary/1 превратили карту в бинарник. С помощью file:write_file/2 записали бинарник в файл. Полученный файл имеет размер 9_999_232 байта, то есть на одну пару нашей карты приходится примерно 10 байтов. Далее мы перезагрузили Систему и с помощью file:read_file/1 получили из файла бинарник. После этого с помощью binary_to_term/1 восстановили из бинарника исходную карту.

Если мы создаём свой актор на основе обобщённого поведения, тогда сохранение карты в файл разумно делать в функции terminate, а восстановление — в функции init.

Документация

maps — документация по модулю maps из стандартной библиотеки.

---

Copyright © 2024-2026 Алексей Карманов