5  地图

5  地图

这份关于高效使用地图的指南首先简要介绍了记录和地图之间的选择，然后是三个部分，提供了关于使用地图作为记录、字典和集合替代品的具体（但简要）建议。剩下的部分更深入地探讨了地图的实现方式、地图语法，以及最后是 maps 模块中的函数。

本章中使用的术语

  • 最多包含 32 个元素的地图将非正式地称为小地图。
  • 包含超过 32 个元素的地图将非正式地称为大地图。

5.1  地图还是记录？

如果遵循本章中的建议，记录与使用小地图代替记录的性能预计是相似的。因此，记录和地图之间的选择应该基于数据结构的所需属性，而不是性能。

记录相对于地图的优势在于

  • 如果记录字段的名称拼写错误，将会出现编译错误。如果地图键的拼写错误，编译器不会给出警告，程序将在运行时以某种方式失败。
  • 记录使用的内存比地图略少，并且预计在大多数情况下性能略微优于地图。

记录相对于地图的缺点是，如果向记录添加新字段，则使用该记录的所有代码都必须重新编译。因此，建议只在可以轻松地全部重新编译的代码单元中使用记录，例如在一个应用程序或一个模块中。

  • 使用地图语法，而不是 maps 模块中的函数。

  • 避免在地图中拥有超过 32 个元素。一旦地图中超过 32 个元素，它将需要更多内存，并且键将无法再与地图的其他实例共享。

  • 在创建新地图时，始终使用将要使用的所有键创建地图。为了最大限度地共享键（从而最大限度地减少内存使用），创建一个使用地图语法构建地图的单个函数，并始终使用它。

  • 始终使用 := 运算符更新地图（即，要求已经存在具有该键的元素）。:= 运算符效率略高，并且有助于捕获键的拼写错误。

  • 尽可能一次匹配多个地图元素。

  • 尽可能一次更新多个地图元素。

  • 避免使用默认值和 maps:get/3 函数。如果有默认值，地图不同实例之间的键共享将不太有效，并且无法一次性匹配具有默认值的多个元素。

  • 为了避免处理可能缺少某些键的地图，maps:merge/2 可以有效地添加多个默认值。例如

          DefaultMap = #{shoe_size => 42, editor => emacs},
      MapWithDefaultsApplied = maps:merge(DefaultMap, OtherMap)

使用地图作为字典意味着以下使用模式

  • 键通常是编译时未知的变量。

  • 地图中可以有任意数量的元素。

  • 通常，一次只查找或更新一个元素。

鉴于这种使用模式，使用地图语法和 maps 模块之间的性能差异通常很小。因此，使用哪一种主要取决于个人喜好。

地图通常是最有效的字典数据结构，但也有一些例外

  • 如果需要经常将字典转换为排序列表，或从排序列表转换为字典，使用 gb_trees 可能是一个更好的选择。

  • 如果所有键都是非负整数，array 模块可能是一个更好的选择。

从 OTP 24 开始，sets 模块可以选择将集合表示为地图。例如

1> sets:new([{version,2}]).
#{}
2> sets:from_list([x,y,z], [{version,2}]).
#{x => [],y => [],z => []}

由地图支持的 sets 通常是最有效的集合表示，但有一些可能的例外

  • ordsets:intersection/2 可能比 sets:intersection/2 更有效。如果经常使用交集操作，并且避免对集合中的单个元素进行操作（例如 is_element/2），那么 ordsets 可能比 sets 更合适。

  • 如果经常使用交集操作，并且对集合中的单个元素进行操作（例如 is_element/2）也必须高效，那么 gb_sets 可能比 sets 更合适。

  • 如果集合的元素是在一个相当紧凑的范围内变化的整数，那么该集合可以表示为一个整数，其中每一位代表集合中的一个元素。并集操作由 bor 执行，交集操作由 band 执行。

在内部，地图根据地图中元素的数量有两种不同的表示。当地图的大小超过 32 个元素，或者缩减到 32 个元素或更少时，表示方式就会改变。

  • 最多包含 32 个元素的地图具有紧凑的表示，使其适合作为记录的替代品。
  • 包含超过 32 个元素的地图表示为一棵树，无论其中有多少元素，都可以高效地搜索和更新。

小地图在运行时系统内部看起来像这样

FLATMAP N 键 值1 . . . 值N

表 5.1：  小地图的表示

FLATMAP
小地图的标签（在运行时系统的源代码中称为扁平地图）。
N
地图中元素的数量。
键
包含地图键的元组：{Key1,...,KeyN}。键是排序的。
值1
对应于键元组中第一个键的值。
值N
对应于键元组中最后一个键的值。

