Разница между Lookup () и Dictionary (of list())

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

сейчас, возможно, я просто не понимаю структуры достаточно хорошо, но как это ILookup(of key, ...) отличается от Dictionary(of key, list(of ...))?

также где бы я хотел использовать ILookup и где бы это было более эффективно с точки зрения скорости программы / памяти / доступа к данным и т. д.?

6 125
c# .net vb.net linq

6 ответов:

два существенных различия:

  • Lookup незыблем. Ура :) (по крайней мере, я считаю бетон Lookup класс является неизменяемым, а ILookup интерфейс не предоставляет никаких мутирующих членов. Там может быть другие изменяемые реализации, конечно.)
  • при поиске ключа, которого нет в поиске, вы получаете пустую последовательность вместо KeyNotFoundException. (Следовательно, нет TryGetValue, AFAICR.)

они, вероятно, будут эквивалентны по эффективности-поиск вполне может использовать Dictionary<TKey, GroupingImplementation<TValue>> за кулисами, например. Выберите между ними на основе ваших требований. Лично я считаю, что поиск обычно лучше подходит, чем Dictionary<TKey, List<TValue>>, в основном из-за первых двух пунктов выше.

обратите внимание, что в качестве детали реализации, конкретная реализация IGrouping<,> который используется для реализации значений IList<TValue>, что означает, что это эффективно для использования с Count(),ElementAt() etc.

207

интересно, что никто не указал фактическую самую большую разницу (взятую непосредственно из MSDN):

Поиск напоминает словарь. Этот разница в том, что словарь отображает ключи на один значения, в то время как поиск сопоставляет ключи с коллекциями ценности.

29

и Dictionary<Key, List<Value>> и Lookup<Key, Value> логически может содержать данные, организованные подобным образом, и оба имеют тот же порядок эффективности. Главное отличие-это Lookup неизменен: у него нет Add() методы и нет открытого конструктора (и, как упоминал Джон, вы можете запросить несуществующий ключ без исключения и иметь ключ как часть группировки).

как и на что вы используете, это действительно зависит от того, как вы хотите их использовать. Если вы поддерживаете карту ключа к нескольким значения, которые постоянно изменяются, то a Dictionary<Key, List<Value>> вероятно, лучше, так как он изменчив.

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

27

основное различие между ILookup<K,V> и Dictionary<K, List<V>> является ли словарь изменяемым; вы можете добавлять или удалять ключи, а также добавлять или удалять элементы из списка, который просматривается. Ан ILookup и неизменяемые и не может быть изменен после создания.

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

10

еще одно отличие, которое еще не упомянуто, - это Lookup ()поддерживает нулевые ключи:

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

7

когда исключение не является опцией, перейдите для поиска

если вы пытаетесь получить структуру столь же эффективной, как Dictionary но вы не знаете наверняка, что нет дубликата ключа на входе,Lookup - это безопаснее.

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

и это особенно верно, если сравнить его с System.Linq.Enumerable.ToDictionary функция :

// won't throw
new[] { 1, 1 }.ToLookup(x => x); 

// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);

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

соображения производительности, словарь: явный победитель

Если вам не нужен список, и вы собираетесь управлять огромным количеством элементов, Dictionary (или даже ваша собственная индивидуальная структура) будет более эффективной:

        Stopwatch stopwatch = new Stopwatch();
        var list = new List<string>();
        for (int i = 0; i < 5000000; ++i)
        {
            list.Add(i.ToString());
        }
        stopwatch.Start();
        var lookup = list.ToLookup(x => x);
        stopwatch.Stop();
        Console.WriteLine("Creation: " + stopwatch.Elapsed);

        // ... Same but for ToDictionary
        var lookup = list.ToDictionary(x => x);
        // ...

как Lookup должен поддерживать a список элементов для каждого ключа, это медленнее, чем словарь (около 3x медленнее для огромного количества элементов)

скорость поиска : Создание: 00:00:01.5760444

скорость словарь : Создание: 00:00:00.4418833

2