时间戳

首页 > 解决方案 > OrderBy 和接受 LINQ

c# - OrderBy 和接受 LINQ

问题描述

我在 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();
            }

        }

我还编写了 2 个“不同”实现来查找最小元素、返回它并将其从列表中删除：

   public static IEnumerable<T> OrderByInsertion<T>(this IEnumerable<T> input) where T : IComparable<T>
        {
            var list = input.ToList();

            while (list.Any())
            {
                var min = list.Min();
                yield return min;
                list.Remove(min);
            }
        }

        public static IEnumerable<T> OrderByInsertionWithIndex<T>(this IEnumerable<T> input) where T : IComparable<T>
        {
            var list = input.ToList();

            while (list.Any())
            {
                var minIndex = 0;


                for (int i = 1; i < list.Count; i++)
                {
                    if (list[i].CompareTo(list[minIndex]) < 0)
                    {
                        minIndex = i;
                    }
                }

                yield return list[minIndex];
                list.RemoveAt(minIndex);
            }
        }

结果真的让我吃惊：

i:     1, OrderBy:      19969, value 0
i:     1, Insert :       9999, value 0
i:     1, Index  :       9999, value 0


i:     2, OrderBy:      19969, value 1
i:     2, Insert :      19997, value 1
i:     2, Index  :      19997, value 1


i:     3, OrderBy:      19969, value 2
i:     3, Insert :      29994, value 2
i:     3, Index  :      29994, value 2


i:     4, OrderBy:      19969, value 3
i:     4, Insert :      39990, value 3
i:     4, Index  :      39990, value 3


i:     5, OrderBy:      19970, value 4
i:     5, Insert :      49985, value 4
i:     5, Index  :      49985, value 4

...

i:    71, OrderBy:      19973, value 70
i:    71, Insert :     707444, value 70
i:    71, Index  :     707444, value 70

...

i:    99, OrderBy:      19972, value 98
i:    99, Insert :     985050, value 98
i:    99, Index  :     985050, value 98

到目前为止，仅使用 LINQOrderBy().Take(n)是最有效和最快的，这是我所预料的，但永远不会猜到差距是几个数量级。

所以，我的问题主要是对面试官的：你如何评价这样的答案？

代码：

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

时间复杂度：

我不知道细节，但可能 OrderBy 使用某种快速排序，不n log(n)，无论我们想要哪个第 n 个元素。

你会要求我实现我自己的方法，还是使用框架就足够了？

编辑：

因此，事实证明，就像下面建议的答案一样，OrderedEnumerable使用QuickSelect的变体将元素排序到您要求的位置。从好的方面来说，它会缓存订单。

虽然您能够更快地找到第 n 个元素，但它并不是更快，而是快了一些百分比。此外，每一个 C# 程序员都会理解你的一个班轮。

我认为我在面试中的回答最终会出现在“我将使用 OrderBy，因为它足够快并且编写它需要 10 秒。如果结果很慢，我们可以使用 QucikSelect 获得一些时间，但实施它好花很多时间”

感谢所有决定参与此活动的人，并向所有浪费时间认为这是其他事情的人表示歉意:)

标签： c#sortinglinq

解决方案

好的，让我们从容易得到的结果开始：

你的实现是错误的。您需要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

一般来说，一个草率实施的快速选择在平均三分之二的时间里胜过你的建议......我会说这是一个非常强大的指标，如果你想了解细节，它是更好的算法。

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

[1] - 从这个 SO 答案中获取的实现，每个递归深度步骤产生 3 次比较

推荐阅读