Какой самый быстрый способ сравнить словарь C # со словарем «золотого стандарта» на равенство?

Question

У меня есть заведомо исправный словарь, и во время выполнения мне нужно создать новый словарь и выполнить проверку, чтобы увидеть, имеет ли он те же пары ключ-значение, что и заведомо исправный словарь (потенциально вставленный в разных порядках)и выберите один путь, если он делает, и другой, если это не так.Мне не обязательно нужно сериализовать весь заведомо исправный словарь (например, я мог бы использовать хэш), но мне нужны некоторые данные на диске, которые имеют достаточно информации о заведомо исправном словаре, чтобы можно было сравнить, если нетдля отдыха.Какой самый быстрый способ сделать это?Я могу использовать SortedDictionary, но количество времени, необходимое для инициализации и добавления значений, имеет значение для скорости этой задачи.

Конкретный пример:

Рассмотрим словарь <String,List<String>>, который выглядит примерно такэто (очевидно, в произвольном порядке):

{ {"key1", {"value1", "value2"} }, {"key2", {"value3", "value4"} } }  

Я создаю этот Словарь один раз и сохраняю некоторую информацию о нем на диске (полная сериализация, хэш, что угодно).Затем во время выполнения я делаю следующее:

Dictionary<String,List<String>> d1 = new Dictionary<String,List<String>> ();
Dictionary<String,List<String>> d2 = new Dictionary<String,List<String>> ();
Dictionary<String,List<String>> d3 = new Dictionary<String,List<String>> ();

String key11 = "key1";
String key12 = "key1";
String key13 = "key1";
String key21 = "key2";
String key22 = "key2";
String key23 = "key2";

List<String> value11 = new List<String> {"value1", "value2"};
List<String> value12 = new List<String> {"value1", "value2"};
List<String> value13 = new List<String> {"value1", "value2"};
List<String> value21 = new List<String> {"value3", "value4"};
List<String> value22 = new List<String> {"value3", "value4"};
List<String> value23 = new List<String> {"value3", "value5"};

dict1.add(key11, value11);
dict1.add(key21, value21);
dict2.add(key22, value22);
dict2.add(key12, value12);
dict3.add(key13, value13);
dict3.add(key23, value23);

dict1.compare(fileName); //Should return true
dict2.compare(fileName); //Should return true
dict3.compare(fileName); //Should return false

Опять же, если общее время от запуска до возврата из compare () быстрее, я могу изменить этот код, чтобы использовать SortedDictionary (или что-то еще), но я не могу гарантировать заказ, и мне нужно последовательное сравнение.Функция Compare () может загрузить сериализацию и выполнить итерацию по словарям, может сериализовать словарь в памяти и сравнить сериализацию с именем файла, или может выполнить множество других действий.

Answer 1

Решение одно: использовать заданное равенство.

Если словари имеют разные размеры, вы знаете, что они неравны.

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

В качестве альтернативы, создайте два набора хешей и возьмите их пересечение результирующее пересечение должно быть размером с исходные множества.

Это занимает O (n) время и O (n) пространство.

Как только вы узнаете, что наборы ключей равны, просмотрите все ключи по одному, извлеките значения и сравните их. Поскольку значения являются последовательностями, используйте SequenceEquals. Это занимает O (n) время и O (1) пространство.

Решение второе: сортировка ключей

Опять же, если словари имеют разный размер, вы знаете, что они неравны.

Если они имеют одинаковый размер, отсортируйте оба набора ключей и выполните для них SequenceEquals; если последовательности клавиш неравны, то словари неравны.

Это занимает O (n lg n) времени и O (n) пространства.

Если это удастся, то, снова, пройдитесь по клавишам по одному и сравните значения.

Решение третье:

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

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

Это O (n) во времени и O (1) в пространстве.

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

Answer 2

Из-за моих комментариев к принятому ответу, вот более строгая проверка.

goodDictionary.Keys.All(k=>
    {
        List<string> otherVal;
        if(!testDictionary.TryGetValue(k,out otherVal))
        {
            return false;
        }
        return goodDictionary[k].SequenceEquals(otherVal);
    })

Answer 3

Я не думаю, что здесь есть волшебная пуля;вам просто нужно выполнить поиск для каждой пары ключей:

public bool IsDictionaryAMatch(Dictionary<string, List<string>> dictionaryToCheck)
{
    foreach(var kvp in dictionaryToCheck)
    {
         // Do the Keys Match
         if(!goodDictionary.Exists(x => x.Key == kvp.Key))
             return false;

         foreach(var valueElement in kvp.Value)
         {
              // Do the Values in each list match
              if(!goodDictionary[kvp.Key].Exists(x => x == valueElement))
                  return false;
         }
    }

    return true;
}

Answer 4

Ну, в какой-то момент вам нужно сравнить, что у каждого ключа есть одно и то же значение, но перед этим вы можете сделать быстрые вещи, например, проверить, сколько ключей имеет каждый словарь, а затем проверить, совпадает ли список ключей.Они должны быть достаточно быстрыми, и в случае неудачи любого из этих тестов вы можете прервать более дорогое тестирование.

После этого вы сможете создать отдельные списки ключей и затем запустить запрос Paraells для сравненияфактические значения.

Answer 5

Если у вас уже есть сериализация, возьмите хеш (я рекомендую SHA-1) каждого сериализованного словаря и затем сравните их.