Sort or RemoveAll сначала на IEnumerable, который нуждается в обоих?

Question

Когда IEnumerable нуждается в сортировке и удалении элементов, есть ли преимущества / недостатки выполнения этапов в определенном порядке?Мои тесты производительности показывают, что это не имеет значения.

Упрощенный (и несколько надуманный) пример того, что я имею в виду, показан ниже:

public IEnumerable<DataItem> GetDataItems(int maximum, IComparer<DataItem> sortOrder)
    {
        IEnumerable<DataItem> result = this.GetDataItems();

        result.Sort(sortOrder);
        result.RemoveAll(item => !item.Display);

        result = result.Take(maximum);  
        return result;
    }

Answer 1

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

Answer 2

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

Подумав, подумал ли вы об использовании LINQ?Эти вызовы можно заменить вызовом Where и OrderBy, оба из которых будут отложены, а затем вызову Take, как в вашем примере.Библиотеки LINQ должны найти лучший способ сделать это для вас, и если ваш размер данных увеличивается до такой степени, что обработка занимает заметное количество времени, вы можете использовать PLINQ с простым вызовом AsParallel.

Answer 3

Есть два правильных ответа, но они вас ничему не научат:

1. Это не имеет значения.
2. Вероятно, вам следует сначала сделать RemoveAll.

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

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

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

Существует также очень много смысла в том, чтобы сказать «сначала профиль».Что если профилирование показывает, что 90% времени тратится на выполнение x.Foo(), что и происходит в цикле?Проблема с Foo(), с циклом или с обоими?Очевидно, что если мы можем сделать оба более эффективными, мы должны это сделать, но как мы рассуждаем об этом, не зная того, о чем нам говорит профилировщик?

Когда что-то происходит с несколькими элементами (что верно как для RemoveAll, так и дляSort) есть пять вещей (я уверен, что я больше не думаю о них сейчас), которые будут влиять на производительность:

1. Постоянные затраты за набор (как время, так иобъем памяти).Сколько стоит сделать такие вещи, как вызов функции, которой мы передаем коллекцию, и т. Д. Это почти всегда незначительно, но там может быть скрыта какая-то неприятная высокая стоимость (часто из-за ошибки).
2. Постоянные затраты на единицу товара (как время, так и память).Сколько стоит сделать что-то, что мы делаем на некоторых или на всех предметах.Поскольку это происходит несколько раз, их улучшение может быть ощутимым выигрышем.
3. Количество предметов.Как правило, чем больше элементов, тем больше влияние на производительность.Существуют исключения (следующий пункт), но если эти исключения не применяются (и нам нужно рассмотреть следующий пункт, чтобы узнать, когда это так), то это будет важно.
4. Сложность операции.Опять же, это зависит как от сложности времени, так и от сложности памяти, но здесь есть шансы, что мы можем выбрать улучшение одного за счет другого.Я расскажу об этом подробнее ниже.
5. Количество одновременных операций.Это может быть большой разницей между «работает на моей машине» и «работает на работающей системе».Если в подходе с супер-эффективным использованием времени .5 ГБ памяти тестируется на компьютере с 2 ГБ доступной памяти, он будет работать замечательно, но когда вы переместите его на компьютер с 8 ГБ доступной памяти и несколькими одновременно работающими пользователями, это 'В 16 одновременных операциях вы попадете в узкое место, и вдруг то, что превосходит другие подходы в ваших измерениях производительности, станет горячей точкой приложения.

Еще немного поговорим о сложности.Сложность времени - это мера того, как время, затраченное на выполнение чего-либо, соотносится с количеством элементов, с которыми оно выполнено, а сложность памяти - это мера того, как используемая память соотносится с тем же количеством элементов.Получение элемента из словаря - это O (1) или константа , потому что это занимает столько же времени, сколько бы ни был словарь (не совсем верно, строго он «приближается» к O (1), но он близокдостаточно для большинства размышлений).Найти что-то в уже отсортированном списке можно O (log ₂ n) или logarithmic .Фильтрация по списку будет линейной или O (n).Сортировка чего-либо с использованием быстрой сортировки (которую использует Sort) имеет тенденцию быть linearithmic или O (n log ₂ n), но в худшем случае - по списку, который уже отсортирован -будет квадратичным O (n ² ).

