в linq почему последующие вызовы IEnumerable.Intersect намного быстрее - PullRequest
Новая
       3

в linq почему последующие вызовы IEnumerable.Intersect намного быстрее

4 голосов
/ 27 февраля 2012

глядя на этот вопрос C # Сходство двух массивов было отмечено, что начальный вызов linq был значительно медленнее, чем последующие вызовы.Что кешируется, что имеет такое значение?Меня интересует, когда мы можем ожидать достижения такого типа поведения (возможно, здесь просто потому, что одни и те же списки используются снова и снова). 

    static void Main(string[] args)
    {
        var a = new List<int>() { 7, 17, 21, 29, 30, 33, 40, 42, 51, 53, 60, 63, 66, 68, 70, 84, 85, 91, 101, 102, 104, 108, 109, 112, 115, 116, 118, 125, 132, 137, 139, 142, 155, 163, 164, 172, 174, 176, 179, 184, 185, 186, 187, 188, 189, 192, 197, 206, 209, 234, 240, 244, 249, 250, 252, 253, 254, 261, 263, 270, 275, 277, 290, 292, 293, 304, 308, 310, 314, 316, 319, 321, 322, 325, 326, 327, 331, 332, 333, 340, 367, 371, 374, 403, 411, 422, 427, 436, 440, 443, 444, 446, 448, 449, 450, 452, 455, 459, 467, 470, 487, 488, 489, 492, 494, 502, 503, 505, 513, 514, 522, 523, 528, 532, 534, 535, 545, 547, 548, 553, 555, 556, 565, 568, 570, 577, 581, 593, 595, 596, 598, 599, 606, 608, 613, 615, 630, 638, 648, 661, 663, 665, 669, 673, 679, 681, 685, 687, 690, 697, 702, 705, 708, 710, 716, 719, 724, 725, 727, 728, 732, 733, 739, 744, 760, 762, 775, 781, 787, 788, 790, 795, 797, 802, 806, 808, 811, 818, 821, 822, 829, 835, 845, 848, 851, 859, 864, 866, 868, 875, 881, 898, 899, 906, 909, 912, 913, 915, 916, 920, 926, 929, 930, 933, 937, 945, 946, 949, 954, 957, 960, 968, 975, 980, 985, 987, 989, 995 };
        var b = new List<int>() { 14, 20, 22, 23, 32, 36, 40, 48, 63, 65, 67, 71, 83, 87, 90, 100, 104, 109, 111, 127, 128, 137, 139, 141, 143, 148, 152, 153, 157, 158, 161, 163, 166, 187, 192, 198, 210, 211, 217, 220, 221, 232, 233, 236, 251, 252, 254, 256, 257, 272, 273, 277, 278, 283, 292, 304, 305, 307, 321, 333, 336, 341, 342, 344, 349, 355, 356, 359, 366, 373, 379, 386, 387, 392, 394, 396, 401, 409, 412, 433, 437, 441, 445, 447, 452, 465, 471, 476, 479, 483, 511, 514, 516, 521, 523, 531, 544, 548, 551, 554, 559, 562, 566, 567, 571, 572, 574, 576, 586, 592, 593, 597, 600, 602, 615, 627, 631, 636, 644, 650, 655, 657, 660, 667, 670, 680, 691, 697, 699, 703, 704, 706, 707, 716, 742, 748, 751, 754, 766, 770, 779, 785, 788, 790, 802, 803, 806, 811, 812, 815, 816, 821, 824, 828, 841, 848, 853, 863, 866, 870, 872, 875, 879, 880, 882, 883, 885, 886, 887, 888, 892, 894, 902, 905, 909, 912, 913, 914, 916, 920, 922, 925, 926, 928, 930, 935, 936, 938, 942, 945, 952, 954, 955, 957, 959, 960, 961, 963, 970, 974, 976, 979, 987 };
        var s = new System.Diagnostics.Stopwatch();
        const int cycles = 10;
        for (int i = 0; i < cycles; i++)
        {
            s.Start();
            var z= a.Intersect(b);
            s.Stop();
            Console.WriteLine("Test 1-{0}: {1} {2}", i, s.ElapsedTicks, z.Count());
            s.Reset();
            a[0]=i;//simple attempt to make sure entire result isn't cached
        }

        for (int i = 0; i < cycles; i++)
        {
            var z1 = new List<int>(a.Count);
            s.Start();
            int j = 0;
            int b1 = b[j];
            foreach (var a1 in a)
            {
                while (b1 <= a1)
                {
                    if (b1 == a1)
                        z1.Add(b[j]);
                    j++;
                    if (j >= b.Count)
                        break;
                    b1 = b[j];
                }
            }
            s.Stop();
            Console.WriteLine("Test 2-{0}: {1} {2}", i, s.ElapsedTicks, z1.Count);
            s.Reset();
            a[0]=i;//simple attempt to make sure entire result isn't cached
        }

        Console.Write("Press Enter to quit");
        Console.ReadLine();
    }
}

