Zusammenführen von Wörterbüchern in C#

Question

Wie lassen sich 2 oder mehr Wörterbücher am besten zusammenführen ( Dictionary<T1,T2> ) in C#? (3.0-Funktionen wie LINQ sind in Ordnung).

Ich denke an eine Methodensignatur in der Art von:

public static Dictionary<TKey,TValue>
                 Merge<TKey,TValue>(Dictionary<TKey,TValue>[] dictionaries);

o

public static Dictionary<TKey,TValue>
                 Merge<TKey,TValue>(IEnumerable<Dictionary<TKey,TValue>> dictionaries);

EDIT: Ich habe eine coole Lösung von JaredPar und Jon Skeet, aber ich dachte an etwas, das mit doppelten Schlüsseln umgehen kann. Im Falle einer Kollision spielt es keine Rolle, welcher Wert im Diktat gespeichert wird, solange er konsistent ist.

Answer 1

Basierend auf den obigen Antworten, aber durch Hinzufügen eines Func-Parameters, damit der Aufrufer die Duplikate behandeln kann:

public static Dictionary<TKey, TValue> Merge<TKey, TValue>(this IEnumerable<Dictionary<TKey, TValue>> dicts, 
                                                           Func<IGrouping<TKey, TValue>, TValue> resolveDuplicates)
{
    if (resolveDuplicates == null)
        resolveDuplicates = new Func<IGrouping<TKey, TValue>, TValue>(group => group.First());

    return dicts.SelectMany<Dictionary<TKey, TValue>, KeyValuePair<TKey, TValue>>(dict => dict)
                .ToLookup(pair => pair.Key, pair => pair.Value)
                .ToDictionary(group => group.Key, group => resolveDuplicates(group));
}

Answer 2

Wie wäre es mit einer zusätzlichen params Überlastung?

Außerdem sollten Sie sie als IDictionary für maximale Flexibilität.

public static IDictionary<TKey, TValue> Merge<TKey, TValue>(IEnumerable<IDictionary<TKey, TValue>> dictionaries)
{
    // ...
}

public static IDictionary<TKey, TValue> Merge<TKey, TValue>(params IDictionary<TKey, TValue>[] dictionaries)
{
    return Merge((IEnumerable<TKey, TValue>) dictionaries);
}

Answer 3

In Anbetracht der Leistung beim Suchen und Löschen von Wörterbuchschlüsseln da es sich um Hash-Operationen handelt, und da der Wortlaut der Frage am besten Meiner Meinung nach ist der unten stehende Ansatz vollkommen richtig, und die anderen sind meiner Meinung nach etwas zu kompliziert.

    public static void MergeOverwrite<T1, T2>(this IDictionary<T1, T2> dictionary, IDictionary<T1, T2> newElements)
    {
        if (newElements == null) return;

        foreach (var e in newElements)
        {
            dictionary.Remove(e.Key); //or if you don't want to overwrite do (if !.Contains()
            dictionary.Add(e);
        }
    }

ODER wenn Sie in einer Multithread-Anwendung arbeiten und Ihr Wörterbuch ohnehin thread-sicher sein muss, sollten Sie dies tun:

    public static void MergeOverwrite<T1, T2>(this ConcurrentDictionary<T1, T2> dictionary, IDictionary<T1, T2> newElements)
    {
        if (newElements == null || newElements.Count == 0) return;

        foreach (var ne in newElements)
        {
            dictionary.AddOrUpdate(ne.Key, ne.Value, (key, value) => value);
        }
    }

Sie könnten dann wrap dies, damit es eine Aufzählung von Wörterbüchern zu behandeln. Unabhängig davon sehen Sie etwa ~O(3n) (alle Bedingungen sind perfekt), da die .Add() wird eine zusätzliche, unnötige, aber praktisch kostenlose Maßnahme durchgeführt, Contains() hinter den Kulissen. Ich glaube nicht, dass es noch viel besser wird.

Wenn Sie zusätzliche Operationen bei großen Sammlungen begrenzen wollen, sollten Sie die Count jedes Wörterbuchs, das Sie zusammenführen wollen, und setzen Sie die Kapazität des Zielwörterbuchs auf diesen Wert, wodurch die späteren Kosten der Größenänderung vermieden werden. Das Endprodukt sieht also etwa so aus...

    public static IDictionary<T1, T2> MergeAllOverwrite<T1, T2>(IList<IDictionary<T1, T2>> allDictionaries)
    {
        var initSize = allDictionaries.Sum(d => d.Count);
        var resultDictionary = new Dictionary<T1, T2>(initSize);
        allDictionaries.ForEach(resultDictionary.MergeOverwrite);
        return resultDictionary;
    }

Beachten Sie, dass ich eine IList<T> zu dieser Methode... vor allem, weil man bei der Aufnahme eines IEnumerable<T> haben Sie sich für mehrere Aufzählungen desselben Satzes geöffnet, was sehr kostspielig sein kann, wenn Sie Ihre Sammlung von Wörterbüchern aus einer verzögerten LINQ-Anweisung erhalten haben.

Answer 4

Vereinfacht wieder von früher ohne LINQ und ein bool-Standard der nicht-destruktive zusammenführen, wenn vorhanden oder vollständig überschreiben, wenn wahr, anstatt mit einem enum. Es entspricht immer noch meinen eigenen Bedürfnissen, ohne dass ein komplizierterer Code jemals erforderlich ist:

using System.Collections.Generic;
using System.Linq;

public static partial class Extensions
{
    public static void Merge<K, V>(this IDictionary<K, V> target, 
                                   IDictionary<K, V> source, 
                                   bool overwrite = false)
    {
        foreach (KeyValuePair _ in source)
            if (overwrite || !target.ContainsKey(_.Key))
                target[_.Key] = _.Value;
    }
}

Answer 5

Die Party ist jetzt so gut wie tot, aber hier ist eine "verbesserte" Version von user166390, die ihren Weg in meine Erweiterungsbibliothek gefunden hat. Abgesehen von einigen Details, habe ich einen Delegaten hinzugefügt, um den zusammengefassten Wert zu berechnen.

/// <summary>
/// Merges a dictionary against an array of other dictionaries.
/// </summary>
/// <typeparam name="TResult">The type of the resulting dictionary.</typeparam>
/// <typeparam name="TKey">The type of the key in the resulting dictionary.</typeparam>
/// <typeparam name="TValue">The type of the value in the resulting dictionary.</typeparam>
/// <param name="source">The source dictionary.</param>
/// <param name="mergeBehavior">A delegate returning the merged value. (Parameters in order: The current key, The current value, The previous value)</param>
/// <param name="mergers">Dictionaries to merge against.</param>
/// <returns>The merged dictionary.</returns>
public static TResult MergeLeft<TResult, TKey, TValue>(
    this TResult source,
    Func<TKey, TValue, TValue, TValue> mergeBehavior,
    params IDictionary<TKey, TValue>[] mergers)
    where TResult : IDictionary<TKey, TValue>, new()
{
    var result = new TResult();
    var sources = new List<IDictionary<TKey, TValue>> { source }
        .Concat(mergers);

    foreach (var kv in sources.SelectMany(src => src))
    {
        TValue previousValue;
        result.TryGetValue(kv.Key, out previousValue);
        result[kv.Key] = mergeBehavior(kv.Key, kv.Value, previousValue);
    }

    return result;
}