Тестирование на равенство между словарями в c #

Предполагая, что для ключей и значений словаря правильно реализованы методы equals и hash, каков наиболее краткий и эффективный способ проверки на равенство двух словарей?

В этом контексте два словаря называются равными, если они содержат одинаковый набор ключей (порядок не важен), и для каждого такого ключа они согласуются по значению.

Вот несколько способов, которыми я придумал (возможно, их гораздо больше):

public bool Compare1<TKey, TValue>(
    Dictionary<TKey, TValue> dic1, 
    Dictionary<TKey,TValue> dic2)
{
    return dic1.OrderBy(x => x.Key).
        SequenceEqual(dic2.OrderBy(x => x.Key));
}

public bool Compare2<TKey, TValue>(
    Dictionary<TKey, TValue> dic1, 
    Dictionary<TKey, TValue> dic2)
{
    return (dic1.Count == dic2.Count && 
        dic1.Intersect(dic2).Count().
        Equals(dic1.Count));
}

public bool Compare3<TKey, TValue>(
    Dictionary<TKey, TValue> dic1, 
    Dictionary<TKey, TValue> dic2)
{
    return (dic1.Intersect(dic2).Count().
        Equals(dic1.Union(dic2).Count()));
}

Ответы на вопрос(9)

@ Аллен ответ:

bool equals = a.Intersect(b).Count() == a.Union(b).Count()

о массивах, но насколькоIEnumerable<T> методы используются, это может быть использовано дляDictionary<K,V> тоже.

Если два словаря содержат одинаковые ключи, но в разном порядке, следует ли их считать равными? Если нет, то словари должны сравниваться путем запуска перечислителей через оба одновременно. Это, вероятно, будет быстрее, чем перечисление в одном словаре и поиск каждого элемента в другом. Если вы заранее знаете, что равные словари будут иметь элементы в одном и том же порядке, такое двойное перечисление, вероятно, поможет вам.

 supercat29 июн. 2015 г., 17:05
... нет необходимости сравнивать их содержимое. Аналогично, если они имеют неравные размеры. Если размеры равны, и суммированные расширенные хэши равны, и можно предположить, что коллекции используют один и тот жеEqualityComparer, переберите один и проверьте, содержит ли другой все элементы.
 supercat29 июн. 2015 г., 17:04
Если вам нужно сравнение, не зависящее от порядка, пользовательский тип словаря, который включает встроенную поддержку для такой вещи, возможно, будет быстрее, чем любой из встроенных типов. В противном случае, если вы контролируете, когда элементы добавляются или удаляются из словарей, может быть полезно вычислить хэш-код каждого добавленного или удаленного элемента и продолжать работуUInt64 Всего(hash+0x123456789L)*hash, делая вычисления вunchecked контекст [когда элементы добавляются, добавьте вышеуказанное значение к итогу; после удаления вычтите его]. Если две коллекции имеют неравные итоги ...
 Machtyn29 июн. 2015 г., 16:53
Полагаю, зависит от вашего заявления. В моем конкретном случае порядок ключей не имеет значения, а порядок значений по сравнению с подобным ключом не имеет значения.

Это действительно зависит от того, что вы подразумеваете под равенством.

Этот метод будет проверять, что два словаря содержат одинаковые ключи с одинаковыми значениями (при условии, что оба словаря используют одинаковыеIEqualityComparer<TKey> реализация).

public bool CompareX<TKey, TValue>(
    Dictionary<TKey, TValue> dict1, Dictionary<TKey, TValue> dict2)
{
    if (dict1 == dict2) return true;
    if ((dict1 == null) || (dict2 == null)) return false;
    if (dict1.Count != dict2.Count) return false;

    var valueComparer = EqualityComparer<TValue>.Default;

    foreach (var kvp in dict1)
    {
        TValue value2;
        if (!dict2.TryGetValue(kvp.Key, out value2)) return false;
        if (!valueComparer.Equals(kvp.Value, value2)) return false;
    }
    return true;
}
 rony l29 сент. 2010 г., 11:13
@ LukeH: да, это так. Благодарю.
 rony l29 сент. 2010 г., 11:18
это более эффективно, чем ответ Ника? dic1.Count == dic2.Count &&! dic1.Except (dic2) .Any ();
 NG.27 сент. 2010 г., 16:20
