ここに移動すると: The IOrderedEnumerableDocsで .Contains() メソッドをクリックすると、ここに移動します:一般化された Enumerable.Contains() ドキュメント
これは、基礎となる IEnumerable 実装を使用しているだけという意味ですか?
要素と比較できる並べ替えられたリストがあることを知っている場合、よりパフォーマンスの高い検索の可能性があることを考えると、これは奇妙に思えます (たとえば、セット全体を列挙するのではなく、要素が存在するかどうかを確認するためにバイナリ検索を実行しますか?
何か不足していますか？
IEnumerable<T>特定のメソッドが操作としてのみ文書化されているという事実は、特定の実装または派生インターフェイスに対して最適化されていないことを意味するわけではないことに最初から注意する価値があります。実際、非常に多くのメソッドが、Enumerableさまざまな派生インターフェイスおよび/または具体的な実装に対してさまざまなパスを取ります。ここでの典型的な例は、implementsまたはで呼び出されたCount()場合、別のパスを取ることです。完全なフレームワークにはさらにいくつかの例があり、.NET Core にはさらに多くの例があり、そのうちのいくつかは、呼び出しから取得するの実装に最適化されたパスを使用します。IEnumerable<T>ICollection<T>ICollectionIOrderedEnumerable<T>OrderBy()
最近の私の趣味は .NET Core、特に Linq、そして特にパフォーマンスの向上に貢献しているため、そのうちのいくつかは私のものです (ただし、何かをハッキングしている場合は、触れているビットのテストを増やす必要があることは明らかですが、そうすることで軽微なバグが見つかった場合、パフォーマンスの改善よりも優先されます)。
に関して言えば、計算に O(n log n) 時間から O(j + k) 時間から O(n + k log k) 計算時間にIOrderedEnumerable変更(一般的なページング慣用句) などのことを行いました。.OrderBy(someLambda).Skip(j).Take(k)列挙するのに O(k) 時間、.OrderBy(someLambda).First()O(n) 空間と O(n log n) 時間から O(1) 空間と O(n) 時間、など。
私は他の方法を改善することを検討するかもしれません。
もしそうなら、私はあなたが提案するようにはしません。
まず、別のオーバーロードを にIOrderedEnumerable<T>するには、パブリック API にメソッドを追加する必要がありますが、一部のケースのみをカバーする必要があります (おそらく、 an として指定されたIEnumerable<T>ものは実際には an ですIOrderedEnumerable<T>)。オーバーロードしてケースIEnumerable<T>を検出する方がはるかに優れています。IOrderedEnumerable<T>
次に、二分探索を使用するには、IOrderedEnumerableがソートされた手段を知る必要があります。これは、OrderedEnumerable<TElement, TKey>created by の呼び出しで可能ですOrderByが、より一般的には可能ではありません。
第三に、それは可能な限り最大の利益にはなりません。
の現在のコストは次のsource.OrderBy(someLambda).Contains(someItem)とおりです。
source: O(n) 空間、O(n) 時間。someItemか、何も存在しないことを確認します。: O(n) 時間。Contains()二分探索を使用するように最適化された場合、次のようになります。
source: O(n) 空間、O(n) 時間。someItemか、存在しないことを確認します。: O(log n) 時間 (平均、O(n) より悪いのは、正確な一致がすべての要素と同じレベルでソートされる可能性があり、それらすべてと比較する必要があるためです) .しかし、それは完全な無駄です。最適化したい場合Contains()（およびそのための他の非常に多くの集計方法）、最適な戦略は次のようになります。
source.Contains(someItem)て結果を返します。sourceこれは、さらに悪いことに O(n) 時間と O(1) スペースになりますが、たとえば a HashSet<T>(Contains()既に最適化されているケース) の場合は O(log n) または O(1) 時間になる可能性があります。理論と実践の両方で、上記のバッファリング手順よりも高速になります。その変更を実装すると、作業が大幅に削減され、はるかに大きなメリットが得られます。
私はこれを検討しており、実際にそのような PR を提出するかもしれませんが、バランスを取る価値があるかどうかはまだわかりません (したがって、他の誰かがそのような PR を提出した場合の私の意見はどうなるでしょうか)。そのような場合に最適化するために必要なチェックは安価ですが、完全に無料というわけではありません….OrderBy(foo).Contains(bar)。.Contains(bar)
二分探索を使用できるようにするには、ある種のソートされたデータ構造が必要です。おそらくソートされた配列またはSortedListです。しかし、IOrderedEnumerable実装しかできていません。クエリはまだ具体化されていません。
IOrderedEnumerableIterator ブロックまたはいくつかの遅延クエリを使用して簡単に作成できます (これが通常の生成方法です) 。そこには実際のデータ構造はありません。O（n）であるそれらを列挙するIOrderedEnumerableか、列挙せずにすべての要素を取得する方法はありません。IEnumerable
したがって、二分探索などを実装する方法はありません。