воскресенье, 23 марта 2014 г.

Как удалить элементы из списка.

Представьте себе, что у нас есть список, содержащий какие-то элементы, а нам нужно в какой-то момент удалить часть из них. Какие варианты есть? Самый очевидный для многих вариант - с использованием foreach работать не будет:

            foreach (var item in list)
            {
                if (item % 2 == 0)
                { list.Remove(item); }
            }


Не будет он работать вот почему. foreach компилятором разворачивается в примерно такую конструкцию:
            
            List< t >.Enumerator enumerator = list.GetEnumerator();
            try
            {
               while (enumerator.MoveNext())
               {
                 ....
               }
            }
            finally
            {
               enumerator.Dispose();
            }

А если мы используем что-то типа Resharper и посмотрим на метод MoveNext(), то увидим, что он сравнивает версию коллекции, и если она изменилась, то выбрасывает исключение.
            
            [__DynamicallyInvokable]
            public bool MoveNext()
            {
                List< t > list = this.list;
                if ((this.version == list._version) && (this.index < list._size))
                {
                    this.current = list._items[this.index];
                    this.index++;
                    return true;
                }
                return this.MoveNextRare();
            }

            private bool MoveNextRare()
            {
                if (this.version != this.list._version)
                {
                    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
                }
                this.index = this.list._size + 1;
                this.current = default(T);
                return false;
            }


Давайте попробуем дрогой вариант - цикл for.

Как думаете, вот этот код отработает правильно?
            
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] % 2 == 0)
                { list.Remove(list[i]); }
            }

Именно этот отработает правильно, но так как это не более, чем случайность, то может привести ко многим ошибка в дальнейшем. Попробуем немного изменить условие и все сразу ломается.
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] < 5)
                { list.Remove(list[i]); }
            }
Происходит так потому, что при удалении элемента, индексы всех последующих уменьшаются на единицу. И если в первом случае нам просто везло, что при каждой следующей итерации попадался элемент кратный двум, то тут подобный сдвиг все ломает. Что бы цикл for работал правильно вне зависимости от условий нужно проходить список с конца. Тогда удаление элемента не приведет к катастрофическим последствиям, так как все, что после текущего элемента уже пройдено.

            for (int i = list.Count - 1; i >= 0; i--)
            {
                if (list[i] < 5)
                { list.Remove(list[i]); }
            }

Ну а самый удобный, хотя и не самый быстрый вариант - это использование LINQ, а точнее метода RemoveAll.

            list.RemoveAll(x => x < 5);

Вот результаты замеров скорости на моей машине:
For :           00:00:00.0000278
RemoveAll :     00:00:00.0002202

Почему в 10 раз медленнее? Потому, что если воспользуетесь тем же решарпером, то увидите, что во-первых весть список проходится два раза, а во-вторых, при каждой итерации вызывается предекат match. Так что, выбирайте какой вариант ваш, быстрый или удобный ;)

[__DynamicallyInvokable]
public int RemoveAll(Predicate< t > match)
{
    if (match == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }
    int index = 0;
    while ((index < this._size) && !match(this._items[index]))
    {
        index++;
    }
    if (index >= this._size)
    {
        return 0;
    }
    int num2 = index + 1;
    while (num2 < this._size)
    {
        while ((num2 < this._size) && match(this._items[num2]))
        {
            num2++;
        }
        if (num2 < this._size)
        {
            this._items[index++] = this._items[num2++];
        }
    }
    Array.Clear(this._items, index, this._size - index);
    int num3 = this._size - index;
    this._size = index;
    this._version++;
    return num3;
}


Комментариев нет:

Отправить комментарий