例如，让我们看看地图 #{a => foo, z => bar} 是如何表示的

FLATMAP 2 {a,z} foo bar

表 5.2：  #{a => foo, z => bar}

让我们更新地图：M#{q => baz}。现在地图看起来像这样

FLATMAP 3 {a,q,z} foo baz bar

表 5.3：  #{a => foo, q => baz, z => bar}

最后，更改一个元素的值：M#{z := bird}。现在地图看起来像这样

FLATMAP 3 {a,q,z} foo baz bird

表 5.4：  #{a => foo, q => baz, z => bird}

当更新现有键的值时，键元组不会更新，从而允许键元组与具有相同键的地图的其他实例共享。实际上，键元组可以在所有具有相同键的地图之间共享，只要小心一些。为了做到这一点，定义一个返回地图的函数。例如

new() ->
    #{a => default, b => default, c => default}.

这样定义后，键元组 {a,b,c} 将成为一个全局字面量。为了确保在创建地图实例时共享键元组，始终调用 new() 并修改返回的地图

    (SOME_MODULE:new())#{a := 42}.

对小地图使用地图语法特别有效。只要键在编译时已知，地图就会一次性更新，使得更新地图的时间基本上是恒定的，与更新的键数量无关。匹配也是如此。（当键是变量时，一个或多个键可能相同，因此操作需要从左到右依次执行。）

小地图的内存大小是所有键和值的大小加上 5 个字。有关内存大小的更多信息，请参阅 高级。

包含超过 32 个元素的地图是用 哈希数组映射树 (HAMT) 实现的。大地图可以高效地搜索和更新，无论地图中有多少元素。

与小地图相比，在大地图上使用地图语法匹配或更新多个元素所获得的性能提升较少。执行时间大致与匹配或更新的元素数量成正比。

大地图的存储开销高于小地图。对于大地图来说，除了键和值之外的额外字数与元素数量大致成正比。对于一个包含 33 个元素的地图来说，根据 高级 中的公式，开销至少是 53 个堆字（而对于小地图来说，无论元素数量如何，开销都是 5 个额外字）。

当大型地图更新时，更新后的地图和原始地图将共享 HAMT 的公共部分，但共享的效率永远无法与小型地图的最佳可能的键元组共享相媲美。

因此，如果使用地图而不是记录，并且预计将创建许多地图实例，从内存效率的角度来看，最好避免使用大型地图（例如，通过将相关的地图元素分组到子地图中以减少元素的数量）。

使用地图语法通常比使用 maps 模块中相应的函数效率更高。

对于以下只能通过地图语法实现的操作，地图语法的效率提升更为明显

  • 匹配多个字面量键

  • 更新多个字面量键

  • 向地图添加多个字面量键

例如

DO

    Map = Map1#{x := X, y := Y, z := Z}

DO NOT

    Map2 = maps:update(x, X, Map1),
    Map3 = maps:update(y, Y, Map2),
    Map = maps:update(z, Z, Map3)

如果地图是一个小型地图，第一个示例的运行速度大约是后者的三倍。

请注意，对于变量键，元素是从左到右顺序更新的。例如，对于以下使用变量键的更新

    Map = Map1#{Key1 := X, Key2 := Y, Key3 := Z}

编译器会将其重写为以下形式，以确保从左到右应用更新

    Map2 = Map1#{Key1 := X},
    Map3 = Map2#{Key2 := Y},
    Map = Map3#{Key3 := Z}

如果已知某个键存在于地图中，对于小型地图，使用 := 运算符比使用 => 运算符效率略高。

以下是一些关于 maps 模块中大多数函数的说明。对于每个函数，都将说明其实现语言（C 或 Erlang）。我们之所以提到语言，是因为它暗示了函数的效率。

  • 如果一个函数是用 C 实现的，那么在 Erlang 中几乎不可能以更高的效率实现相同的功能。

  • 然而，有可能超过 Erlang 中实现的 maps 模块函数的效率，因为它们通常以一种试图使所有可能输入的性能都合理的方式实现。

    例如，maps:map/2 会遍历地图的所有元素，调用映射函数，将更新后的地图元素收集到一个列表中，最后使用 maps:from_list/1 将列表转换回地图。如果已知地图中最多只有 1% 的值会发生变化，那么只更新发生变化的值可能更高效。

注意

本节中给出的实现细节在将来可能会发生变化。

maps:filter/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的地图。如果已知只有少数值会被删除，那么避免使用 maps:filter/2 并编写一个使用 maps:remove/3 删除不需要的值的函数可能会更高效。

maps:filtermap/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的地图。有关如何实现更高效版本的提示，请参阅 maps:map/2 和 maps:filter/2 的说明。

