Является ли словарь <TKey, TValue> быстрее LINQ в списке <T>?

Обычно я использую List<T> для коллекций. Но если мне нужен быстрый поиск в коллекции, то, например, в следующем примере я бы использовал словарь, чтобы быстро найти его id:

Dictionary<int, Customer>

Но так как я могу использовать LINQ для запроса List<T> в любом случае, как показано ниже, есть ли какая-либо причина, чтобы решить проблему использования словаря вместо списка? Является ли словарь быстрее или LINQ делает что-то за кулисами, что делает его столь же быстрым?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Customer> customers = new List<Customer>()
            {
             new Customer { Id = 234, FirstName = "Jim", LastName = "Smith" },
             new Customer { Id = 345, FirstName = "John", LastName = "Thomas" },
             new Customer { Id = 654, FirstName = "Rick", LastName = "Ashton" },
             new Customer { Id = 948, FirstName = "Rod", LastName = "Anders" }
            };

            var customer = (from c in customers
                           where c.Id == 654 select c).SingleOrDefault();
            Console.WriteLine(customer.Display());

            Console.ReadLine();

        }
    }


    public class Customer
    {
        public int Id { get; set; }
        public string FirstName { get; set; }
        public string LastName { get; set; }

        internal string Display()
        {
            return String.Format("{0}, {1} ({2})", LastName, FirstName, Id);
        }

    }
}

Ответы

Ответ 1

Если вы логически хотите создать коллекцию, где вы можете легко найти клиента по своему ID, я бы использовал некоторую форму IDictionary<int, Customer>. Это выражает то, чего вы пытаетесь достичь.

Теперь вы можете использовать список, чтобы сделать то же самое, и, как говорит leppie, для небольших наборов данных это будет примерно так же быстро или даже быстрее, но для небольших наборов данных это будет очень быстро, так почему вам все равно? Я думаю, что более важно рассказать читателю вашего кода, что вы пытаетесь сделать с коллекцией, - и словарь достигает этой цели гораздо эффективнее, чем список, IMO.

Ответ 2

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

Ответ 3

Согласно MSDN получение элемента из словаря на основе ключа "подходит к операции O (1)". С другой стороны, выполнение Where в списке проходит через элементы для поиска совпадений. Таким образом, обычно словарь будет определенно быстрее.

Если вы хотите ускорить операции Linq, вы можете использовать Indexed LINQ, который позволяет помещать индексы в ваши коллекции.

Ответ 4

Для списков, содержащих менее 20 элементов, служебные данные Dictionary/Hashtable приведут к тому, что он будет медленнее, чем список.

Ответ 5

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

Ответ 6

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