erlang 数据结构 --maps

xiaoxiao2021-02-28  13

1. 今天是maps

1.1. key-value 数据结构 1.2. 更好的模式匹配

2.操作:

2.0 格式

1> F = #{a => 1, b => 2}. #{a => 1,b => 2}

2.1. 更新key-value

=> 如果原本有key, 则更新, 如果没有key,就插入key-value; := 更新已有的key的value,如果原来没有key,就报错

3> F1 = F#{a => 2}. #{a => 2,b => 2} 4> F2 = F#{c => 3}. #{a => 1,b => 2,c => 3} 5> F3 = F#{a := 1}. #{a => 1,b => 2} 8> F5 = F#{c := 2}. ** exception error: {badkey,c} in function maps:update/3 called as maps:update(c,2,#{a => 1,b => 2}) in call from erl_eval:'-expr/5-fun-0-'/2 (erl_eval.erl, line 255) in call from lists:foldl/3 (lists.erl, line 1263)

2.2 模式匹配

maps 记录频率

freq(Is) -> freq(Is, #{}). freq([I|Is], #{I := C} = M) -> freq(Is, M#{ I := C + 1}); freq([I|Is], M) -> freq(Is, M#{ I => 1 }); freq([], M) -> maps:to_list(M).

gb_trees用于比较的等效代码:

freq(Is) -> freq(Is, gb_trees:empty()). freq([I|Is], T) -> case gb_trees:lookup(I, T) of none -> freq(Is, gb_trees:enter(I, 1), T); {value, V} -> freq(Is, gb_trees:enter(I, V + 1, T)) end; freq([], T) -> gb_trees:to_list(T).

这也是maps相比于其他key-value数据结构不同的地方。

3 内存实现

eep中对内存的描述为 Data layout: map_ext |———————————–

14116SizeKeysValues

erl_map.h 中对内存实现的描述

/* map node * * ----------- * Eterm THING * Uint size * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = size * ---- * Eterm V1 * ... * Eterm Vn, where n = size * ----------- */ /* the head-node is a bitmap or array with an untagged size */

maps 为boxed 对象, 开头为boxed对象的必要tag,接下来为size, 之后Eterm为keys( 指向了一段连续的内存key tuple), 之后为value tuple 我们可以从源码 erl_map.c erts_maps_get/2 实现中验证这种看法, 这个函数的目的是得到key对应的value

const Eterm * erts_maps_get(Eterm key, Eterm map) { Uint32 hx; if (is_flatmap(map)) { Eterm *ks, *vs; flatmap_t *mp; Uint n, i; mp = (flatmap_t *)flatmap_val(map); n = flatmap_get_size(mp); if (n == 0) { return NULL; } ks = (Eterm *)tuple_val(mp->keys) + 1; vs = flatmap_get_values(mp); if (is_immed(key)) { for (i = 0; i < n; i++) { if (ks[i] == key) { return &vs[i]; } } } else { for (i = 0; i < n; i++) { if (EQ(ks[i], key)) { return &vs[i]; } } } return NULL; } ASSERT(is_hashmap(map)); hx = hashmap_make_hash(key); return erts_hashmap_get(hx, key, map); }

可以看出先在ks的tuple中找到key对应的index i, 然后从value的tuple vs[i] 得到。

4.使用场景

有很多种说法,

4.1. 替换record ,

No more need for records

4.2 更好的key-value 数据结构

也有认为是将maps定义为一个具有模式匹配的更好的key-value数据结构。虽然从上面实现上看并不是很理想, 比如当寻找某个值的时候其实是遍历了整个keys tuple,o(N) 的时间复杂度, 我们可以在实际项目中看到的是maps 替换了proplists,但是, 相比于其他比如dict, gb_tree, 还没有优势。

5.后语:

自己只是很简单的看了下目前maps的接口,使用和内存实现,以及自己看到的使用情况。更加具体的内容可以看引用中大神的blog

6. 引用

6.1. yufeng Erlang 新数据类型Map的定位和性能 6.2. siyao Erlang 的新数据结构 map 浅析 6.3. 坚强2002 当我们谈论Erlang Maps时,我们谈论什么 Part 1 and 当我们谈论Erlang Maps时,我们谈论什么 Part 2 6.4. learnyousomeerlang

转载请注明原文地址: https://www.6miu.com/read-2150005.html

最新回复(0)