Scalanie słowników w C #

Jaki jest najlepszy sposób scalenia 2 lub więcej słowników (Dictionary<T1,T2> ) w C #? (Funkcje 3.0, takie jak LINQ, są w porządku).

Myślę o sygnaturze metody w następujący sposób:

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

lub

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

EDYCJA: Mam fajne rozwiązanie od JaredPara i Jona Skeeta, ale myślałem o czymś, co obsługuje duplikaty kluczy. W przypadku kolizji nie ma znaczenia, która wartość jest zapisywana w dykcie, o ile jest spójna.

Zależy to częściowo od tego, co chcesz się wydarzyć, jeśli napotkasz duplikaty. Na przykład możesz wykonać:

var result = dictionaries.SelectMany(dict => dict)
                         .ToDictionary(pair => pair.Key, pair => pair.Value);

Spowoduje to wyjątek, jeśli otrzymasz duplikaty kluczy.

EDYCJA: Jeśli użyjesz ToLookup, otrzymasz odnośnik, który może mieć wiele wartości na klucz. Państwo mogłoby następnie przekonwertować do słownika:

var result = dictionaries.SelectMany(dict => dict)
                         .ToLookup(pair => pair.Key, pair => pair.Value)
                         .ToDictionary(group => group.Key, group => group.First());

Jest to trochę brzydkie - i nieefektywne - ale to najszybszy sposób na zrobienie tego pod względem kodu. (Wprawdzie go nie testowałem).

Możesz oczywiście napisać własną metodę rozszerzenia ToDictionary2 (o lepszej nazwie, ale nie mam teraz czasu na wymyślenie jednej) - nie jest to strasznie trudne, po prostu nadpisywanie (lub ignorowanie) duplikatów kluczy. Ważną rzeczą (moim zdaniem) jest użycie SelectMany i uświadomienie sobie, że słownik obsługuje iterację nad parami klucz / wartość.

Zrobiłbym to w ten sposób:

dictionaryFrom.ToList().ForEach(x => dictionaryTo.Add(x.Key, x.Value));

Proste i łatwe. Zgodnie z tym postem na blogu jest nawet szybszy niż większość pętli, ponieważ jego podstawowa implementacja uzyskuje dostęp do elementów według indeksu, a nie modułu wyliczającego (zobacz tę odpowiedź) .

Będzie oczywiście rzucał wyjątek, jeśli istnieją duplikaty, więc musisz to sprawdzić przed scaleniem.

Nie wybuchnie to, jeśli istnieje wiele kluczy (klucze „jaśniejsze” zastępują klucze „lewe”), mogą łączyć wiele słowników (w razie potrzeby) i zachowują typ (z zastrzeżeniem, że wymaga znaczącego domyślnego konstruktora publicznego):

public static class DictionaryExtensions
{
    // Works in C#3/VS2008:
    // Returns a new dictionary of this ... others merged leftward.
    // Keeps the type of 'this', which must be default-instantiable.
    // Example: 
    //   result = map.MergeLeft(other1, other2, ...)
    public static T MergeLeft<T,K,V>(this T me, params IDictionary<K,V>[] others)
        where T : IDictionary<K,V>, new()
    {
        T newMap = new T();
        foreach (IDictionary<K,V> src in
            (new List<IDictionary<K,V>> { me }).Concat(others)) {
            // ^-- echk. Not quite there type-system.
            foreach (KeyValuePair<K,V> p in src) {
                newMap[p.Key] = p.Value;
            }
        }
        return newMap;
    }

}

Trywialnym rozwiązaniem byłoby:

using System.Collections.Generic;
...
public static Dictionary<TKey, TValue>
    Merge<TKey,TValue>(IEnumerable<Dictionary<TKey, TValue>> dictionaries)
{
    var result = new Dictionary<TKey, TValue>();
    foreach (var dict in dictionaries)
        foreach (var x in dict)
            result[x.Key] = x.Value;
    return result;
}

Spróbuj wykonać następujące czynności

static Dictionary<TKey, TValue>
    Merge<TKey, TValue>(this IEnumerable<Dictionary<TKey, TValue>> enumerable)
{
    return enumerable.SelectMany(x => x).ToDictionary(x => x.Key, y => y.Value);
}

Dictionary<String, String> allTables = new Dictionary<String, String>();
allTables = tables1.Union(tables2).ToDictionary(pair => pair.Key, pair => pair.Value);

Jestem bardzo spóźniony na imprezę i być może coś mi brakuje, ale jeśli nie ma duplikatów kluczy lub, jak mówi OP, „W przypadku kolizji nie ma znaczenia, która wartość jest zapisywana w dyktonie, o ile spójne: „co jest nie tak z tym (łączenie D2 w D1)?

foreach (KeyValuePair<string,int> item in D2)
            {
                 D1[item.Key] = item.Value;
            }

