Изменение коллекции при перечислении другой

Я хочу удалить каждую монету, для которой логическое значение удаления установлено в true, и я знаю, что не могу удалить ее из той же коллекции, которую перебирает foreach. Итак, я сделал копию (временную), но она продолжает выдавать одно и то же исключение:

Коллекция была изменена; операция перечисления может не выполняться.

Что я делаю неправильно? Вот мой код:

List<Coin> temp = coins;
foreach (Coin c in coins)
{
    if (c.delete)
        temp.Remove(c);
    else
        c.somethingElse();
}
coins = temp;

person Nicolás Belazaras    schedule 25.07.2013    source источник


Ответы (3)


Здесь проще всего вызвать coins.RemoveAll(coin => coin.delete);. (гуглите List.RemoveAll). Это оставляет вам список монет со всеми «удалениями», удаленными в одном выражении, и вам не нужно беспокоиться о счетчиках, переменных цикла, временных копиях или чем-то еще. Итак, вы можете перебирать оставшиеся монеты, делая все, что хотите.

coins.RemoveAll(coin => coin.delete);
foreach (var coin in coins)
    coin.somethingElse();

Если вам нужна более быстрая реализация, которая выполняет итерацию по списку только один раз, вот что вам нужно. Не используйте решения с Remove или RemoveAt в цикле, потому что это медленные операции, поэтому их использование в цикле убьет производительность. Приведенное ниже просто переместит каждую «хорошую» монету вниз на позицию index, а затем увеличит index, так что в любое время все «хорошие» монеты будут ниже index. Наконец, вы удаляете все монеты выше index, так что у вас остаются только «хорошие» монеты. Поскольку он повторяется только один раз, он примерно в 2 раза быстрее, чем вариант RemoveAll, и намного быстрее, чем любое из решений Remove или RemoveAt в цикле.

var index = 0;
for (var i = 0; i < coins.Count; ++i)
{
    var coin = coins[i];
    if (!coin.delete)
    {
        coin.somethingElse();
        coins[index++] = coin;
    }
}
coins.RemoveRange(index, coins.Count - index);
person Dax Fohl    schedule 25.07.2013
comment
Это довольно удивительно, но эффективно ли это? Я имею в виду, разве вы не будете делать две итерации по списку? (Я не знаю, как метод RemoveAll работает внутри) - person Nicolás Belazaras; 25.07.2013
comment
Вы не можете избежать 2 итераций при использовании foreach для удаления элементов из-за ограничения модификации коллекции. Можно было бы сделать его немного более эффективным с помощью цикла for вместо foreach, но, вероятно, в большинстве случаев оно того не стоит. Удобочитаемость против преждевременной оптимизации. - person craftworkgames; 25.07.2013
comment
@Nico это будет быстрее, чем удалять каждый элемент по одному; List.Remove — относительно медленная операция, поэтому, даже если вы выполняете итерацию только один раз, вы вызываете эту медленную операцию несколько раз. Один вызов List.RemoveAll в любой день превзойдет этот показатель. Если производительность абсолютно важна, и вам не важен порядок ваших монет, вы можете использовать HashSet<Coin> вместо List<Coin>. - person Dax Fohl; 25.07.2013
comment
Я не знаю, так ли важна производительность здесь, это для моногейм-игры. По крайней мере, сейчас я буду использовать опцию «для вместо foreach». - person Nicolás Belazaras; 25.07.2013
comment
@Nico Я попробовал, и HashSet все равно оказался медленнее. HashSet быстрее определяет, содержит ли ваш набор/список определенный элемент, но медленнее для вставки и удаления, чем List. - person Dax Fohl; 25.07.2013
comment
Обычно я согласен с тем, что преждевременная оптимизация — корень всех зол. Однако отказ от сборки мусора в логике обновления XNA не является преждевременной оптимизацией. Поэтому я предлагаю принципиально не использовать лямбда-выражения и foreach в подобных ситуациях. На мой взгляд, лучше использовать обратный цикл for. - person WolfRevokCats; 03.08.2013
comment
Профиль @WolfRevokCats, прежде чем делать предположения о производительности. На моем ПК выполнение этого в обратном цикле с использованием RemoveAt с элементами 300K занимает 91129 мс, тогда как приведенное выше решение выполняется за 3 мс. RemoveAt является медленной операцией, потому что она должна сдвигать все элементы каждый раз в цикле. RemoveAll никогда не сдвигает элемент более одного раза. gist.github.com/daxfohl/6143558 - person Dax Fohl; 03.08.2013
comment
@Nico Я добавил реализацию, которая повторяет цикл только один раз. Он работает примерно в 2 раза быстрее, чем решение RemoveAll. - person Dax Fohl; 03.08.2013
comment
@DaxFohl: да, во втором фрагменте гораздо лучший подход. Поскольку ваш ответ принят, и это нормально, вы можете добавить примечание, чтобы направить людей от вашего первого фрагмента ко второму. Вы правы, что RemoveAt — медленный метод, но генерация мусора в куче (как в вашем первом ответе) в некоторых отношениях хуже, чем медленный — он недетерминированно медленный и вызовет уродливое прерывание GC, которое заморозит весь игровой процесс. . Ваше здоровье. - person WolfRevokCats; 04.08.2013
comment
@DaxFohl также обратите внимание, что я не делал никаких предположений о производительности (отказ от GC в обновлении XNA не является предположением о производительности, подлежащим профилированию). Но просто для удовольствия я прошел ваш тест на профилирование и немного изменил предположения. Проверьте это: gist.github.com/anonymous/6148807 - person WolfRevokCats; 04.08.2013
comment
@WolfRevokCats вы создаете список один раз вне цикла. Таким образом, все элементы удаляются на первой итерации, а остальные итерации ничего не делают. Если клонировать список для каждой итерации, RemoveAt все еще намного медленнее. RemoveAt работает быстрее только тогда, когда нечего удалять. - person Dax Fohl; 04.08.2013
comment
@Dax Fohl - да, это именно то, что я хочу сказать. Если реальная цель заключается в частом сканировании, но очень редком удалении, то может случиться так, что подход RemoveAt станет быстрее, поскольку он не включает копирование всего массива. Это просто зависит от фактического использования в программе. Если бы у меня был массив, который постоянно взбалтывается, я бы согласился с вашим предложением избегать RemoveAt. Опять же, это просто зависит, и на использование профилировщика (в отличие от несколько искусственных тестов) можно положиться, чтобы показать, что лучше в реальной жизненной ситуации. Ваше здоровье. - person WolfRevokCats; 04.08.2013

