Плоский список кортежей с дублированием «ключи» против словаря списков C#

Question

При чтении данных отображения из конфигурации, система может потреблять один или несколько типов (не .NET Type)

, например:

• SystemAlpha потребляет TypeA

• SystemBeta потребляет TypeA

• SystemBeta потребляет TypeB

Это может быть сохранено в плоском списке типа List<Tuple<string, string>> как system, type пары, с которыми было бы легко связаться с LINQ. Запрос на то, какие типы потребляются, какие системы выполняются здесь тоже, что является плюсом. Было бы несколько записей каждой системы, если они потребляли более одного типа (т. Е. Дублирующий «ключ»). Недостатком является скорость поиска здесь O(n) (можно использовать отсортированный список для O(log(n)))

В то время как с Dictionary<string, List<string>> бы одну запись для каждой системы с перечнем потребляемых видов. O(1) поиск здесь, но с недостатком, заключающийся в том, что вы не можете легко запросить, какие системы потребляют определенный тип.

Отображения будут достаточно маленькими (вероятно), чтобы быть в порядке, имея в худшем случае O(n), и есть достаточно памяти, чтобы обойти (в отношении служебных данных словаря).

Так что я спрашиваю:

1. Какой бы самый расширяемый и многоразовые? (возможно, в конечном итоге большое сопоставление)
2. С точки зрения считывания кода, что было бы проще для кого-то позже прийти и прочитать/использовать?
3. Я переусердствую это?

(И MultiValueDictionary еще не полностью отпущена)

Answer 1

Я бы пошел с Dictionary<TKey, List<TValue>>. Это дает более четкое сообщение тому, кто читает ваш код позже.

Если вам действительно нужно по значению lookup, у вас может быть еще Dictionary<TKey, List<TValue>>, который будет содержать ссылки в противоположном направлении. Обертывание их обоих в классе, который будет держать их в синхронизации, упростит заверие, когда что-то изменит коллекцию, отразит изменения.

Если количество элементов мало вы можете пропустить вторую коллекцию и сделать линейный поиск, чтобы определить, какие системы потребляют определенный тип:

return dict.SelectMany(x => x.Value.Select(y => new { x.Key, Value = y }) 
      .Where(x => x.Value == typeToSearch) 
      .Select(x => x.Key); 

Answer 2

Во-первых, сравнение не является справедливым в том смысле, что две структуры данных не ставят те же ограничения на данных, что вы можете хранить: плоский список кортежей допускает любое количество дубликатов «ключей», в то время как в словаре нет. Это ограничение важно: читатель из вашего кода читает этот смысл от Dictionary<K,V>, но не от List<Tuple<K,V>>.

Поскольку сообщение о ваших намерениях для читателей является одной из важнейших задач, которые вы имеете в качестве дизайнера, использование Dictionary<K,V> - лучший выбор. Кроме того, преимущества, которые вы указали в своем посте, также применяются: поиск по постоянному времени станет более важным, так как ваше сопоставление растет по размеру.