Значение настройки производительности C # для каждого элемента списка

Question

Я пытаюсь найти быстрый способ установить определенное свойство каждого элемента в общем списке.

По сути, требуется перебирать список элементов и сбрасывать свойство IsHit в FALSE. Только элементы из второго списка попаданий должны быть установлены в TRUE.

Моя первая попытка выглядела так:

listItems.ForEach(delegate(Item i) { i.IsHit = false; });

foreach (int hitIndex in hits)
{
    listItems[hitIndex - 1].IsHit = true;
}

Примечание: попадания основаны на 1, список предметов основан на 0.

Затем я попытался улучшить скорость и придумал следующее:

for (int i = 0; i < listItems.Count; i++)
{
    bool hit = false;
    for (int j = 0; j < hits.Count; j++)
    {
        if (i == hits[j] - 1)
        {
            hit = true;
            hits.RemoveAt(j);
            break;
        }
    }

    if (hit)
    {
        this.listItems[i].IsHit = true;
    }
    else
    {
        this.listItems[i].IsHit = false;
    }
}

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

К сожалению, я не вижу способа улучшить код дальше. Но я, наверное, что-то упустил.

Спасибо

PS: код в C # / .NET 2.0 предпочтительнее.

---

В итоге я перешел на решение Eamon Nerbonne. Но потом я заметил что-то странное в моих тестах.

Делегат:

listItems.ForEach(delegate(Item i) { i.IsHit = false; });

быстрее чем:

foreach (Item i in listItems)
{
    i.IsHit = false;
}

Как это возможно?

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

Answer 1

Можете ли вы поместить элементы вашего второго списка в словарь? Если это так, вы можете сделать это:

for( int i = 0; i < firstList.Count; i++ )
{
   firstList[i].IsHit = false;

   if( secondList.Contains (firstList[i].Id) )
   {
       secondList.Remove (firstList[i].Id);
       firstList[i].IsHit = true;
   }
}

Где secondList - вне словаря.

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

Answer 2

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

Самое быстрое решение, вероятно, будет следующим:

foreach(var item in listItems)
    item.IsHit = false;
foreach (int hitIndex in hits)
    listItems[hitIndex - 1].IsHit = true;

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

Только если IsHit действительно медленный , следующее будет быстрее:

bool[] isHit = new bool[listItems.Count]; //default:false.
//BitArray isHit = new BitArray(listItems.Count);  
//BitArray is potentially faster for very large lists.
foreach (int hitIndex in hits)
    isHit [hitIndex - 1] = true;
for(int i=0; i < listItems.Count; i++)
    listItems[i].IsHit = isHit[i];

Наконец, рассмотрите возможность использования массива, а не List<>. Как правило, массивы работают быстрее, если вам не нужны методы вставки / удаления типа List<>.

Ключевое слово var - это C # 3.5, но его можно использовать в .NET 2.0 (в целом для новых языковых функций не требуются более новые версии библиотек, просто они наиболее полезны для этих новых библиотек). Конечно, вы знаете тип, для которого List<> специализирован, и можете явно указать его.

Answer 3

Вы можете отсортировать коллекцию обращений и выполнить бинарный поиск, тогда вы будете O (n log ₂ n) вместо O (n ² )