ты не опустошаешь словарь? Во время второго вызова comparex произойдет сбой, поскольку второй параметр пуст. зачем модифицировать словарь - это не нарушает принцип простой проверки равенства?
 Ani27 сент. 2010 г., 19:18
@ LukeH: Хорошо, достаточно справедливо. Я полагаю, это зависит от того, считаете ли вы поискO(1) (лучший случай) илиO(log n) (средний случай для большинства хеш-таблиц). ИМО, поведение большинства хэшей в сочетании с ростом числа хэш-блоков обычно делает егоO(logn).
 LukeH27 сент. 2010 г., 19:06
@Ani: я действительно не вижу, как это поможет. Создание и сравнение хэшей потребует прохождения как словарей, чтения ключей и значений. Если мы сгенерируем и сравним хеш этих ключей и значений, мы получим результат с «высокой вероятностью»; если мы просто сравним их непосредственно, мы получим точный ответ. Я что-то пропускаю?
 NG.27 сент. 2010 г., 16:31
@LukeH: круто - просто хотел убедиться, что я правильно читаю.
 LukeH27 сент. 2010 г., 16:30
@SB: Очень хорошая мысль.CompareX Метод не должен действительно мутировать ни один из переданных ему словарей. Это должно было быть простым доказательством концепции, но я отредактирую, чтобы сделать его более безопасным.
 rony l30 сент. 2010 г., 14:10
@ LukeH: отлично, спасибо!
 LukeH29 сент. 2010 г., 11:47
@rony:Except Метод работает аналогично моему ответу. Производительность должна быть очень близкой, хотя я ожидаю, что мой, возможно, будет иметьнезначительный край:Except метод требует первоначального прохожденияdic2 построить отдельный набор. Вы должны были бы сравнить себя, чтобы быть уверенным, но я был бы удивлен, если есть какая-то существенная разница.
 LukeH28 сент. 2010 г., 18:28
@rony: об этом заботится первая строка метода.
 Iain Ward27 сент. 2010 г., 16:12
+1 Хорошо, мне нравится
 LukeH27 сент. 2010 г., 19:16
@Ani: Не могли бы вы дать более подробную информацию, пожалуйста? Как генерация и сравнение хешей (сгенерированных из ключей / значений) будет быстрее, чем просто сравнение самих ключей / значений? Вытащить информацию изdict2 должно быть примерно O (1), предполагая, что хэш-коды наполовину приличны.
 Ani27 сент. 2010 г., 19:07
Когда словари имеют равное число, Случай 1: Они неравны - хеш почти наверняка отклонит их равенство в линейном времени. Случай 2: они равны - ваш цикл входит в наихудший случай, когда он должен полностью перечислить dict1 (n) и тратитьnlogn в получении эквивалентного kvps из формы dict2. В этом случае быстрая линейная проверка хеша едва ли ухудшает время выполнения.
 rony l28 сент. 2010 г., 18:19
Разве .Net равно семантическому не требует, чтобы два нулевых словаря считались равными?
 Ani27 сент. 2010 г., 18:53
@LukeH: Это хороший ответ, хотя большинство ответов здесьO(n log n) с некоторым быстрым отклонением продолжается. Я хотел бы добавить хэш-проверку, которая сделает это быстро отклонить в линейном времени свысоко вероятность. Например.int hash = dict.Aggregate(0, (hash, kvp) => hash ^ kvp.Key.GetHashCode() ^ kvp.Value.GetHashCode()); Это ничего не добавляет к сложности времени.

В дополнение к ответу @Nick Jones вам необходимо реализовать gethashcode таким же образом, без учета порядка. Я хотел бы предложить что-то вроде этого:

public override int GetHashCode()
{
        int hash = 13;
        var orderedKVPList = this.DictProp.OrderBy(kvp => kvp.key)
        foreach (var kvp in orderedKVPList)
        {
                 hash = (hash * 7)  + kvp.Key.GetHashCode();
                 hash = (hash * 7)  + kvp.value.GetHashCode();
        }
        return hash;
}

Для «Вложенных словарей и списков» я объединил несколько идей, чтобы сделать это:https://gist.github.com/NullVoxPopuli/f95baaa48b4e9854dcfe (слишком много кода для размещения здесь) ~, 100 строк

В OP-вопросах говорилось, что тест на равенство должен охватывать не только сопоставление ключей, но и их значение ».В этом контексте два словаря называются равными, если они содержат одинаковый набор ключей (порядок не важен), идля каждого такого ключа они согласны с ценностью«.