Что я делаю неправильно?

Причина, по которой ваш код не работает, заключается в том, что вы копируете только ссылку на переменную монет. Подобно указателю в C, ссылка представляет собой не что иное, как переменную, которая содержит адрес памяти другого типа. Таким образом, переменная temp указывает на ту же коллекцию, что и переменная монет.

Поэтому я сделал копию (временную)

Ваш код предназначен для выполнения (как вы его описываете):

List<Coin> temp = coins.ToList();
foreach (Coin c in coins)
{
    if (c.delete)
        temp.Remove(c);
    else
        c.somethingElse();
}
coins = temp;

(см. Enumerable.ToList)

Как уже упоминал Дакс, есть и другие, более короткие способы достижения того же результата. List.RemoveAll в этом случае вполне приемлемое решение. Вы также можете изучить запросы LINQ.

person craftworkgames    schedule 25.07.2013
comment
Спасибо, чувак, я этого не знал = только скопировал ссылку, но я думаю, это имеет смысл, поскольку ты можешь переопределить ее. Проголосовал бы, если бы было достаточно представителей: P - person Nicolás Belazaras; 25.07.2013
comment
Рад помочь. Эта проблема спотыкала меня несколько раз. Вы не можете переопределить операторы присваивания (=) в C# (по уважительной причине). msdn.microsoft.com/en-us/library /8edha89s(v=vs.71).aspx - person craftworkgames; 25.07.2013

Поскольку вы отметили свой вопрос тегом «xna» и «monogame», вы можете извлечь выгоду из решения, которое позволяет избежать генерации мусора (выделения памяти кучи, которые вызовут последующую взбалтывание сборщика мусора). Вот что я бы использовал, что также работает на любом языке программирования со структурой данных типа списка, даже если магия LINQ недоступна:

// Iterate the list backwards so we never skip items or accidentally
// access past the end of the list.
for (int i = coins.Count - 1; i >= 0; --i)
{
   if (coins[i].delete)
   {
      coins.RemoveAt(i);
   }
   else
   {
      coins[i].somethingElse();
   }
}

В решении @DaxFohl я считаю, что создание лямбда («coin => coin.delete») выделит мусорную память в куче. И также возможно, что перечисление будет выделяться из кучи, по крайней мере, в Mono. Я слышал слух, что каноническая реализация Microsoft .NET в Windows имеет эти перечисления, супероптимизированные по сравнению с другими. использование памяти, но я предпочитаю перестраховаться в своей игровой логике.

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

person WolfRevokCats    schedule 28.07.2013
comment
Это круто, братан; и да, это вызывается внутри метода обновления моей игры, это способ распоряжаться монетами, которые собрал мой игрок. Что вы разрабатываете? - person Nicolás Belazaras; 30.07.2013
comment
Игра, основанная на физике, для iOS, Android, Win8, WP и OS X. Поэтому для меня важно оставаться действительно простым, чтобы все хорошо работало на MS .NET, а также на Mono. Удачи с вашим проектом! - person WolfRevokCats; 03.08.2013