Эрланг на практике. Key-Value структуры данных. — Эрланг на практике

Видео может быть заблокировано из-за расширений браузера. В статье вы найдете решение этой проблемы.

Key-Value структуры данных
proplists
dict
orddict
gb_trees

Key-Value структуры данных

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

Тема большая, поэтому я разделил ее на два урока. На этом уроке мы рассмотрим proplists, dict, orddirt и gb_trees. А на следующем maps и ets таблицы.

proplists

Самое простое, что можно придумать, это собрать пару "ключ-значение" в кортеж, и положить такие кортежи в список.

1> PropList = [{key1, "Val1"}, {key2, 2}, {key3, true}].
[{key1,"Val1"},{key2,2},{key3,true}]

Именно это и делает модуль proplists.

Только proplists еще позволяет пары, где значение -- true, сокращать, сохраняя вместо кортежа просто ключ.

2> PropList2 = [{key1, "Val1"}, {key2, 2}, key3].
[{key1,"Val1"},{key2,2},key3]

API модуля довольно странное. Есть несколько функций для извлечения значения по ключу, есть функция для удаление значения. Но нет функций для добавления и изменения значения.

Впрочем, с добавлением все просто. Для этого используем оператор cons:

3> PropList3 = [{key4, "Hello"} | PropList2].
[{key4,"Hello"},{key1,"Val1"},{key2,2},key3]

С изменением значения тоже просто, для этого опять используем оператор cons :)

4> PropList4 = [{key1, "New val"} | PropList3].
[{key1,"New val"},
 {key4,"Hello"},
 {key1,"Val1"},
 {key2,2},
 key3]

Тогда оказывается, что в списке есть два ключа key1, но proplists такое разрешает. В этом случае будет возвращаться первое от головы списка значение.

Для извлечения значения по ключу есть функции get_value/2, get_value/3 и get_all_values/2.

5> proplists:get_value(key1, PropList4).
"New val"
6> proplists:get_value(key777, PropList4).
undefined
7> proplists:get_value(key777, PropList4, "default value").
"default value"
8> proplists:get_all_values(key1, PropList4).
["New val","Val1"]
9> proplists:get_all_values(key777, PropList4).
[]

Есть еще функции lookup/2 и lookup_all/2, они отличаются тем, что возвращают не значение, а кортеж ключ-значение.

10> proplists:lookup(key1, PropList4).
{key1,"New val"}
11> proplists:lookup(key777, PropList4).
none
12> proplists:lookup_all(key1, PropList4).
[{key1,"New val"},{key1,"Val1"}]
13> proplists:lookup_all(key777, PropList4).
[]

Ну и функция delete/2 удаляет значение из списка:

14> proplists:delete(key1, PropList4).
[{key4,"Hello"},{key2,2},key3]

Понятно, что такая структура данных не очень эффективна. Операции поиска и удаления выполняются не за логарифмическое время, а за линейное. Несмотря на это proplists популярен и широко используется в проектах.

Обычно он используется для конфигурирования, для хранения различных настроек и опций. Ну и в других случаях, когда мы знаем, что ключей в наших данных будет не много, не больше нескольких десятков, то смело берем proplists. Ибо в этой ситуации его эффективность не важна.

dict

Модуль dict мощнее и эффективнее.

Он уже предлагает полный CRUD API (Create, Read, Update, Delete) и некоторые функции сверх того.

Для начала словарь нужно создать:

1> Dict = dict:new().
{dict,0,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}

Затем можно добавлять новые значения функцией store/3.

2> Dict2 = dict:store(key1, "val 1", Dict).
{dict,1,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[key1,118,97,108,32,49]],
        [],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
3> Dict3 = dict:store(key2, "val 2", Dict2).
{dict,2,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[key1,118,97,108,32,49]],
        [[key2,118,97,108,32,50]],
        [],[],[],[],[],[],[],[],[],[],[],[],[]}}}

Как мы видим внутреннее представление это структуры довольно сложное, читать его в консоли и в логах неудобно. Тут на помощью придет функция to_list/1

