Блог

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

Решение первое: используйте set equality.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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