LINQ 中的 OrderBy 和 Take

Question

我在 Youtube 上看了一些程序员采访的视频。其中一个问题是编写一个返回数组中第 n 个最小元素的函数。

在视频中，我看到一位女士尝试用 C++ 编写一些重复代码，但我认为很好，在 C# 中它是一个衬里：

var nth = vals.OrderBy(x => x).Take(i).Last();

然后我意识到我不知道这实际上是否是一个好的解决方案，因为下一个问题是关于时间复杂度的。我去了文档，我发现的是返回的对象OrderBy具有在枚举时执行完整延迟排序所需的所有信息。

所以我决定对其进行测试，并MyComparable : IComparable<MyComparable>在 CompareTo 方法中编写了一个具有单值和静态计数器的类：

 class MyComparable : IComparable<MyComparable>

    {

        public MyComparable(int val)

        {

            Val = val;

        }

        public static int CompareCount { get; set; }

        public int Val { get; set; }

        public int CompareTo(MyComparable other)

        {

            ++CompareCount;

            if (ReferenceEquals(this, other)) return 0;

            if (ReferenceEquals(null, other)) return 1;

            return Val.CompareTo(other.Val);

        }

    }

然后我写了一个循环来查找数组中的第 n 个元素：

 static void Main(string[] args)

        {

            var rand = new Random();

            var vals = Enumerable.Range(0, 10000)

//                .Reverse() // pesimistic scenario

//                .OrderBy(x => rand.Next()) // average scenario

                .Select(x => new MyComparable(x))

                .ToArray();

            for (int i = 1; i < 100; i++)

            {

                var nth = vals.OrderBy(x => x).Take(i).Last();

                Console.WriteLine($"i: {i,5}, OrderBy: {MyComparable.CompareCount,10}, value {nth.Val}");

                MyComparable.CompareCount = 0;

                var my_nth = vals.OrderByInsertion().Take(i).Last();

                Console.WriteLine($"i: {i,5}, Insert : {MyComparable.CompareCount,10}, value {my_nth.Val}");

                MyComparable.CompareCount = 0;

                my_nth = vals.OrderByInsertionWithIndex().Take(i).Last();

                Console.WriteLine($"i: {i,5}, Index  : {MyComparable.CompareCount,10}, value {my_nth.Val}");

                MyComparable.CompareCount = 0;

                Console.WriteLine();

                Console.WriteLine();

            }

        }

Answer 1

