thèse - Comment puis-je fusionner deux hachages sans doublons écrasés dans Ruby?




doctorat big (4)

Il existe un moyen dans la bibliothèque Ruby standard de fusionner les hachages sans écraser les valeurs existantes ou réaffecter le hachage.

important_hash.merge!(defaults) { |key, important, default| important }

Existe-t-il un moyen simple ou élégant de fusionner deux hachages sans écraser les clés en double?

Autrement dit, si la clé est présente dans le hachage d'origine, je ne veux pas changer sa valeur.


Si vous avez deux hachages, options et defaults , et que vous souhaitez fusionner les defaults par defaults dans les options sans écraser les clés existantes, ce que vous voulez vraiment faire est l'inverse: fusionner les options en defaults par defaults :

options = defaults.merge(options)

Ou, si vous utilisez Rails, vous pouvez faire:

options.reverse_merge!(defaults)

Si votre problème est que le hachage d'origine et le second ont tous les deux des clés dupliquées et que vous ne voulez pas les écraser dans les deux sens, vous devrez peut-être opter pour une simple fusion manuelle avec vérification et gestion des collisions:

hash2.each_key do |key|
  if ( hash1.has_key?(key) )
       hash1[ "hash2-originated-#{key}" ] = hash2[key]
  else
       hash1[key]=hash2[key]
  end
end

Évidemment, ceci est très rudimentaire et suppose que hash1 n'a pas de clé appelée "hash2-originated-whatever" - vous feriez mieux d'ajouter simplement un nombre à la clé pour qu'elle devienne key1, key2 et ainsi de suite jusqu'à ce que vous frappiez celui qui n'est pas déjà en hash1. De plus, je n'ai pas fait de rubis depuis quelques mois, donc ce n'est probablement pas correct sur le plan syntaxique, mais vous devriez être capable de comprendre l'essentiel.

Vous pouvez également redéfinir la valeur de la clé en tant que tableau afin que hash1 [key] renvoie la valeur d'origine de hash1 et la valeur de hash2. Cela dépend de ce que vous voulez que votre résultat soit vraiment.


Hélas la plupart des réponses sont O(n^2) .

Voici une solution O(n) ,

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => 'the"

Quelle est la complexité de cela?

  • Fonctionne en O(n) et se brise au premier match
  • Utilise la mémoire O(n) , mais seulement le montant minimal

Maintenant, en fonction de la fréquence des doublons dans votre tableau, ces temps d'exécution peuvent devenir encore meilleurs. Par exemple, si le tableau de taille O(n) a été échantillonné à partir d'une population de k << n éléments différents, seule la complexité pour l'exécution et l'espace devient O(k) , mais il est plus probable que l'affiche originale valide l'entrée et veut s'assurer qu'il n'y a pas de doublons. Dans ce cas, la complexité de la mémoire et de l'exécution est O(n) car nous nous attendons à ce que les éléments n'aient pas de répétitions pour la majorité des entrées.





ruby