Supposons que j'ai deux cartes ( m1, m2 ) qui devraient avoir pour la plupart des paires de kv identiques, mais chacune peut avoir des entrées, l'autre pas. En fin de compte, je veux une carte qui contient toutes les paires kv des deux cartes, donc à un niveau élevé, je veux les fusionner.

Cependant, étant donné les implémentations de Map.merge (Erlang BIF) et Map. split (récursion de queue), ainsi que l'heuristique de s'attendre à ce que les différences soient peu proportionnelles à la taille de la carte, laquelle des options ci-dessous est la mieux adaptée pour atteindre le résultat souhaité?

  1. Commencez par diviser pour trouver les paires de kv uniques à m2 et ne fusionner que celles

    ...
    {_duplicateKeys, m2only} = Map.split(m2, Map.keys(m1))
    Map.merge(m1, m2only)
    ...
    
  2. Ou simplement fusionner, en espérant que la mise en œuvre optimisera la construction de la carte

    ...
    Map.merge(m1, m2)
    ...
    
2
Nolan330 21 avril 2017 à 01:24

3 réponses

Meilleure réponse

Je m'attendrais à ce que le coût de split l'emporte sur les économies réalisées en merge.

Lorsque les cartes sont volumineuses, il semble que le BIF utilise hashmap_merge, qui a ce commentaire dans la source:

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

L'implémentation semble détecter quand il y a des sous-arbres identiques dans les cartes:

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 */
3
Mike Buhot 20 avril 2017 à 22:42

Après avoir consulté la documentation de Map.merge BIF et en discutant dans # elixir-lang avec asonge, il a été décidé que la simple fusion était la solution appropriée .

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

Il y a quelques nuances à la solution: l'échelle de la carte est importante pour décider comment la carte est représentée en mémoire - flatmap pour petit, hashmap pour grand.

Cependant, la simple fusion a été choisie car un hashmap est utilisé pour les grandes cartes où l'optimisation serait importante. Étant donné que de nombreux nœuds se compareront égaux dans la plupart des cartes similaires, l'algorithme ne devrait avoir besoin que de reconstruire une petite partie de l'arborescence sous-jacente à la carte. Du moins, c'est ce que nos recherches indiquent; cela n'a pas été testé dans la pratique

2
Nolan330 20 avril 2017 à 22:39

Je choisirais l'approche Map.merge. L'optimisation prématurée est généralement un anti-pattern. Si vous trouvez plus tard des problèmes de performances, vous pouvez alors optimiser. Les BIF Erlang sont généralement assez performants.

ÉDITER:

Voici une référence rapide

spallen@Steves-MacBook-Pro ~/myprojects/elixir/maps  time ./map.exs                         
MapDemo running count: 5000000
./map.exs  21.30s user 2.73s system 98% cpu 24.371 total
spallen@Steves-MacBook-Pro  ~/myprojects/elixir/maps  time ./split.exs                       
SplitDemo running count: 5000000
./split.exs  25.68s user 4.28s system 98% cpu 30.479 total

Voici le code

#! /usr/local/bin//elixir
defmodule MapDemo do
  @upper 5000000
  def run do
    IO.puts "MapDemo running count: #{@upper}"
    map1 =
      0..@upper
      |> Enum.map(& {"key_#{&1}", &1})
      |> Enum.into(%{})

    map2 =
      100..(@upper + 100)
      |> Enum.map(& {"key_#{&1}", &1})
      |> Enum.into(%{})

    Map.merge(map1, map2)
  end
end

MapDemo.run

Et

#! /usr/local/bin//elixir
defmodule SplitDemo do
  @upper 5000000
  def run do
    IO.puts "SplitDemo running count: #{@upper}"
    map1 =
      0..@upper
      |> Enum.map(& {"key_#{&1}", &1})
      |> Enum.into(%{})

    map2 =
      100..(@upper + 100)
      |> Enum.map(& {"key_#{&1}", &1})
      |> Enum.into(%{})

    {_duplicateKeys, m2only} = Map.split(map2, Map.keys(map1))
    Map.merge(map1, m2only)
  end
end

SplitDemo.run
3
Steve Pallen 20 avril 2017 à 23:08