Почему при запуске LINQ OrderBy до выбора требуется больше времени? - PullRequest
Новая
       30

Почему при запуске LINQ OrderBy до выбора требуется больше времени?

3 голосов
/ 06 июня 2019

При написании решения проблемы кодирования я обнаружил интересное поведение моих операторов LINQ.У меня было два сценария:

Первый: 

arr.Select(x => x + 5).OrderBy(x => x)

Второй: 

arr.OrderBy(x => x).Select(x => x + 5)

После небольшого тестирования с System.Diagnostics.Stopwatch я получил следующие результатыдля целочисленного массива длиной 100_000.

Для первого подхода: 

00:00:00.0000152

Для второго: 

00:00:00.0073650

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

В итоге я получил 2 идеи:
1. Второй сценарий должен преобразовать в IOrderedEnumerable, а затем вернуться к IEnumerable, в то время какпервый сценарий должен преобразовать только в IOrderedEnumerable, а не обратно.
2. В итоге получается 2 цикла.Первый для сортировки, а второй для выбора при подходе 1 выполняет все в 1 цикле.

Так что мой вопрос: почему для выбора порядка требуется больше времени, прежде чем выбрать?

Ответы [ 2 ]

3 голосов
/ 06 июня 2019

Давайте посмотрим на последовательности: 

private static void UnderTestOrderBySelect(int[] arr) {
  var query = arr.OrderBy(x => x).Select(x => x + 5); 

  foreach (var item in query)
    ;
}

private static void UnderTestSelectOrderBy(int[] arr) {
  var query = arr.Select(x => x + 5).OrderBy(x => x);  

  foreach (var item in query)
    ;
}

// See Marc Gravell's comment; let's compare Linq and inplace Array.Sort
private static void UnderTestInPlaceSort(int[] arr) {
  var tmp = arr;
  var x = new int[tmp.Length];

  for (int i = 0; i < tmp.Length; i++)
    x[i] = tmp[i] + 5;

  Array.Sort(x);
}

Чтобы выполнить тест, давайте запустим 10 раз и в среднем 6 средние результаты: 

private static string Benchmark(Action<int[]> methodUnderTest) {
  List<long> results = new List<long>();

  int n = 10;

  for (int i = 0; i < n; ++i) {
    Random random = new Random(1);

    int[] arr = Enumerable
      .Range(0, 10000000)
      .Select(x => random.Next(1000000000))
      .ToArray();

    Stopwatch sw = new Stopwatch();

    sw.Start();

    methodUnderTest(arr);

    sw.Stop();

    results.Add(sw.ElapsedMilliseconds);
  }

  var valid = results
    .OrderBy(x => x)
    .Skip(2)                  // get rid of top 2 runs
    .Take(results.Count - 4)  // get rid of bottom 2 runs
    .ToArray();

  return $"{string.Join(", ", valid)} average : {(long) (valid.Average() + 0.5)}";
}

Времязапустить и взглянуть на результаты: 

  string report = string.Join(Environment.NewLine,
    $"OrderBy + Select: {Benchmark(UnderTestOrderBySelect)}",
    $"Select + OrderBy: {Benchmark(UnderSelectOrderBy)}",
    $"Inplace Sort:     {Benchmark(UnderTestInPlaceSort)}");

  Console.WriteLine(report);

Результат: (Core i7 3,8 ГГц, .Net 4.8 IA64) 

OrderBy + Select: 4869, 4870, 4872, 4874, 4878, 4895 average : 4876
Select + OrderBy: 4763, 4763, 4793, 4802, 4827, 4849 average : 4800
Inplace Sort:     888, 889, 890, 893, 896, 904 average : 893

Не знаюt * видимая значительная разница , Select + OrderBy представляется несколько более эффективной (около 2% прироста), чем OrderBy + Select.Сортировка по месту, однако, имеет производительность намного лучше (5 раз ), чем у любого из Linq.

2 голосов
/ 06 июня 2019

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

select myColumn from myTable order by myColumn;

Таким образом, производительность должна быть одинаковой, независимо от того, заказываете ли вы сначала в Linq или выбираете первым.

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

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

...