Удаление из массива, зеркальное (странное) поведение

Question

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

Для алгоритмов курса мы должны микро-оптимизировать некоторые вещи, каждый из них выясняет, как работает удаление из массива. Назначение - это удалить что-то из массива и повторно выровнять содержимое, чтобы не было пробелов, я думаю, что это очень похоже на то, как std :: vector :: erase работает с C++.

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

Во-первых, здесь немного кода, который я использовал:

class Test { 

    Stopwatch sw; 
    Obj[] objs; 

    public Test() { 
     this.sw = new Stopwatch(); 
     this.objs = new Obj[1000000]; 

     // Fill objs 
     for (int i = 0; i < objs.Length; i++) { 
      objs[i] = new Obj(i); 
     } 
    } 

    public void test() { 

     // Time deletion 
     sw.Restart(); 
     deleteValue(400000, objs); 
     sw.Stop(); 

     // Show timings 
     Console.WriteLine(sw.Elapsed); 
    } 

    // Delete function 
    // value is the to-search-for item in the list of objects 
    private static void deleteValue(int value, Obj[] list) { 

     for (int i = 0; i < list.Length; i++) { 

      if (list[i].Value == value) { 
       for (int j = i; j < list.Length - 1; j++) { 
        list[j] = list[j + 1]; 

        //if (list[j + 1] == null) { 
        // break; 
        //} 
       } 
       list[list.Length - 1] = null; 
       break; 
      } 
     } 
    } 
} 

Я бы просто создать этот класс и вызвать метод испытания(). Я делал это в цикле 25 раз.

Мои выводы:

• Первый раунд она занимает гораздо больше времени, чем другие 24, я думаю, что это из-за кэширования, но я не уверен.
• Когда я использую значение, которое находится в начале списка, оно должно перемещать больше элементов в памяти, чем когда я использую значение в конце, хотя по-прежнему это занимает меньше времени.
• Benchtimes отличаются совсем немного.
• Когда я включаю прокомментированный, если производительность повышается (10-20%), даже если значение, которое я ищу, находится почти в конце списка (это означает, что если он отключается много раз, не будучи фактически полезным) ,

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

Edit после тестирования:

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

Когда я запускаю тест с моей функцией описано чуть выше здесь я получаю балл: 362,1

Когда я запускаю его с ответом ДОК я получаю балл: 846,4

Так что мой был быстрее, но затем я начал экспериментировать с пустым пустым массивом, и все стало странно. Для того, чтобы избавиться от неизбежного NullPointerExceptions я добавил дополнительную проверку на если (думая, что это разрушило бы немного больше производительности) как так:

if (fromItem != null && fromItem.Value != value) 
    list[to++] = fromItem; 

Это, казалось, не только работать, но и существенно повысить производительность!Теперь я получаю балл: 247,9

Странная вещь, оценки, кажется низким, чтобы быть правдой, но иногда шип, это множество я взял СРЕДНЕМ от: 94, 26, 966, 36, 632, 95, 47, 35, 109, 439

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

Answer 1

Вы используете Stopwatch ко времени вашего метода. Это вычисляет общее количество часов времени, полученного во время вызова метода, который может включать the time required for .Net to initially JIT your method, interruptions for garbage collection или замедление, вызванное загрузкой системы из других процессов. Шум из этих источников, вероятно, будет доминировать над шумом из-за недостатков кэша.

This answer дает некоторые рекомендации относительно того, как можно свести к минимуму некоторые шумы от сбора мусора или других процессов. Чтобы исключить шум JIT, вы должны вызвать свой метод один раз, не синхронизируя его, или покажите время, затраченное первым вызовом в отдельном столбце в таблице результатов, так как оно будет таким разным. Вы также можете рассмотреть using a proper profiler, который точно сообщит, сколько времени ваш код использовал, исключая «шум» от других потоков или процессов.

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

public static void RemoveFromArray(this Obj[] array, int value) 
    { 
     int to = 0; 
     for (int from = 0; from < array.Length; from++) 
     { 
      var fromItem = array[from]; 
      if (fromItem.Value != value) 
       array[to++] = fromItem; 
     } 
     for (; to < array.Length; to++) 
     { 
      array[to] = default(Obj); 
     } 
    } 

Однако, вместо того, чтобы использовать стандартный алгоритм можно экспериментировать, используя Array.RemoveAt() с вашей версией, так как (я считаю) внутренне это делает удаление в неуправляемом коде.