代码之家 › 专栏 › 技术社区 › Harald Coppoolse

不可枚举。如果只请求第一个元素,则按订单完成列表

linq performance

Harald Coppoolse · 技术社区 · 7 年前

如果序列已排序。你只需要得到有序序列的第一个元素。Orderby是否足够聪明,不能订购整个序列?

IEnumerable<MyClass> myItems = ...
MyClass maxItem = myItems.OrderBy(item => item.Id).FirstOrDefault();

因此,如果询问第一个元素,则只有具有最小值的项被排序为序列的第一个元素。当询问下一个元素时,将订购剩余序列中具有最小值的项目,以此类推。

附加

显然,这个问题还不清楚。让我们举个例子。

创建包含所有元素的链表
只要链表包含元素:
- 扫描链接列表的其余部分一次,以查找任何较小的元素
- 从链表中删除最小的元素
- 收益率返回最小元素

代码:

public static IEnumerable<TSource> Sort<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (keySelector == null) throw new ArgumentNullException(nameof(keySelector));

    IComparer<TKey> comparer = Comparer<TKey>.Default;

    // create a linkedList with keyValuePairs of TKey and TSource
    var keyValuePairs = source
        .Select(source => new KeyValuePair<TKey, TSource>(keySelector(source), source);
    var itemsToSort = new LinkedList<KeyValuePair<Tkey, TSource>>(keyValuePairs);

    while (itemsToSort.Any())
    {   // there are still items in the list
        // select the first element as the smallest one
        var smallest = itemsToSort.First();

        // scan the rest of the linkedList to find the smallest one
        foreach (var element in itemsToSort.Skip(1))
        {
           if (comparer.Compare(element.Key, smallest.Key) < 1)
        {   // element.Key is smaller than smallest.Key: element becomes the smallest:
            smallest = element;
        }
    }

    // remove the smallest element from the linked list and return the value:
    itemsToSort.Remove(smallestElement);
    yield return smallestElement.Value;
}

假设我有一个整数序列。

Suppose I have the following sequence of integers:

{4, 8, 3, 1, 7}

在第一次迭代中,迭代器在内部创建键/值对的链接列表,并将列表的第一个元素指定为最小元素

Linked List =  4 - 8 - 3 - 1 - 7
Smallest = 4

Linked List =  4 - 8 - 3 - 1 - 7
Smallest = 1

最小的将从链表中删除,并产生回报:

Linked List =  4 - 8 - 3 - 7
return 1

Linked List =  4 - 8 - 3 - 7
smallest = 4

再次扫描链表以找到最小的一个

Linked List =  4 - 8 - 3 - 7
smallest = 3

Linked List =  4 - 8 -  7
return 3

很容易看出,如果只要求排序列表中的第一个元素,则列表只扫描一次。每次迭代,要扫描的列表都会变小。

我理解如果你只想要第一个元素,你必须扫描列表至少一次。如果不要求第二个元素,则列表的其余部分没有排序。

4 回复 | 直到 7 年前

Jon Hanna 7 年前

在框架版本(4.0、4.5等)中,然后:

整个源被加载到缓冲区中。
生成整数映射,然后根据这些键进行排序(如果源元素是大值类型,则使用映射意味着交换操作具有更便宜的副本)。
这个 FirstOrDefault MoveNext 和 Current default(TSource) .

第一默认值 上的操作 IOrderedEnumerable 默认(TSource)
保留的值将与通过第一次排序找到的框架版本的元素相同,因此返回该值。

这意味着在框架版本中 myItems.OrderBy(item => item.Id).FirstOrDefault() O(n log n) 时间复杂度(最坏情况 O(nÂ²) )和 O(n) 空间复杂性,但在.NET核心版本中 O(n) O(1) 空间复杂性。

FirstOrDefault() 了解 OrderBy ThenBy 等等)与其他可能的源不同,并且有代码来处理它*,而在框架版本中没有。

两者都扫描整个序列(您无法知道 myItems 在你检查之前,排序规则并不是第一个),但在这一点之后,它们的机制和效率有所不同。

如果询问下一个元素,那么不仅会再次进行任何排序,而且会有将作为 我的项目 在此期间可能会有变化。

myItems.OrderBy(item => item.Id).ElementAtOrDefault(i) )然后扫描( 相对于 i O(n) 尽管常数因子大于 FirstOrDefault() 可以高达 O(n) 而不是那样(它足够聪明,可以转向 ElementAtOrDefault(0) 进入 O(n) (除非.NET Core可以将其转换为 FirstOrDefault() ).

myItems.OrderBy(item => item.Id).Take(k) 然后,框架版本将再次进行排序( O(n log n) )并且对结果的后续枚举进行了限制,以便在之后停止返回元素 k 已获得。NET核心版本将进行部分排序,而不必费心对它意识到的元素进行排序,这些元素总是在所取的部分之后,即 O(n + k log k) Take 和 Skip 进一步减少必要的排序量。

理论上,正义的排序 OrderBy(cmp) 可能会更懒惰,因为:

将元素加载到缓冲区中。
做一个排序,在进行分区时可能倾向于使用“左”分区。
yield 一旦发现元素是下一个要枚举的元素。

*严格来说,几个linq操作的结果都知道如何以针对每个操作进行优化的方式找到第一个元素,并且 FirstOrDefault()

Henk Holterman 7 年前

如果序列已排序。。。

这很好,但不是IEnumerable的属性,因此OrderBy永远无法直接“知道”这一点。

Count() 将在运行时检查其 IEnumerable<> source 实际上是指向一个列表,然后使用Count属性的快捷方式。

同样,OrderBy可以查看它是否在SortedList上调用,但没有明确的标记接口,而且这些集合使用得太少,因此不值得这么做。

.OrderBy().First() 可以想象映射到 .Min() ~~直到现在~~

Enigmativity 7 年前

不,不是。在不遍历整个列表的情况下,它如何知道列表是有序的?

这里有一个简单的测试:

void Main()
{
    Console.WriteLine(OrderedEnumerable().OrderBy(x => x).First());
}

public IEnumerable<int> OrderedEnumerable()
{
    Console.WriteLine(1);
    yield return 1;
    Console.WriteLine(2);
    yield return 2;
    Console.WriteLine(3);
    yield return 3;
}

正如预期的那样,这产生了:

-1

nvoigt 7 年前

如果你看看 reference source 并遵循 classes

因此,序列被读取一次,所有的键都被计算出来,然后根据键对索引进行排序,然后得到第一个输出。