Я что-то упускаю или отмеченный ответhttps://stackoverflow.com/a/3804852/916121 проверять только равенство размеров и ключей, но не их значение?

Я бы написал это рядом с ответом, но не смог бы решить, как добавить его в качестве комментария, извините.

 Ted Bigham20 июл. 2017 г., 00:17
Да, вы что-то упустили. Ответ сравнивает записи (пара ключ-значение), а не ключи.
Решение Вопроса
dic1.Count == dic2.Count && !dic1.Except(dic2).Any();
 Nick Jones27 сент. 2010 г., 16:57
Извините, сейчас добавили недостающие, чтобы не исправить. Словари эквивалентны, если они имеют одинаковый размер и нет элементов, которые находятся в первом, а не во втором.
 Dan Tao27 сент. 2010 г., 17:02
Это кажется лучше;)
 Dan Tao27 сент. 2010 г., 16:53
Это не кажется мне правильным.
 NullVoxPopuli27 мар. 2015 г., 16:43
Это не работает с вложенными данными :-(
 Jason Masters04 февр. 2019 г., 20:05
Я не мог комментировать, когда я его опубликовал, но я согласен с Singularity и Ником Джонсом, предполагая, что вы перезаписали equals и gethashcode для всех ваших объектов, этот метод работает и является тем, что я использовал. Однако, если вы собираетесь использовать это как часть метода equals вашего объекта (при условии, что у объекта есть вспомогательный словарь, который сравнивается), вы должны также реализовать метод GetHashCode (), независимый от порядка. Это пример одного:stackoverflow.com/a/51953631/8333865
 Sebastian P.R. Gingter22 мая 2013 г., 11:13
Почему это правильно? Он не соблюдает требуемое равенство ценностей. Он просто проверяет наличие всех ключей в обоих словарях.
 Konamiman12 мая 2014 г., 11:00
@ SebastianP.R.Gingter: ADictionary<TKey, TValue>> также является примеромIEnumerable<KeyValuePair<TKey, TValue>>, Итак, вы сравниваете случаиKeyValuePair<TKey, TValue>, которые равны, если и ключ, и значение равны.
 Machtyn29 июн. 2015 г., 18:24
Я полагаю, что этот ответ работает только тогда, когда в ключе и значениях словаря используются только встроенные типы или пользовательский класс, в котором IEqualityComparer настроен правильно. Хотя я бы использовалdict1.SequenceEqual(dict2), Он не будет работать, если ключ или значение является коллекцией, например List <string>. (Смотри мой ответ.)
 Mrchief16 апр. 2015 г., 20:08
Почему это принято и проголосовано? Он не делает то, что просил ОП, а именнои для каждого такого ключа они соглашаются на ценность.
 Singularity13 апр. 2017 г., 02:26
Этот ответ правильныйпри условии, что [все] словарные ключи и значения имеют свои равенства и методы хеширования реализованы правильно" - методexcept() будет выполнять установленную разницу наKeyValuePairs в словаре, и каждыйKeyValuePair будет делегироватьEquals а такжеGetHashCode методы для ключей и значений (следовательно, почему эти методы должны быть реализованы правильно). Если ключи и значения являются списками или словарями, это не будет работать должным образом, потому что эти типы просто используют равенство ссылок дляEquals а такжеGetHashCode.

Вы можете использовать linq для сравнения ключ / значение:

public bool Compare<TKey, TValue>(Dictionary<TKey, TValue> dict1, Dictionary<TKey, TValue dict2)
{
    IEqualityComparer<TValue> valueComparer = EqualityComparer<TValue>.Default;

    return  dict1.Count == dict2.Count &&
            dict1.Keys.All(key => dict2.ContainsKey(key) && valueComparer.Equals(dict1[key], dict2[key]));
}
 Michael Sandler24 июн. 2015 г., 14:59
Как насчетTValue val; return dict1.Count == dict2.Count && dict1.All(x => dict2.TryGetValue(x.Key, out val) && valueComparer.Equals(x.Value, val)); ?

Я думал, что принятый ответ будет правильным, основываясь на том, что я читал в смарт-справке для метода Except: «Создает заданное различие двух последовательностей с помощью средства сравнения по умолчанию для сравнения значений». Но я обнаружил, что это не очень хороший ответ.

Рассмотрим этот код:

Dictionary<string, List<string>> oldDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}},
     {"003C", new List<string> {"Doe", "Jane"}}};
