Словарьбыстрее, чем LINQ в списке <T>? - PullRequest
14 голосов
/ 10 августа 2010

Я обычно использую 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);
        }

    }
}

Ответы [ 6 ]

24 голосов
/ 10 августа 2010

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

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

4 голосов
/ 10 августа 2010

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

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

4 голосов
/ 10 августа 2010

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

3 голосов
/ 10 августа 2010

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

1 голос
/ 10 августа 2010

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

0 голосов
/ 10 августа 2010

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

...