Linq содержит: производительность в списке против массива - PullRequest
Новая
       8

Linq содержит: производительность в списке против массива

0 голосов
/ 17 мая 2018

В моей программе у меня есть массив целых чисел (int[]). Позже мне нужно добавить больше целых чисел в список. Вот почему я конвертирую массив в List<int>. Мне было интересно, к какому Enumerable я должен применить Содержит звонки, которые мне нужны.

Это небольшие списки, о которых я говорю, и только пара поисков. Преобразование в HashSet было бы слишком много накладных расходов.

Теоретически поиск определенного элемента в списке, а также в массиве имеет сложность O (n). В среднем, n / 2 элементов должны быть повторены и проверены перед тем, как найти нужный.

Мне было любопытно, действительно ли эта теория верна. Поэтому мой вопрос: для небольших наборов данных есть заметная разница в производительности между List<int>.Contains() и int[].Contains()?

1 Ответ

0 голосов
/ 17 мая 2018

Я создал тестовый метод, показывающий:

Измеримых различий между ними нет при использовании случайных данных.

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

var seedGenerator = new Random();
const int RunsPerRound = 10;
int[] itemsPerRound = { 10, 20, 30, 40, 50, 100, 1000, 2000, 3000, 4000, 5000, 10000, 20000 };
foreach (var items in itemsPerRound)
{
    var runsPerRound = RunsPerRound;
    // For very small test sets, increase number of runs
    if (items < 100)
        runsPerRound = 1000;
    int totalRoundItems = items * runsPerRound;
    long totalRoundTicksList = 0;
    long totalRoundTicksArray = 0;
    for (int i = 0; i < runsPerRound; i++)
    {
        // List
        int seed = seedGenerator.Next();
        var r = new Random(seed);
        var list = new List<int>(items);
        for (int j = 0; j < items; j++)
            list.Add(r.Next());
        var sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        for (int j = 0; j < items; j++)
            list.Contains(r.Next());
        sw.Stop();
        totalRoundTicksList += sw.ElapsedTicks;

        // Array
        r = new Random(seed);
        var array = new int[items];
        for (int j = 0; j < items; j++)
            array[j] = r.Next();
        sw.Reset();
        sw.Start();
        for (int j = 0; j < items; j++)
            list.Contains(r.Next());
        sw.Stop();
        totalRoundTicksArray += sw.ElapsedTicks;
    }

    double perItemTicksList = totalRoundTicksList / totalRoundItems;
    double perItemTicksArray = totalRoundTicksArray / totalRoundItems;
    double ticksRatio = (double)totalRoundTicksList / totalRoundTicksArray;
    Console.WriteLine($"ItemsPerRound {items}:\tList:{totalRoundTicksList}\tArray:{totalRoundTicksArray}\tRatio:{ticksRatio:0.###}\tListPerItem:{perItemTicksList}\tArrayPerItem:{perItemTicksArray}");
}

На моей машине я получаю эти результаты. Обратите внимание, что соотношение между временем для Contains на List и массивом очень близко к 1. 

ItemsPerRound 10:       List:1576       Array:1373      Ratio:1.148     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 20:       List:3640       Array:4203      Ratio:0.866     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 30:       List:7617       Array:7652      Ratio:0.995     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 40:       List:12675      Array:12565     Ratio:1.009     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 50:       List:19381      Array:19098     Ratio:1.015     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 100:      List:664        Array:616       Ratio:1.078     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 1000:     List:57581      Array:56698     Ratio:1.016     ListPerItem:5   ArrayPerItem:5
ItemsPerRound 2000:     List:239500     Array:259884    Ratio:0.922     ListPerItem:11  ArrayPerItem:12
ItemsPerRound 3000:     List:547807     Array:526768    Ratio:1.04      ListPerItem:18  ArrayPerItem:17
ItemsPerRound 4000:     List:1059016    Array:1023493   Ratio:1.035     ListPerItem:26  ArrayPerItem:25
ItemsPerRound 5000:     List:1402850    Array:1385418   Ratio:1.013     ListPerItem:28  ArrayPerItem:27
ItemsPerRound 10000:    List:5814664    Array:5888034   Ratio:0.988     ListPerItem:58  ArrayPerItem:58
ItemsPerRound 20000:    List:22417904   Array:22015204  Ratio:1.018     ListPerItem:112 ArrayPerItem:110
...