C#: почему словарь намного быстрее, чем список?

Я тестирую скорость получения данных из словаря против списка.
я использовал этот код для проверки:

    internal class Program
{
    private static void Main(string[] args)
    {
        var stopwatch = new Stopwatch();
        List<Grade> grades = Grade.GetData().ToList();
        List<Student> students = Student.GetStudents().ToList();

        stopwatch.Start();
        foreach (Student student in students)
        {
            student.Grade = grades.Single(x => x.StudentId == student.Id).Value;
        }
        stopwatch.Stop();
        Console.WriteLine("Using list {0}", stopwatch.Elapsed);
        stopwatch.Reset();
        students = Student.GetStudents().ToList();
        stopwatch.Start();
        Dictionary<Guid, string> dic = Grade.GetData().ToDictionary(x => x.StudentId, x => x.Value);
        foreach (Student student in students)
        {
            student.Grade = dic[student.Id];
        }
        stopwatch.Stop();
        Console.WriteLine("Using dictionary {0}", stopwatch.Elapsed);
        Console.ReadKey();
    }
}

public class GuidHelper
{
    public static List<Guid> ListOfIds=new List<Guid>();

    static GuidHelper()
    {
        for (int i = 0; i < 10000; i++)
        {
            ListOfIds.Add(Guid.NewGuid());
        }
    }
}


public class Grade
{
    public Guid StudentId { get; set; }
    public string Value { get; set; }

    public static IEnumerable<Grade> GetData()
    {
        for (int i = 0; i < 10000; i++)
        {
            yield return new Grade
                             {
                                 StudentId = GuidHelper.ListOfIds[i], Value = "Value " + i
                             };
        }
    }
}

public class Student
{
    public Guid Id { get; set; }
    public string Name { get; set; }
    public string Grade { get; set; }

    public static IEnumerable<Student> GetStudents()
    {
        for (int i = 0; i < 10000; i++)
        {
            yield return new Student
                             {
                                 Id = GuidHelper.ListOfIds[i],
                                 Name = "Name " + i
                             };
        }
    }
}

есть список студентов и классов в памяти у них есть StudentId в общем.
Во-первых, я попытался найти класс студента, используя LINQ в списке, который занимает около 7 секунд на моей машине, а по-другому сначала я преобразовал список в словарь, а затем нашел оценки студента из словаря, используя ключ, который занимает меньше секунды .

8 55
c# .net performance

8 ответов:

при этом:

student.Grade = grades.Single(x => x.StudentId == student.Id).Value;

как написано он должен перечислить весь List пока он не найдет запись в списке, которая имеет правильный studentId (соответствует ли запись 0 лямбда? Нет... Соответствует ли запись 1 лямбде? Нет... и т. д.). Это O (n). Поскольку вы делаете это один раз для каждого студента, это O(n^2).

однако, когда вы делаете это:

student.Grade = dic[student.Id];

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

Итак, словарь быстрее, потому что вы использовали лучший алгоритм.

108

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

11

причина в том, что словарь-это поиск, а список-это перебор.

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

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

поэтому каждая итерация поиска занимает все больше и больше времени. Чем больше список, тем больше времени потребуется. Хотя словарь всегда является более или менее фиксированным временем поиска (оно также увеличивается по мере увеличения словаря, но гораздо медленнее, поэтому по сравнению с ним он почти фиксирован).

10

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

попробуйте сортировать свой список, это будет немного быстрее.

8

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

минусы этого в том, что ради производительности вам нужно много места заранее (в зависимости от реализации будь то отдельная цепочка или линейное / квадратичное зондирование вам может понадобиться по крайней мере столько, сколько вы планируете магазин, вероятно, двойной в последнем случае), и вам нужен хороший алгоритм хэширования, который однозначно отображает ваш вход ("John Smith") к соответствующему выходу, такому как позиция в массиве (hash_array[34521]).

также перечисление записей в отсортированном порядке является проблемой. Если позволите процитировать Википедию:

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

прочитать на линейного пробирования и отдельные цепочки для некоторых деталей gorier:)

5

словарь основан на хэш-таблице, которая является довольно эффективным алгоритмом для поиска вещей. В списке вы должны идти элемент за элементом, чтобы найти что-то.

Это все вопрос организации данных...

3

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

Это некоторые хорошие статьи для сравнения списка со словарем.

здесь. А это один.

2

из MSDN-Dictionary упоминает близко к O (1), но я думаю, что это зависит от типов, участвующих.

универсальный класс Dictionary(TKey,TValue) предоставляет отображение из набора ключей в набор значений. Каждое дополнение к справочнику состоит из значения и связанного с ним ключа. Извлечение значения по его ключу происходит очень быстро, близко к O(1), поскольку класс Dictionary реализован как хэш-таблица.

Примечание.: Скорость поиска зависит от качества алгоритм хэширования типа, указанного для TKey.

List(TValue) не реализует поиск хэша, поэтому он является последовательным, а производительность-O (n). Это также зависит от типов участвующих и бокс/распаковка должна быть рассмотрена.

-1