maps:find/2 是用 C 实现的。

与使用 maps:find/2 相比，使用地图匹配语法效率略高，因为将避免构建 {ok,Value} 元组。

作为一项优化，编译器会将对 maps:get/2 的调用重写为对保护 BIF map_get/2 的调用。对保护 BIF 的调用比对其他 BIF 的调用更高效，使得性能与使用地图匹配语法类似。

如果地图很小，并且键是在编译时已知的常量，那么使用地图匹配语法比多次调用 maps:get/2 效率更高。

作为一项优化，编译器会将对 maps:get/3 的调用重写为类似于以下 Erlang 代码：

    Result = case Map of
                 #{Key := Value} -> Value;
                 #{} -> Default
             end

这相当高效，但如果使用小型地图作为记录的替代方案，最好不要依赖默认值，因为它会阻止共享键，最终可能会使用比不在地图中存储默认值节省的内存更多的内存。

如果确实需要默认值，请考虑将默认值放在一个地图中，并将该地图与另一个地图合并，而不是多次调用 maps:get/3

    DefaultMap = #{Key1 => Value2, Key2 => Value2, ..., KeyN => ValueN},
    MapWithDefaultsApplied = maps:merge(DefaultMap, OtherMap)

只要默认地图包含将要使用的所有键，而不仅仅是包含默认值的键，这有助于在默认地图和你应用默认值的默认地图之间共享键。这是否比多次调用 maps:get/3 更快取决于地图的大小和默认值的数量。

变更

在 OTP 26.0 之前，maps:get/3 通过调用函数来实现，而不是将其重写为 Erlang 表达式。现在它速度略快，但不再可跟踪。

maps:intersect/2 和 maps:intersect_with/3 是用 Erlang 实现的。它们都使用 maps:from_list/1 创建新的地图。

注意

地图通常是实现集合的最有效方式，但有一个例外是交集操作，在交集操作中，对 ordsets 上的 ordsets:intersection/2 可能比对作为地图实现的集合上的 maps:intersect/2 更有效。

maps:from_list/1 是用 C 实现的。

maps:from_keys/2 是用 C 实现的。

作为一项优化，编译器会将对 maps:is_key/2 的调用重写为对保护 BIF is_map_key/2 的调用。对保护 BIF 的调用比对其他 BIF 的调用更高效，使得性能与使用地图匹配语法类似。

maps:iterator/1 在 C 和 Erlang 中得到了高效的实现。

maps:keys/1 是用 C 实现的。如果需要对结果列表进行排序，请使用 lists:sort/1 对结果进行排序。

maps:map/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的地图。如果已知只有少数值会被更新，那么避免使用 maps:map/2 并编写一个调用 maps:update/3 仅更新已更改值的函数可能会更高效。

maps:merge/2 是用 C 实现的。对于 小型地图，如果某个参数地图包含所有键，那么键元组可能会与该参数地图共享。如果可能，请优先使用字面量键元组。

变更

maps:merge/2 对键元组的共享是在 OTP 26.0 中引入的。旧版本总是会在调用者的堆上构造一个新的键元组。

maps:merge_with/3 是用 Erlang 实现的。它会更新并返回两个地图中较大的那个。

编译器会将对 maps:new/0 的调用重写为使用 #{} 语法来构造一个空地图。

maps:next/1 在 C 和 Erlang 中得到了高效的实现。

maps:put/3 是用 C 实现的。

如果已知该键已存在于地图中，那么 maps:update/3 比 maps:put/3 效率略高。

如果键是在编译时已知的常量，那么使用地图更新语法和 => 运算符比多次调用 maps:put/3 效率更高，特别是对于小型地图。

maps:remove/2 是用 C 实现的。

作为一项优化，编译器会将对 maps:size/1 的调用重写为对保护 BIF map_size/1 的调用。对保护 BIF 的调用比对其他 BIF 的调用更高效。

maps:take/2 是用 C 实现的。

maps:to_list/1 在 C 和 Erlang 中得到了高效的实现。如果需要对结果列表进行排序，请使用 lists:sort/1 对结果进行排序。

注意

地图通常比 gb_trees 性能更高，但如果需要频繁地进行排序列表的转换，那么 gb_trees 可能是更好的选择。

maps:update/3 是用 C 实现的。

如果键是在编译时已知的常量，那么使用地图更新语法和 := 运算符比多次调用 maps:update/3 效率更高，特别是对于 小型地图。

maps:values/1 是用 C 实现的。

maps:with/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的地图。

maps:without/2 是用 Erlang 实现的。它返回输入地图的修改后的副本。

版权所有 © 2001-2024 爱立信 AB。保留所有权利。