Учитывая это, с набором из 8 элементов операция O (1) потребует 1k секунд, чтобы сделать что-то, где k - постоянное количество времени, O ( log ₂ n) означает 3k секунд, O (n) означает 8k , O (n log ₂ n) означает 24k и O (n ² ) означает 64k . Это наиболее часто встречающиеся, хотя есть множество других, таких как O (нм), на которые влияют два разных размера, или O (n!), Которые будут 40320k .

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

Итак. Давайте вернемся к рассматриваемым вами случаям: фильтрация с последующей сортировкой и сортировкой с последующей фильтрацией.

1. Константы для каждого набора. Поскольку мы перемещаем две операции, но по-прежнему выполняем обе, в любом случае это будет то же самое.
2. Константы для каждого предмета. Опять же, мы все равно делаем одно и то же для каждого элемента, так что никакого эффекта.
3. Количество предметов. Фильтрация уменьшает количество элементов. Поэтому чем раньше мы отфильтруем элементы, тем эффективнее будет остальная часть операции. Таким образом, RemoveAll сначала побеждает в этом отношении.
4. Сложность операции. Это либо O (n), за которым следует средний регистр-O (log ₂ n) -худший случай-O (n ² ), либо это средний регистр- O (log ₂ n) - в худшем случае - O (n ² ), за которым следует O (n). Так или иначе.
5. Количество одновременных дел. Общее давление памяти будет снято, как только мы удалим некоторые элементы (сначала небольшой выигрыш для RemoveAll).

Итак, у нас есть две причины считать RemoveAll сначала наиболее вероятным, и ни одна из них не считает его менее эффективным.

Мы не будем предполагать, что мы были на 100% уверены, что мы здесь правы. Для начала мы могли просто ошибиться в наших рассуждениях. С другой стороны, могут быть и другие факторы, которые мы отклонили как не относящиеся к делу, которые на самом деле относились к делу. Все еще верно, что мы должны профилировать перед оптимизацией, но рассуждения о вещах, о которых я упоминал выше, в первую очередь увеличат вероятность того, что мы напишем производительный код (не то же самое, что оптимизация; но вопрос выбора между варианты, когда удобочитаемость, ясность и корректность одинаковы в любом случае) и облегчает поиск вероятных путей улучшения тех вещей, которые профилирование показалось трудным.

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

В этом случае, если список освобождается от всех удалений, он все равно будет O (n), но с гораздо меньшей константой. В качестве альтернативы, если он только что переместил указатель «последнего элемента» *, он становится O (1). Нахождение указателя равно O (log ₂ n), поэтому здесь есть обе причины полагать, что фильтрация в первую очередь будет быстрее (причины указаны выше), а сортировка в первую очередь будет быстрее (что удаление можно сделать гораздо более быстрая операция, чем была раньше). В таком случае это становится возможным только путем расширения нашего профилирования. Также верно, что на производительность будет влиять тип отправляемых данных, поэтому нам нужно профилировать с реалистичными данными, а не с искусственными тестовыми данными, и мы можем даже обнаружить, что то, что было более производительным выбором, становится менее производительным выбором месяцев позже, когда набор данных используется на изменения. Здесь способность рассуждать становится еще более важной, потому что мы должны отметить возможность того, что изменения в реальном использовании могут внести эти изменения в этом отношении, и знать, что это то, что мы должны следить за жизнью проекта *. 1116 *

(* Обратите внимание, List<T> не просто перемещает указатель последнего элемента для RemoveRange, который покрывает последний элемент, но другая коллекция может.)

Answer 4

Вы бы хотели что-то вроде этого:

public IEnumerable<DataItem> GetDataItems(int maximum, IComparer<DataItem> sortOrder) 
{ 
    IEnumerable<DataItem> result = this.GetDataItems(); 
    return result
           .Where(item => item.Display)
           .OrderBy(sortOrder)
           .Take(maximum); 
} 

Answer 5

Я думаю, что метод Sort () обычно имеет сложность O (n * log (n)), а RemoveAll () - просто O (n), поэтому в общем случае лучше сначала удалить элементы.

Answer 6

Вероятно, было бы лучше сначала RemoveAll, хотя это имело бы большое значение, только если ваше сравнение сортировки было интенсивным для вычисления.