Оптимизация LINQ для IList

Некоторое время назад я написал метод расширения IList для перечисления части списка с использованием индексов. Во время рефакторинга я понял, что аналогичный запрос можно выполнить, вызвав Skip(toSkip).Take(amount). При тестировании я заметил, что Skip не оптимизирован для IList. Немного погуглив, я наткнулся на пост Джона Скита, обсуждение того, почему такие методы оптимизации, как Skip, опасны.

Насколько я понимаю в статье, проблема не в том, что исключение возникает в оптимизированных методах при изменении коллекции, но, как говорится в комментарии, документация msdn конфликтует сама с собой.

В IEnumerator.MoveNext():

Если в коллекцию вносятся изменения, такие как добавление, изменение или удаление элементов, перечислитель безвозвратно становится недействительным, а следующий вызов MoveNext или Reset выдает исключение InvalidOperationException.

В IEnumerator.GetEnumerator():

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

Я вижу достоинства в обоих соглашениях и немного теряюсь, стоит ли их оптимизировать. Что такое правильное решение? Я рассматривал подход IList.AssumeImmutable() в духе AsParallel(), как упоминал Крис Вандермоттен в комментариях. Какая-то реализация уже существует или это плохая идея?


.net c# optimization linq skip
person Steven Jeuris    schedule 02.05.2011    source источник
comment
Если Джон придет к выводу, что оптимизация Skip и т. д. будет ошибкой, и у него есть абзац, объясняющий, почему... тогда я расценю это как хорошее рассуждение.   -  person Marc Gravell    schedule 03.05.2011
comment
Я думаю, что неопределенная семантика более прагматична, чем семантика выдачи исключения (хотя последняя более надежна), просто потому, что последняя требует, чтобы каждый экземпляр счетчика мог проверять модификацию хост-контейнера. Фу!   -  person Rafe    schedule 03.05.2011
comment
Однако точка зрения Джона остается в силе. Ничто не мешает вам написать перечислитель ItemsInRange(Lo, Hi) без использования Skip/Take.   -  person Rafe    schedule 03.05.2011
comment
@Rafe: я написал ответ на этот счет и удалил его, потому что по симметрии ItemsInRange должен существовать и для IEnumerable, и это вызовет исключение, поэтому версия IList не может быть оптимизирована аргументом Джона.   -  person Rick Sladkey    schedule 03.05.2011
comment
@Marc: Откуда мы знаем, что Джон был прав после переосмысления, а не прав с самого начала?   -  person Gabe    schedule 03.05.2011

Ответы (2)


arrow_upward
3
arrow_downward

Я согласен с Рейфом, что поведение undefined более правильно. Только версионные коллекции могут генерировать исключения, и не все версионные коллекции являются версионными (самый большой пример — массивы). Даже версионные коллекции могут вести себя неправильно, если вы сделаете ровно 2^32 изменения между вызовами MoveNext.

Предполагая, что вы действительно заботитесь о поведении версий, решение состоит в том, чтобы получить Enumerator для IList и вызывать для него MoveNext для каждой итерации:

    public static IEnumerable<T> Skip<T>(this IList<T> source, int count)
    {
        using (var e = source.GetEnumerator())
            while (count < source.Count && e.MoveNext())
                yield return source[count++];
    }

Таким образом, вы получаете поведение O(1) за счет индексации, но вы все равно получаете все поведение создания исключений при вызове MoveNext. Обратите внимание, что мы вызываем MoveNext только для побочных эффектов исключений; мы игнорируем значения, которые он перечисляет.

person Gabe    schedule 03.05.2011
comment
Интересное решение! Это выглядит немного хакерским, но на самом деле имеет смысл. - person Steven Jeuris; 03.05.2011

arrow_upward
0
arrow_downward

Класс ReadOnlyCollection может помочь с неизменяемой коллекцией.

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

здесь находится статья от msdn, в которой содержится информация о том, какие коллекции использовать для разные цели. Я бы использовал подходящую коллекцию для задачи вместо того, чтобы пытаться оптимизировать Skip and Take.

person Charles Lambert    schedule 03.05.2011
comment
Я не понимаю, как ваш ответ относится к вопросу. - person Gabe; 03.05.2011
comment
Проблема в том, что следующая выполняемая строка кода может не быть вызовом MoveNext() Хотите пояснить? - person Steven Jeuris; 03.05.2011
comment
@Steven - не хотел публиковать этот первый абзац. Я начал отвечать, думая, что ты спрашиваешь о чем-то другом. Я обновил его, чтобы удалить этот текст. - person Charles Lambert; 03.05.2011
comment
Мне серьезно нужно перестать отвечать на вопросы прямо перед сном. - person Charles Lambert; 03.05.2011