Wydaje się to dość proste, może zbyt proste. Zastanawiam się, czy coś mi umknęło. Tego używam w kodzie, w którym wiem, że nie ma duplikatów kluczy. Nadal jednak testuję, więc chciałbym wiedzieć, czy coś przeoczyłem, zamiast dowiedzieć się później.

Poniższe działa dla mnie. Jeśli są duplikaty, użyje wartości dictA.

public static IDictionary<TKey, TValue> Merge<TKey, TValue>(this IDictionary<TKey, TValue> dictA, IDictionary<TKey, TValue> dictB)
    where TValue : class
{
    return dictA.Keys.Union(dictB.Keys).ToDictionary(k => k, k => dictA.ContainsKey(k) ? dictA[k] : dictB[k]);
}

Oto funkcja pomocnika, której używam:

using System.Collections.Generic;
namespace HelperMethods
{
    public static class MergeDictionaries
    {
        public static void Merge<TKey, TValue>(this IDictionary<TKey, TValue> first, IDictionary<TKey, TValue> second)
        {
            if (second == null || first == null) return;
            foreach (var item in second) 
                if (!first.ContainsKey(item.Key)) 
                    first.Add(item.Key, item.Value);
        }
    }
}

Opcja 1: Zależy to od tego, co chcesz zrobić, jeśli masz pewność, że nie masz duplikatu klucza w obu słownikach. niż możesz zrobić:

var result = dictionary1.Union(dictionary2).ToDictionary(k => k.Key, v => v.Value)

Uwaga: spowoduje to wygenerowanie błędu, jeśli w słownikach pojawią się duplikaty kluczy.

Opcja 2: Jeśli możesz mieć duplikat klucza, będziesz musiał obsługiwać duplikat klucza za pomocą klauzuli where.

var result = dictionary1.Union(dictionary2.Where(k => !dictionary1.ContainsKey(k.Key))).ToDictionary(k => k.Key, v => v.Value)

Uwaga: nie otrzyma duplikatu klucza. jeśli będzie jakikolwiek duplikat klucza, to dostanie on klucz Dictionary1.

Opcja 3: Jeśli chcesz użyć ToLookup. otrzymasz odnośnik, który może mieć wiele wartości na klucz. Możesz przekonwertować to wyszukiwanie na słownik:

var result = dictionaries.SelectMany(dict => dict)
                         .ToLookup(pair => pair.Key, pair => pair.Value)
                         .ToDictionary(group => group.Key, group => group.First());

Co powiesz na dodanie paramsprzeciążenia?

Powinieneś także wpisać je tak, IDictionaryaby uzyskać maksymalną elastyczność.

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);
}

Biorąc pod uwagę wydajność wyszukiwania i usuwania kluczy słownikowych, ponieważ są to operacje haszujące, i biorąc pod uwagę, że sformułowanie pytania było najlepszym sposobem, myślę, że poniżej jest całkowicie poprawne podejście, a pozostałe są nieco zbyt skomplikowane, IMHO.

    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);
        }
    }

LUB jeśli pracujesz w aplikacji wielowątkowej, a słownik i tak musi być bezpieczny dla wątków, powinieneś to zrobić:

    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);
        }
    }

Następnie możesz to zawinąć, aby obsłużyć wyliczenie słowników. Niezależnie od tego, patrzysz na ~ O (3n) (wszystkie warunki są idealne), ponieważ .Add()zrobi to dodatkowe, niepotrzebne, ale praktycznie bezpłatne,Contains() za kulisami. Nie sądzę, żeby było znacznie lepiej.

Jeśli chcesz ograniczyć dodatkowe operacje na dużych kolekcjach, powinieneś podsumować Countkażdy słownik, który zamierzasz scalić, i ustawić pojemność słownika docelowego do tego, co pozwala uniknąć późniejszych kosztów zmiany rozmiaru. Tak więc produkt końcowy jest taki ...

    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;
    }

Zauważ, że wybrałem IList<T>tę metodę ... głównie dlatego, że jeśli ją wprowadziłeś IEnumerable<T>, otworzyłeś się na wiele wyliczeń tego samego zestawu, co może być bardzo kosztowne, jeśli masz swoją kolekcję słowników z odroczonego LINQ komunikat.

W oparciu o powyższe odpowiedzi, ale dodanie parametru Func, aby umożliwić programowi wywołującemu obsługę duplikatów:

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));
}

Partia jest już prawie martwa, ale tutaj jest „ulepszona” wersja user166390, która trafiła do mojej biblioteki rozszerzeń. Oprócz niektórych szczegółów dodałem delegata, aby obliczyć scaloną wartość.

/// <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;
}

@Tim: Powinien być komentarzem, ale komentarze nie pozwalają na edycję kodu.

