Разница между Lookup () и словарём (Of list ())

165

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

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

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

Джон Бустос
источник
1
можно также захотеть посмотреть, что такое телепередача «ключ к поиску»
nawfal

Ответы:

255

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

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

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

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

Джон Скит
источник
Если поиск несуществующего ключа приводит к пустой последовательности, а не к исключению, то он очень не может быть использован в качестве общей коллекции imo. Это нормально в случае неизменной коллекции, которая является побочным продуктом запросов linq.
nawfal
@nawfal - это именно то, для чего нужны поиски. Из msdn : «Вы можете создать экземпляр Lookup <TKey, TElement>, вызвав ToLookup для объекта, который реализует IEnumerable <T>.»
Найл Коннотон
50

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

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

Младен Михайлович
источник
51
Проверьте вопрос: речь идет о разнице между Lookup <TKey, TValue> и словарем <TKey, List <TValue >>, так что эта разница уже видна явно.
Мартао
5
@Martao Некоторые люди находят этот вопрос, когда ищут его, чтобы понять разницу между поисками и словарями. Этот ответ действительно полезен.
jakubiszon
34

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

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

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

Джеймс Майкл Хэйр
источник
11

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

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

Servy
источник
1
@JohnBustos С точки зрения производительности, нет. Это чисто логично. Вы можете передавать ссылки на структуру вокруг, чтобы не беспокоиться о том, что кто-то еще изменит ее из-под вас. Вы можете сделать предположение о том, что неизменным является то, чего нельзя было бы сделать, если бы оно было изменчивым.
Serv
Спасибо, Servy, это очень хороший момент, когда вы часто передаете столько переменных ByRef - по крайней мере, эту, которую вы точно не можете изменить. Спасибо!
Джон Бустос
2
@JohnBustos Имейте в виду, что по умолчанию метод передачи параметра метода по значению, вам нужно явно добавить byref, и это следует делать довольно редко. Эти структуры данных являются классами, что делает их ссылочными типами, поэтому передача значения является значением ссылки, поэтому передача его другому методу может вызвать видимые изменения в вызывающей стороне.
Serv
Спасибо, Серви, это открывает для меня совершенно новую банку глистов с точки зрения того, что я делаю :), но я понимаю, что ты говоришь. Спасибо!!
Джон Бустос
Под крышками вы знаете, использует ли Lookup ключи для ключей?
Папараццо
10

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

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

Noble_Bright_Life
источник
4

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

Если вы пытаетесь получить структуру, столь же эффективную, как, 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приходится вести список элементов для каждого ключа, он медленнее словаря (примерно в 3 раза медленнее для огромного количества элементов)

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

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

потрясающий
источник