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) 

   where T : IComparable<T>

{

    if (left == right) { return values[left]; }

    // could select pivot deterministically through median of 3 or something

    var pivotIndex = rand.Next(left, right + 1);

    pivotIndex = Partition(values, left, right, pivotIndex);

    if (index == pivotIndex) {

        return values[index];

    } else if (index < pivotIndex) {

        return SelectK(values, left, pivotIndex - 1, index);

    } else {

        return SelectK(values, pivotIndex + 1, right, index);

    }

}

static int Partition<T>(T[] values, int left, int right, int pivot) 

    where T : IComparable<T>

{

    var pivotValue = values[pivot];

    Swap(values, pivot, right);

    var storeIndex = left;

    for (var i = left; i < right; i++) {

        if (values[i].CompareTo(pivotValue) < 0)

        {

            Swap(values, storeIndex, i);

            storeIndex++;

        }

    }

    Swap(values, right, storeIndex);

    return storeIndex;

}

我运行的测试的非代表性子样本给出了输出：

i:  6724, OrderBy:      52365, value 6723

i:  6724, SelectK:      40014, value 6724

i:   395, OrderBy:      14436, value 394

i:   395, SelectK:      26106, value 395

i:  7933, OrderBy:      32523, value 7932

i:  7933, SelectK:      17712, value 7933

i:  6730, OrderBy:      46076, value 6729

i:  6730, SelectK:      34367, value 6730

i:  6536, OrderBy:      53458, value 6535

i:  6536, SelectK:      18341, value 6536

由于我的 SelectK 实现使用随机枢轴元素，因此它的输出有相当多的变化（例如参见第二次运行）。它也比标准库中实现的高度优化的排序算法差得多。

即使那样，也有 SelectK 直接优于标准库的情况，即使我没有付出太多努力。

现在用中位数 3 [1]替换随机主元（这是一个非常糟糕的主元选择器），我们可以获得稍微不同的 SelectK 并与 OrderBy 和 SelectK 竞争。

我一直在用数组中的 1m 个元素与这三匹马赛跑，使用你已经拥有的随机排序，在数组的最后 20% 中请求一个索引，并得到如下结果：

Winning counts: OrderBy 32, SelectK 32, MedianOf3 35

Winning counts: OrderBy 26, SelectK 35, MedianOf3 38 

Winning counts: OrderBy 25, SelectK 41, MedianOf3 33

即使对于 100k 元素并且不将索引限制在数组的末尾，这种模式似乎仍然存在，尽管没有那么明显：

--- 100k elements

Winning counts: OrderBy 24, SelectK 34, MedianOf3 41

Winning counts: OrderBy 33, SelectK 33, MedianOf3 33

Winning counts: OrderBy 32, SelectK 38, MedianOf3 29

--- 1m elements

Winning counts: OrderBy 27, SelectK 32, MedianOf3 40

Winning counts: OrderBy 32, SelectK 38, MedianOf3 29

Winning counts: OrderBy 35, SelectK 31, MedianOf3 33

一般来说，草率实施的 quickselect 在平均情况下有三分之二的时间优于您的建议......我想说这是一个非常强大的指标，如果您想了解细节，这是更好的算法。

当然，您的实现更容易理解 :)

[1] - 取自这个 SO answer的实现，每个递归深度步骤进行 3 次比较