Dictionary<string, string> t1 = new Dictionary<string, string>();
t1.Add("a", "aaa");
Dictionary<string, string> t2 = new Dictionary<string, string>();
t2.Add("b", "bee");
Dictionary<string, string> t3 = new Dictionary<string, string>();
t3.Add("c", "cee");
t3.Add("d", "dee");
t3.Add("b", "bee");
Dictionary<string, string> merged = t1.MergeLeft(t2, t2, t3);

Uwaga: zastosowałem modyfikację @ANeves do rozwiązania @Andrew Orsich, więc MergeLeft wygląda teraz tak:

public static Dictionary<K, V> MergeLeft<K, V>(this Dictionary<K, V> me, params IDictionary<K, V>[] others)
    {
        var newMap = new Dictionary<K, V>(me, me.Comparer);
        foreach (IDictionary<K, V> src in
            (new List<IDictionary<K, V>> { me }).Concat(others))
        {
            // ^-- echk. Not quite there type-system.
            foreach (KeyValuePair<K, V> p in src)
            {
                newMap[p.Key] = p.Value;
            }
        }
        return newMap;
    }

Wiem, że to stare pytanie, ale ponieważ teraz mamy LINQ, możesz to zrobić w jednym wierszu, takim jak ten

Dictionary<T1,T2> merged;
Dictionary<T1,T2> mergee;
mergee.ToList().ForEach(kvp => merged.Add(kvp.Key, kvp.Value));

lub

mergee.ToList().ForEach(kvp => merged.Append(kvp));

Bałam się zobaczyć skomplikowane odpowiedzi, będąc nowym w C #.

Oto kilka prostych odpowiedzi.
Scalanie d1, d2 itd. Słowniki i obsługa nakładających się klawiszy („b” w poniższych przykładach):

Przykład 1

{
    // 2 dictionaries,  "b" key is common with different values

    var d1 = new Dictionary<string, int>() { { "a", 10 }, { "b", 21 } };
    var d2 = new Dictionary<string, int>() { { "c", 30 }, { "b", 22 } };

    var result1 = d1.Concat(d2).GroupBy(ele => ele.Key).ToDictionary(ele => ele.Key, ele => ele.First().Value);
    // result1 is  a=10, b=21, c=30    That is, took the "b" value of the first dictionary

    var result2 = d1.Concat(d2).GroupBy(ele => ele.Key).ToDictionary(ele => ele.Key, ele => ele.Last().Value);
    // result2 is  a=10, b=22, c=30    That is, took the "b" value of the last dictionary
}

Przykład 2

{
    // 3 dictionaries,  "b" key is common with different values

    var d1 = new Dictionary<string, int>() { { "a", 10 }, { "b", 21 } };
    var d2 = new Dictionary<string, int>() { { "c", 30 }, { "b", 22 } };
    var d3 = new Dictionary<string, int>() { { "d", 40 }, { "b", 23 } };

    var result1 = d1.Concat(d2).Concat(d3).GroupBy(ele => ele.Key).ToDictionary(ele => ele.Key, ele => ele.First().Value);
    // result1 is  a=10, b=21, c=30, d=40    That is, took the "b" value of the first dictionary

    var result2 = d1.Concat(d2).Concat(d3).GroupBy(ele => ele.Key).ToDictionary(ele => ele.Key, ele => ele.Last().Value);
    // result2 is  a=10, b=23, c=30, d=40    That is, took the "b" value of the last dictionary
}

Bardziej złożone scenariusze znajdują się w innych odpowiedziach.
Mam nadzieję, że to pomogło.

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

public static class DictionaryExtensions
{
    public enum MergeKind { SkipDuplicates, OverwriteDuplicates }
    public static void Merge<K, V>(this IDictionary<K, V> target, IDictionary<K, V> source, MergeKind kind = MergeKind.SkipDuplicates) =>
        source.ToList().ForEach(_ => { if (kind == MergeKind.OverwriteDuplicates || !target.ContainsKey(_.Key)) target[_.Key] = _.Value; });
}

Możesz pominąć / zignorować (domyślnie) lub zastąpić duplikaty: a wujek Boba pod warunkiem, że nie jesteś zbyt wybredny co do wydajności Linq, ale wolisz zamiast tego zwięzły kod, który mogę zachować, tak jak ja: w takim przypadku możesz usunąć domyślny MergeKind.SkipDuplicates, aby wymusić wybór dla dzwoniącego i spraw, aby deweloper wiedział, jakie będą wyniki!

Zauważ, że jeśli używasz metody rozszerzenia o nazwie „Dodaj”, możesz użyć inicjatorów kolekcji, aby połączyć tyle słowników, ile potrzeba:

public static void Add<K, V>(this Dictionary<K, V> d, Dictionary<K, V> other) {
  foreach (var kvp in other)
  {
    if (!d.ContainsKey(kvp.Key))
    {
      d.Add(kvp.Key, kvp.Value);
    }
  }
}


var s0 = new Dictionary<string, string> {
  { "A", "X"}
};
var s1 = new Dictionary<string, string> {
  { "A", "X" },
  { "B", "Y" }
};
// Combine as many dictionaries and key pairs as needed
var a = new Dictionary<string, string> {
  s0, s1, s0, s1, s1, { "C", "Z" }
};

Scalanie przy użyciu metody rozszerzenia. Nie zgłasza wyjątku, gdy istnieją duplikaty kluczy, ale zamienia te klucze na klucze z drugiego słownika.

internal static class DictionaryExtensions
{
    public static Dictionary<T1, T2> Merge<T1, T2>(this Dictionary<T1, T2> first, Dictionary<T1, T2> second)
    {
        if (first == null) throw new ArgumentNullException("first");
        if (second == null) throw new ArgumentNullException("second");

        var merged = new Dictionary<T1, T2>();
        first.ToList().ForEach(kv => merged[kv.Key] = kv.Value);
        second.ToList().ForEach(kv => merged[kv.Key] = kv.Value);

        return merged;
    }
}

Stosowanie:

Dictionary<string, string> merged = first.Merge(second);

Uproszczony w użyciu w porównaniu z moją wcześniejszą odpowiedzią z domyślną wartością logiczną nieniszczącego scalania, jeśli istnieje lub całkowicie zastępuje, jeśli jest prawdziwy, zamiast używania wyliczenia. Nadal odpowiada moim potrzebom, nie wymagając przy tym żadnego bardziej wyszukanego kodu:

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)
    {
        source.ToList().ForEach(_ => {
            if ((!target.ContainsKey(_.Key)) || overwrite)
                target[_.Key] = _.Value;
        });
    }
}

Scalanie za pomocą EqualityComparermapowania elementów w celu porównania z inną wartością / typem. Tutaj zmapujemy KeyValuePair(typ elementu przy wyliczaniu słownika) do Key.

public class MappedEqualityComparer<T,U> : EqualityComparer<T>
{
    Func<T,U> _map;

    public MappedEqualityComparer(Func<T,U> map)
    {
        _map = map;
    }

    public override bool Equals(T x, T y)
    {
        return EqualityComparer<U>.Default.Equals(_map(x), _map(y));
    }

    public override int GetHashCode(T obj)
    {
        return _map(obj).GetHashCode();
    }
}

Stosowanie:

// if dictA and dictB are of type Dictionary<int,string>
var dict = dictA.Concat(dictB)
                .Distinct(new MappedEqualityComparer<KeyValuePair<int,string>,int>(item => item.Key))
                .ToDictionary(item => item.Key, item=> item.Value);

lub:

public static IDictionary<TKey, TValue> Merge<TKey, TValue>( IDictionary<TKey, TValue> x, IDictionary<TKey, TValue> y)
    {
        return x
            .Except(x.Join(y, z => z.Key, z => z.Key, (a, b) => a))
            .Concat(y)
            .ToDictionary(z => z.Key, z => z.Value);
    }

wynikiem jest związek, w którym dla zduplikowanych wpisów wygrywa „y”.

public static IDictionary<K, V> AddRange<K, V>(this IDictionary<K, V> one, IDictionary<K, V> two)
        {
            foreach (var kvp in two)
            {
                if (one.ContainsKey(kvp.Key))
                    one[kvp.Key] = two[kvp.Key];
                else
                    one.Add(kvp.Key, kvp.Value);
            }
            return one;
        }

Wersja z odpowiedzi @ user166390 z dodanym IEqualityComparerparametrem umożliwiającym porównanie kluczy bez rozróżniania wielkości liter.

    public static T MergeLeft<T, K, V>(this T me, params Dictionary<K, V>[] others)
        where T : Dictionary<K, V>, new()
    {
        return me.MergeLeft(me.Comparer, others);
    }

    public static T MergeLeft<T, K, V>(this T me, IEqualityComparer<K> comparer, params Dictionary<K, V>[] others)
        where T : Dictionary<K, V>, new()
    {
        T newMap = Activator.CreateInstance(typeof(T), new object[] { comparer }) as T;

        foreach (Dictionary<K, V> src in 
            (new List<Dictionary<K, V>> { me }).Concat(others))
        {
            // ^-- echk. Not quite there type-system.
            foreach (KeyValuePair<K, V> p in src)
            {
                newMap[p.Key] = p.Value;
            }
        }
        return newMap;
    }

fromDic.ToList().ForEach(x =>
        {
            if (toDic.ContainsKey(x.Key))
                toDic.Remove(x.Key);
            toDic.Add(x);
        });