Dictionary<string, List<string>> newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}},
     {"003C", new List<string> {"Doe", "Jane"}}};

bool equal = oldDict.Count.Equals(newDict.Count) && !oldDict.Except(newDict).Any();
Console.WriteLine(string.Format("oldDict {0} newDict", equal?"equals":"does not equal"));
equal = oldDict.SequenceEqual(newDict);
Console.WriteLine(string.Format("oldDict {0} newDict", equal ? "equals" : "does not equal"));

Console.WriteLine(string.Format("[{0}]", string.Join(", ", 
    oldDict.Except(newDict).Select(k => 
        string.Format("{0}=[{1}]", k.Key, string.Join(", ", k.Value))))));

Это приводит к следующему:

oldDict does not equal newDict
oldDict does not equal newDict
[001A=[John, Doe], 002B=[Frank, Abignale], 003C=[Doe, Jane]]

Как видите, настройки «oldDict» и «newDict» абсолютно одинаковы. И ни предлагаемое решение, ни вызов SequenceEqual не работают должным образом. Интересно, является ли это результатом того, что Except использует ленивую загрузку или способ, которым компаратор настроен для словаря. (Хотя, глядя на структуру и справочные объяснения, можно предположить.)

Вот решение, которое я придумал. Обратите внимание, что я использовал следующее правило: два словаря равны, если оба содержат одинаковые ключи и значения для каждого ключа совпадают. И ключи, и значения должны быть в одинаковом последовательном порядке. И моё решение может быть не самым эффективным, так как оно основано на повторении всего набора ключей.

private static bool DictionaryEqual(
    Dictionary<string, List<string>> oldDict, 
    Dictionary<string, List<string>> newDict)
{
    // Simple check, are the counts the same?
    if (!oldDict.Count.Equals(newDict.Count)) return false;

    // Verify the keys
    if (!oldDict.Keys.SequenceEqual(newDict.Keys)) return false;

    // Verify the values for each key
    foreach (string key in oldDict.Keys)
        if (!oldDict[key].SequenceEqual(newDict[key]))
            return false;

    return true;
}

Также посмотрите, как изменится результат, если: Порядок ключей не совпадает. (возвращает ложь)

newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"003C", new List<string> {"Doe", "Jane"}},
     {"002B", new List<string> {"Frank", "Abignale"}}};

и порядок ключей совпадает, но значение не совпадает (возвращает false)

newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}},
     {"003C", new List<string> {"Jane", "Doe"}}};

Если порядок последовательности не имеет значения, функция может быть изменена на следующую, но есть вероятность снижения производительности.

private static bool DictionaryEqual_NoSort(
    Dictionary<string, List<string>> oldDict,
    Dictionary<string, List<string>> newDict)
{
    // Simple check, are the counts the same?
    if (!oldDict.Count.Equals(newDict.Count)) return false;

    // iterate through all the keys in oldDict and
    // verify whether the key exists in the newDict
    foreach(string key in oldDict.Keys)
    {
        if (newDict.Keys.Contains(key))
        {
            // iterate through each value for the current key in oldDict and 
            // verify whether or not it exists for the current key in the newDict
            foreach(string value in oldDict[key])
                if (!newDict[key].Contains(value)) return false;
        }
        else { return false; }
    }

    return true;
}

Проверьте, выполняет ли DictionaryEqual_NoSort следующее для newDict (DictionaryEquals_NoSort возвращает true):

newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"003C", new List<string> {"Jane", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}}};     
 Machtyn29 июн. 2015 г., 18:22
Принятый ответ работает для встроенных типов.
 Machtyn29 июн. 2015 г., 18:15
Кроме того, если моя установка принятого ответа и доказательство его несостоятельности неверна, пожалуйста, не стесняйтесь исправлять меня.
 James McMahon25 мар. 2016 г., 17:31
Я удивлен, чтоList<String> не возвращаетсяEquals правильно. Я видел сбой для пользовательского класса, который не переопределяетEquals но я удивлен, увидев такое поведение со списком.
 Machtyn29 июн. 2015 г., 18:14
В моем методе DictionaryEquals я не был уверен, нужна ли мне проверка Count. SequenceEqual это уже делает?

Ваш ответ на вопрос