4> dict:to_list(Dict2).
[{key1,"val 1"}]
5> dict:to_list(Dict3).
[{key1,"val 1"},{key2,"val 2"}]

Она просто превращает dict в proplists, и в таком виде данные читаются гораздо лучше.

Обратная функция from_list/1 тоже есть:

6> dict:from_list([{key1, "val 1"}, {key2, "val 2"}]).
{dict,2,16,16,8,80,48,
      {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
      {{[],
        [[key1,118,97,108,32,49]],
        [[key2,118,97,108,32,50]],
        [],[],[],[],[],[],[],[],[],[],[],[],[]}}}

Для изменения значения в словаре тоже используем функцию store/3

7> Dict4 = dict:store(key1, "new val", Dict3).
8> dict:to_list(Dict4).
[{key1,"new val"},{key2,"val 2"}]

Далее, у нас есть две функции для чтения значения по ключу:

9> dict:fetch(key1, Dict4).
"new val"
10> dict:fetch(key777, Dict4).
** exception error: bad argument
11> dict:find(key1, Dict4).
{ok,"new val"}
12> dict:find(key777, Dict4).
error

Функция fetch/2 возвращает значение, если ключ найден. Или бросает исключение, если такого ключа нет. Функция find/2 возвращает кортеж {ok, Val}, если ключ найден, или атом error, если ключа нет.

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

Ну и для удаления ключа из словаря используем функцию erase/2:

13> Dict5 = dict:erase(key1, Dict4).
14> dict:to_list(Dict5).
[{key2,"val 2"}]

Это полный CRUD API, но кроме него в модуле dict есть и другие интересные функции.

Есть возможность для одного ключа хранить несколько значений. Для этого значения добавляются функцией append/3 или append_list/3:

1> D = dict:new().
2> D2 = dict:append(key1, "value 1", D).
3> D3 = dict:append(key1, "value 2", D2).
4> dict:to_list(D3).
[{key1,["value 1","value 2"]}]
5> D4 = dict:append_list(key1, ["value 3", "value 4"], D3).
6> dict:to_list(D4).
[{key1,["value 1","value 2","value 3","value 4"]}]

Еще есть функции высшего порядка map/2, filter/2, fold/3. Они аналогичны функциям модуля lists, но принимают на вход словарь, и на выходе отдают словарь.

1> D = dict:new().
2> D2 = dict:store(1, "Bob", D).
3> D3 = dict:store(2, "Bill", D2).
4> D4 = dict:store(3, "Helen", D3).
5> dict:to_list(D4).
[{3,"Helen"},{2,"Bill"},{1,"Bob"}]

6> D5 = dict:map(fun(Key, Val) -> string:to_upper(Val) end, D4).
8> dict:to_list(D5).
[{3,"HELEN"},{2,"BILL"},{1,"BOB"}]

9> D6 = dict:filter(fun(Key, Val) -> length(Val) > 3 end, D4).
10> dict:to_list(D6).
[{3,"Helen"},{2,"Bill"}]

11> dict:fold(fun(Key, Val, {KeySum, AllVals}) -> {KeySum + Key, [Val | AllVals]} end, {0, []}, D4).
{6,["Helen","Bill","Bob"]}

Обратите внимание, не foldl, не foldr, а просто fold. Поскольку ключи в словаре не подразумевают определенной последовательности, то и направление свертки не имеет смысла.

orddict

Модуль orddict аналогичен модулю dict, и предоставляет точно такие же функции. Но хранит ключи в сортированом виде. Это позволяет чуть быстрее извлекать значения по ключу, но чуть медленее добавлять значения.

Фред Хеберт в своей книге пишет что orddict эффективен для небольших структур, порядка 75 элементов. Если так, то смысла использовать orddict нет, для такого набора данных и proplists вполне годится.

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

gb_trees

Модуль gb_trees предлагает еще одну key-value структуру данных.

gb_trees означает General Balanced Trees, то есть сбалансированное дерево общего назначения. Если вы изучали алгоритмы, то знаете, что деревья -- эффективные структуры данных, которые обеспечивают доступ к своим элементам за логарифмическое время. Но для этого нужно, чтобы глубина всех веток дерева была примерно одинаковая. Значит деревья должны уметь перемещать свои узлы из одной ветки в другую, то есть, балансироваться.

Понятно, что балансировка сама по себе требует какого-то времени. В gb_trees она выполняется после каждого добавления нового элемента. Но не выполняется при модификации и удалении элемента.

Модуль gb_trees тоже предоставляет CRUD API и некоторые функции сверх того.

Создадим дерево:

1> T = gb_trees:empty().
{0,nil}

Добавим в него значения:

2> T2 = gb_trees:insert(key1, "value 1", T).
{1,{key1,"value 1",nil,nil}}
3> T3 = gb_trees:insert(key2, "value 2", T2).
{2,{key1,"value 1",nil,{key2,"value 2",nil,nil}}}
4> T4 = gb_trees:insert(key2, "value 2", T3).
** exception error: {key_exists,key2}

Как видим, функция insert/3 не позволяет добавлять один и тот же ключ дважды, бросает исключение в этой ситуации.

Модифицируем значения:

5> T4 = gb_trees:update(key1, "new value", T3).
{2,{key1,"new value",nil,{key2,"value 2",nil,nil}}}
6> T5 = gb_trees:update(key777, "new value", T4).
** exception error: no function clause matching gb_trees:update_1(key777,"new value",nil) (gb_trees.erl, line 258)

Функция update/3 бросает исключение, если ключа в дереве нет.

7> T5 = gb_trees:enter(key777, "new value", T4).
{3,
 {key1,"new value",nil,
       {key2,"value 2",nil,{key777,"new value",nil,nil}}}}
8> T6 = gb_trees:enter(key2, "new value", T5).
{3,
 {key1,"new value",nil,
       {key2,"new value",nil,{key777,"new value",nil,nil}}}}

А функция enter/3 исключений не бросает. Если ключа нет, она его добавляет, а если ключ есть, то изменяет значение.

Теперь попробуем получить значения по ключу:

12> gb_trees:get(key1, T6).
"new value"
13> gb_trees:get(some_key, T6).
** exception error: no function clause matching gb_trees:get_1(some_key,nil) (gb_trees.erl, line 239)
14> gb_trees:lookup(key1, T6).
{value,"new value"}
15> gb_trees:lookup(some_key, T6).
none

Здесь у нас две функции. get/2 бросает исключение, если ключа в дереве нет, а lookup/2 возвращает либо кортеж {value, Value}, либо атом none.

Ну и попробуем удалить ключ:

16> gb_trees:delete(key1, T6).
{2,{key2,"new value",nil,{key777,"new value",nil,nil}}}
17> gb_trees:delete(some_key, T6).
** exception error: no function clause matching gb_trees:delete_1(some_key,nil) (gb_trees.erl, line 403)
19> gb_trees:delete_any(key1, T6).
{2,{key2,"new value",nil,{key777,"new value",nil,nil}}}
20> gb_trees:delete_any(some_key, T6).
{3,
 {key1,"new value",nil,
       {key2,"new value",nil,{key777,"new value",nil,nil}}

И опять у нас две функции, которые по-разному реагируют на отсутствие ключа. delete/2 бросает исключение, а delete_any/2 просто возвращает дерево без изменений.

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

По CRUD API все, теперь дополнительные функции:

В gb_trees есть map/2, но нету filter и fold.

22> gb_trees:map(fun(Key, Value) -> string:to_upper(Value) end, T6).
{3,
 {key1,"NEW VALUE",nil,
       {key2,"NEW VALUE",nil,{key777,"NEW VALUE",nil,nil}}}}

Есть функции iterator/1 и next/1, которые позволяют организовать обход дерева. В качестве альтернативы можно преобразовать дерево в proplists с помощью to_list/1, и делать обход списка.

Первый вариант немного медленнее, но экономит память. Второй вариант быстрее, но требует выделения лишней памяти.

Кстати, функции from_list/1 нету, есть только from_orddict/1.