dictionary - Erlang/Elixir 合并带有大多数重复键的映射

Question

假设我有两张 map (m1, m2)，它们应该具有大部分相同的 kv 对，但每张 map 都可能有另一个没有的条目。最终，我想要一个包含来自两个 map 的所有 kv 对的 map ，因此在较高级别我想合并它们。

但是，考虑到 Map.merge 的实现(Erlang BIF) 和 Map.split (尾递归)，以及期望差异与 map 大小成正比的启发式方法，以下哪个选项更适合实现预期结果？

1. 首先拆分找到m2特有的kv对，只合并那些

   ...
   {_duplicateKeys, m2only} = Map.split(m2, Map.keys(m1))
   Map.merge(m1, m2only)
   ...
   

2. 或者只是合并，希望实现能优化构建 map

   ...
   Map.merge(m1, m2)
   ...
   

Answer 1

我预计 split 的成本会超过 merge 的任何节省。

本地图很大时，BIF 看起来像使用 hashmap_merge ，在来源中有此评论:

/*
 * Strategy: Do depth-first traversal of both trees (at the same time)
 * and merge each pair of nodes.
 */

该实现似乎可以检测 map 中何时存在相同的子树:

switch (sp->mix) {
    case 0: /* Nodes A and B contain the *EXACT* same sub-trees
               => fall through and reuse nodeA */

    case 1: /* Only unique A stuff => reuse nodeA */
        res = sp->nodeA;
        break;

    case 2: /* Only unique B stuff => reuse nodeB */
        res = sp->nodeB;
        break;

    case 3: /* We have a mix => must build new node */