好吧，让我们从唾手可得的果实开始：您的实施是错误的。您需要index + 1从序列中获取元素。要理解这一点，请考虑index = 0并重新阅读Take.您的“基准比较”之所以有效，是因为调用OrderBy()IEnumerable 不会修改基础集合。对于我们要做的事情，只允许修改底层数组会更容易。因此，我冒昧地更改您的代码以在每次迭代中从头开始生成值。另外Take(i + 1).Last()相当于ElementAt(i). 你真的应该使用它。哦，你的基准真的没有用，因为你需要消耗的范围内的元素Take越多，这些算法就越接近彼此。据我所知，您对 O(n log n) 的运行时分析是正确的。有一个解决方案的时间复杂度为 O(n)（不是我之前错误声明的 O(log n)）。这是面试官期待的解决方案。不管它值多少钱，您在那里编写的代码都不能移动到该解决方案，因为您对排序过程没有任何控制权。如果你有，你可以实施Quickselect，（这是这里的目标），从而在理论上改进你在这里提出的 LINQ 查询（特别是对于高索引）。以下是基于您的代码对 quickselect 维基百科文章中的伪代码的翻译static T SelectK<T>(T[] values, int left, int right, int index)&nbsp;&nbsp; &nbsp;where T : IComparable<T>{&nbsp; &nbsp; if (left == right) { return values[left]; }&nbsp; &nbsp; // could select pivot deterministically through median of 3 or something&nbsp; &nbsp; var pivotIndex = rand.Next(left, right + 1);&nbsp; &nbsp; pivotIndex = Partition(values, left, right, pivotIndex);&nbsp; &nbsp; if (index == pivotIndex) {&nbsp; &nbsp; &nbsp; &nbsp; return values[index];&nbsp; &nbsp; } else if (index < pivotIndex) {&nbsp; &nbsp; &nbsp; &nbsp; return SelectK(values, left, pivotIndex - 1, index);&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; return SelectK(values, pivotIndex + 1, right, index);&nbsp; &nbsp; }}static int Partition<T>(T[] values, int left, int right, int pivot)&nbsp;&nbsp; &nbsp; where T : IComparable<T>{&nbsp; &nbsp; var pivotValue = values[pivot];&nbsp; &nbsp; Swap(values, pivot, right);&nbsp; &nbsp; var storeIndex = left;&nbsp; &nbsp; for (var i = left; i < right; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if (values[i].CompareTo(pivotValue) < 0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Swap(values, storeIndex, i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; storeIndex++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; Swap(values, right, storeIndex);&nbsp; &nbsp; return storeIndex;}我运行的测试的非代表性子样本给出了输出：i:&nbsp; 6724, OrderBy:&nbsp; &nbsp; &nbsp; 52365, value 6723i:&nbsp; 6724, SelectK:&nbsp; &nbsp; &nbsp; 40014, value 6724i:&nbsp; &nbsp;395, OrderBy:&nbsp; &nbsp; &nbsp; 14436, value 394i:&nbsp; &nbsp;395, SelectK:&nbsp; &nbsp; &nbsp; 26106, value 395i:&nbsp; 7933, OrderBy:&nbsp; &nbsp; &nbsp; 32523, value 7932i:&nbsp; 7933, SelectK:&nbsp; &nbsp; &nbsp; 17712, value 7933i:&nbsp; 6730, OrderBy:&nbsp; &nbsp; &nbsp; 46076, value 6729i:&nbsp; 6730, SelectK:&nbsp; &nbsp; &nbsp; 34367, value 6730i:&nbsp; 6536, OrderBy:&nbsp; &nbsp; &nbsp; 53458, value 6535i:&nbsp; 6536, SelectK:&nbsp; &nbsp; &nbsp; 18341, value 6536由于我的 SelectK 实现使用随机枢轴元素，因此它的输出有相当多的变化（例如参见第二次运行）。它也比标准库中实现的高度优化的排序算法差得多。即使那样，也有 SelectK 直接优于标准库的情况，即使我没有付出太多努力。现在用中位数 3 [1]替换随机主元（这是一个非常糟糕的主元选择器），我们可以获得稍微不同的 SelectK 并与 OrderBy 和 SelectK 竞争。我一直在用数组中的 1m 个元素与这三匹马赛跑，使用你已经拥有的随机排序，在数组的最后 20% 中请求一个索引，并得到如下结果：Winning counts: OrderBy 32, SelectK 32, MedianOf3 35Winning counts: OrderBy 26, SelectK 35, MedianOf3 38&nbsp;Winning counts: OrderBy 25, SelectK 41, MedianOf3 33即使对于 100k 元素并且不将索引限制在数组的末尾，这种模式似乎仍然存在，尽管没有那么明显：--- 100k elementsWinning counts: OrderBy 24, SelectK 34, MedianOf3 41Winning counts: OrderBy 33, SelectK 33, MedianOf3 33Winning counts: OrderBy 32, SelectK 38, MedianOf3 29--- 1m elementsWinning counts: OrderBy 27, SelectK 32, MedianOf3 40Winning counts: OrderBy 32, SelectK 38, MedianOf3 29Winning counts: OrderBy 35, SelectK 31, MedianOf3 33一般来说，草率实施的 quickselect 在平均情况下有三分之二的时间优于您的建议......我想说这是一个非常强大的指标，如果您想了解细节，这是更好的算法。当然，您的实现更容易理解 :)[1] - 取自这个 SO answer的实现，每个递归深度步骤进行 3 次比较