LINQ方法的運行時復雜性（Big-O）有什么保證？我最近開始使用LINQ了，我還沒有真正看到任何LINQ方法的運行時復雜性。顯然，這里有很多因素在起作用，所以讓我們將討論局限于普通的IEnumerableLINQ-to-Objects提供者。此外，假設任何Func作為選擇器/ mutator /等傳入的是廉價的O（1）操作。它似乎很明顯，所有的單次操作（Select，Where，Count，Take/Skip，Any/All，等）將是O（n）的，因為他們只需要步行的順序一次; 雖然這甚至會受到懶惰的影響。對于更復雜的運營來說，事情變得更加模糊; 集合類運算符（Union，Distinct，Except等）使用工作GetHashCode在默認情況下（據我所知），所以它似乎是合理的假設他們使用一個哈希表內，使這些操作為O（n）為好，一般。使用的版本怎么樣IEqualityComparer？OrderBy需要排序，所以很可能我們正在看O（n log n）。如果它已經排序了怎么辦？如果我說OrderBy().ThenBy()并為兩者提供相同的密鑰怎么樣？我可以看到GroupBy（和Join）使用排序或散列。這是什么？Contains將是O（n）on a List，但是O（1）on a HashSet- LINQ檢查基礎容器以查看它是否可以加快速度？真正的問題 - 到目前為止，我一直堅信運營是高效的。但是，我可以依靠嗎？例如，STL容器清楚地指定了每個操作的復雜性。.NET庫規范中的LINQ性能是否有類似的保證？更多問題（回應評論）：沒有真正想過開銷，但我沒想到對于簡單的Linq-to-Objects有很多。CodingHorror帖子討論的是Linq-to-SQL，在那里我可以理解解析查詢并使SQL增加成本 - 對象提供者也有類似的成本嗎？如果是這樣，如果您使用聲明性或功能性語法，它會有所不同嗎？
3 回答
當年話下
TA貢獻1890條經驗 獲得超9個贊
保證非常非常少，但有一些優化：
使用索引訪問擴展方法，比如
ElementAt，Skip，Last或者LastOrDefault，將檢查底層式工具與否IList<T>，讓你得到O（1）訪問，而不是O（N）。該
Count方法檢查ICollection實現，以便該操作是O（1）而不是O（N）。Distinct，GroupByJoin我相信set-aggregation方法（Union，Intersect和Except）也使用散列，所以它們應該接近O（N）而不是O（N2）。Contains檢查ICollection實現，因此如果底層集合也是O（1），它可能是O（1），例如aHashSet<T>，但這取決于實際的數據結構，并且不能保證。散列集覆蓋了該Contains方法，這就是它們為O（1）的原因。OrderBy方法使用穩定的快速排序，因此它們是O（N log N）平均情況。
我認為這涵蓋了大多數（如果不是全部）內置擴展方法。實際保證很少; Linq本身將嘗試利用高效的數據結構，但編寫可能效率低下的代碼并不是免費的。
胡說叔叔
TA貢獻1804條經驗 獲得超8個贊
我早就知道如果枚舉是一個.Count()返回。.CountIList
但是我總是有點疲憊有關Set操作的運行時間復雜度：.Intersect()，.Except()，.Union()。
這是針對.Intersect()（評論我的）反編譯的BCL（.NET 4.0 / 4.5）實現：
private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer){
Set<TSource> set = new Set<TSource>(comparer);
foreach (TSource source in second) // O(M)
set.Add(source); // O(1)
foreach (TSource source in first) // O(N)
{
if (set.Remove(source)) // O(1)
yield return source;
}}結論：
性能是O（M + N）
當集合已經設置時，實現不會占用優勢。（它可能不一定是直截了當的，因為使用過的也需要匹配。）
IEqualityComparer<T>
為了完整起見，這里都為實現.Union()和.Except()。
擾流板警報：它們也具有O（N + M） 復雜度。
private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer){
Set<TSource> set = new Set<TSource>(comparer);
foreach (TSource source in first)
{
if (set.Add(source))
yield return source;
}
foreach (TSource source in second)
{
if (set.Add(source))
yield return source;
}}private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer){
Set<TSource> set = new Set<TSource>(comparer);
foreach (TSource source in second)
set.Add(source);
foreach (TSource source in first)
{
if (set.Add(source))
yield return source;
}}
慕的地8271018
TA貢獻1796條經驗 獲得超4個贊
所有你能真正依賴的是，Enumerable方法是針對一般情況編寫的，不會使用樸素算法?？赡苡械谌降臇|西（博客等）描述了實際使用的算法，但這些并不是官方的，也不是STL算法所保證的。
為了說明，這里是Enumerable.Count來自System.Core 的反映源代碼（由ILSpy提供）：
// System.Linq.Enumerablepublic static int Count<TSource>(this IEnumerable<TSource> source){
checked
{
if (source == null)
{
throw Error.ArgumentNull("source");
}
ICollection<TSource> collection = source as ICollection<TSource>;
if (collection != null)
{
return collection.Count;
}
ICollection collection2 = source as ICollection;
if (collection2 != null)
{
return collection2.Count;
}
int num = 0;
using (IEnumerator<TSource> enumerator = source.GetEnumerator())
{
while (enumerator.MoveNext())
{
num++;
}
}
return num;
}}正如您所看到的，它需要付出一些努力來避免簡單地枚舉每個元素的天真解決方案。
- 3 回答
- 0 關注
- 788 瀏覽
添加回答
舉報
0/150
提交
取消