Почему IOrderedEnumerable не реализует заново.Contains() для повышения производительности

Question

Если вы идете сюда: IOrderedEnumerable Docs и нажимаете на метод.Contains(), то он приведет вас сюда: обобщенные документы Enumerable.Contains()

Я так понимаю, это означает, что он просто использует базовую реализацию IEnumerable?

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

Я что-то пропустил?

Answer 1

С самого начала стоит отметить, что тот факт, что данный метод задокументирован как работающий на IEnumerable<T> не означает, что он не оптимизирован для заданных реализаций или производных интерфейсов. На самом деле очень много методов в Enumerable выбрать разные пути для разных производных интерфейсов и / или конкретных реализаций. Классическим примером здесь является то, что Count() принимает другой путь, если IEnumerable<T> он вызывается на орудиях ICollection<T> или же ICollection, Есть несколько дополнительных примеров этого в полной структуре, и даже больше в.NET Core, включая некоторые, которые используют оптимизированные пути для реализации IOrderedEnumerable<T> ты получаешь от звонка OrderBy(),

Некоторые из них - мои хобби, потому что мое хобби в настоящее время - содействие.NET Core, в частности Linq, и, в частности, повышение производительности (хотя, очевидно, если я что-то взламываю, мне нужно увеличить тесты на части, к которым я прикасаюсь, и при этом выявляются незначительные ошибки, они получают приоритет над улучшениями производительности).

Когда дело доходит до IOrderedEnumerableЯ сделал такие вещи, как изменения .OrderBy(someLambda).Skip(j).Take(k) (общая пейджинговая идиома) от O(n log n) времени для вычисления и O(j + k) времени для перечисления до O(n + k log k) времени для вычисления и O(k) времени для перечисления, и .OrderBy(someLambda).First() для O(n) пространства и O(n log n) времени до O(1) пространства и O(n) времени и так далее.

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

Если бы я сделал, я бы не сделал это, как вы предлагаете.

Во-первых, иметь отдельную перегрузку для IOrderedEnumerable<T> потребует добавления метода к общедоступному API, но охватит только некоторые случаи (возможно, то, что нам дано как IEnumerable<T> на самом деле IOrderedEnumerable<T>). Намного лучше иметь перегрузку для IEnumerable<T> и обнаружить IOrderedEnumerable<T> дело.

Во-вторых, чтобы использовать бинарный поиск, мы должны знать, каким образом IOrderedEnumerable был отсортирован. Это возможно с OrderedEnumerable<TElement, TKey> созданный вызовами OrderBy но не в более общем смысле.

В-третьих, это не будет наибольшим возможным выигрышем.

Текущие расходы source.OrderBy(someLambda).Contains(someItem) являются следующими:

1. буфер source: O(n) пространство, O(n) время.
2. Сортировка буфера: O(n log n) время (среднее, O(n²) хуже).
3. Найдите предмет, который соответствует someItemили подтвердите, что ничего не существует. O(n) время.

Если Contains() был оптимизирован для использования бинарного поиска, он стал бы:

1. буфер source: O(n) пространство, O(n) время.
2. Сортировка буфера: O(n log n) время (среднее, O(n²) хуже).
3. Найдите предмет, который соответствует someItemили подтвердите, что ничего не существует.: O(log n) время (среднее, O(n) хуже, потому что точное совпадение может сортироваться на том же уровне, что и все элементы, и должно сравниваться со всеми из них).

Тем не менее, это полная трата. Если мы хотим оптимизировать Contains() (и очень много других совокупных методов в этом отношении) оптимальным вариантом будет:

1. Вызов source.Contains(someItem) и вернуть результат. В худшем случае это будет O(n) время и O(1) пространство, хотя это может быть O(log n) или O(1) время, если source это, например, HashSet<T> (случай, когда Contains() уже оптимизирован для). Как в теории, так и на практике это закончится быстрее, чем приведенный выше шаг буферизации.

Внедрение этого изменения будет значительно меньше работы и гораздо больше выгоды.

Я обдумал это и мог бы действительно представить такой PR, но я еще не уверен, стоит ли в итоге того стоить (и, следовательно, каково мое мнение, если кто-то другой подаст такой PR), поскольку это почти всегда легче для звонящий, чтобы включить ….OrderBy(foo).Contains(bar) в .Contains(bar) сами по себе, и проверка, необходимая для оптимизации в таком случае, будет дешевой, но не полностью бесплатной.

Answer 2

Чтобы использовать бинарный поиск, вам нужна какая-то сортированная структура данных. Возможно отсортированный массив или SortedList. Но вы только что получили IOrderedEnumerable только реализация; запрос еще не осуществлен.

Ваш IOrderedEnumerable может быть просто создан с использованием блоков Iterator или некоторых ленивых запросов (как обычно это генерируется). Там нет реальной структуры данных. Вы не можете получить все элементы из IOrderedEnumerable или же IEnumerable не перечисляя их, что O(n).

Таким образом, вы не сможете реализовать бинарный поиск или что-то подобное.

Answer 3

Итак, основываясь на ответе @Sriram, но конкретизирую конкретную проблему:

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

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