为了账号安全,请及时绑定邮箱和手机立即绑定

LINQ 中的 OrderBy 和 Take

LINQ 中的 OrderBy 和 Take

C#
翻过高山走不出你 2022-11-22 15:20:55

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

            }


        }

查看完整描述

1 回答

?
精慕HU

TA贡献1590条经验 获得超6个赞

好吧,让我们从唾手可得的果实开始:


您的实施是错误的。您需要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 次比较


查看完整回答
反对 回复 2022-11-22
  • 1 回答
  • 0 关注
  • 8 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信