в соответствии с некоторыми запросами - пример вывода: 

Test 1-0: 2900 45
Test 1-1: 2 45
Test 1-2: 0 45
Test 1-3: 1 45

(обычный цикл показывает лишь небольшую разницу между последовательными прогонами)

примечание после изменений для вызова a.Intersect(b).ToArray(); вместо just a.Intersect(b);, как подсказывает @kerem, результаты становятся: 

Test 1-0: 13656 45
Test 1-1: 113 45
Test 1-2: 76 45
Test 1-3: 64 45
Test 1-4: 90 45 
...

Ответы [ 5 ]

3 голосов
/ 27 февраля 2012

Я ожидаю, что первый цикл любого цикла будет медленнее по трем причинам:

  1. Код должен быть вставлен в первый раз, но не впоследствии.
  2. Если исполняемый код достаточно мал, чтобы поместиться в кэш, он не будет удален и будет быстрее загружаться процессором.
  3. Если данные достаточно малы, чтобы поместиться в кэш, они не будут удалены и будут быстрее загружаться процессором.
2 голосов
/ 27 февраля 2012

LINQ интенсивно использует отложенное выполнение.Если вы не перечислите запрос, он не будет выполнен.

Измените 

 s.Start();
 z= a.Intersect(b);
 s.Stop();

на 

 s.Start();
 z= a.Intersect(b).**ToArray**();
 s.Stop();

и опубликуйте новые результаты производительности.

a.Intersect (b) представляет собой выражение, не зависящее от значений a и b.Значения a и b используются только тогда, когда выражение вычисляется с помощью перечисления.

1 голос
/ 27 февраля 2012

Вы перечисляете результат Intersect() только при вызове Count(); это когда вычисление пересечения действительно происходит. Часть, в которой вы синхронизируете , является созданием перечисляемого объекта, который представляет будущий расчет пересечения .

В дополнение к штрафу за джитинг, который отмечали другие, первый вызов Intersect() может быть первым использованием типа из System.Core.dll, так что вы можете посмотреть на время, необходимое для загрузки кода IL в память, а также.

1 голос
/ 27 февраля 2012

Enumerable.Intersect не выполняет кэширование. Это реализовано с использованием HashSet. Первая последовательность добавляется к HashSet. Затем вторая последовательность удаляется из HashSet. Остальные элементы в HashSet выдаются как перечисляемая последовательность элементов. Вам придется фактически перечислить HashSet, чтобы оплатить стоимость создания HashSet. Эта реализация удивительно эффективна даже для небольших коллекций.

Если вы видите разницу в производительности при последующих вызовах, это не потому, что Enumerable.Intersect выполняет какое-либо кэширование, а, вероятно, потому, что вам нужно "прогреть" свой тест.

1 голос
/ 27 февраля 2012

Система JITting. Неисчислимо.

Поместить новый список (). Пересечь (новый список ()); новая System.Diagnostics.Stopwatch (). Stop (); как ваша первая строка кода и все взаимодействия будут занимать одинаковое количество времени.

...