是否有C#等同于C ++ std :: partial_sort? [英] Is there a C# equivalent to C++ std::partial_sort?

问题描述

我正在尝试为可通过许多标准排序的数据集实现分页算法.不幸的是，尽管其中一些标准可以在数据库级别上实现，但某些标准必须在应用程序级别上完成(我们必须与另一个数据源集成).我们有分页(实际上是无限滚动)的要求，并且正在寻找一种方法来最大程度地减少每次分页调用时在应用程序级别对整个数据集进行排序的麻烦.

I'm trying to implement a paging algorithm for a dataset sortable via many criteria. Unfortunately, while some of those criteria can be implemented at the database level, some must be done at the app level (we have to integrate with another data source). We have a paging (actually infinite scroll) requirement and are looking for a way to minimize the pain of sorting the entire dataset at the app level with every paging call.

仅对绝对需要排序的部分列表进行排序的最佳方法是什么? .NET库中是否有等效于C ++的 std::partial_sort 函数?我应该如何解决这个问题?

What is the best way to do a partial sort, only sorting the part of the list that absolutely needs to be sorted? Is there an equivalent to C++'s std::partial_sort function available in the .NET libraries? How should I go about solving this problem?

这是我要做什么的一个示例:

Here's an example of what I'm going for:

比方说，我需要根据一些排序标准来获取1000个元素集中的元素21-40.为了加快排序速度，并且无论如何我每次都必须遍历整个数据集(这是基于HTTP的Web服务，它是无状态的)，因此我不需要对整个数据集进行排序.我只需要正确订购元素21-40.创建3个分区就足够了:元素1-20，未排序(但全部少于元素21)；元素21-40，已排序；和元素41-1000，未排序(但均大于元素40).

Let's say I need to get elements 21-40 of a 1000 element set, according to some sorting criteria. In order to speed up the sort, and since I have to go through the whole dataset every time anyway (this is a web service over HTTP, which is stateless), I don't need the whole dataset ordered. I only need elements 21-40 to be correctly ordered. It is sufficient to create 3 partitions: Elements 1-20, unsorted (but all less than element 21); elements 21-40, sorted; and elements 41-1000, unsorted (but all greater than element 40).

推荐答案

确定.这是根据您对我的评论所说的内容我会尝试的方法.

OK. Here's what I would try based on what you said in reply to my comment.

我希望能够说第4至第6"，并得到类似的信息:3， 2，1(未排序，但都少于适当的第4个元素)； 4，5，6(已排序 并在同一位置显示排序列表)； 8、7、9 (未排序，但都大于适当的第6个元素).

I want to be able to say "4th through 6th" and get something like: 3, 2, 1 (unsorted, but all less than proper 4th element); 4, 5, 6 (sorted and in the same place they would be for a sorted list); 8, 7, 9 (unsorted, but all greater than proper 6th element).

让我们在列表中添加10可以更容易:10、9、8、7、6、5、4、3、2、1.

Lets add 10 to our list to make it easier: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.

因此，您可以使用快速选择算法来查找i ^th 和k ^th 元素.在上面的例子中，i是4，k是6.这当然会返回值4和6.这将需要两次遍历您的列表.因此，到目前为止，运行时间为O(2n)= O(n).当然，下一部分很简单.我们在关注的数据上有上限和下限.我们需要做的就是再次遍历列表，查找位于上下限之间的任何元素.如果找到这样的元素，则将其放入新的列表中.最后，然后对我们的List排序，该List仅包含我们关心的第i ^th 到第k ^th 个元素.

So, what you could do is use the quick select algorithm to find the the i^th and k^th elements. In your case above i is 4 and k is 6. That will of course return the values 4 and 6. That's going to take two passes through your list. So, so far the runtime is O(2n) = O(n). The next part is easy, of course. We have lower and upper bounds on the data we care about. All we need to do is make another pass through our list looking for any element that is between our upper and lower bounds. If we find such an element we throw it into a new List. Finally, we then sort our List which contains only the i^th through k^th elements that we care about.

所以，我相信总运行时间最终为O(N)+ O((k-i)lg(k-i))

So, I believe the total runtime ends up being O(N) + O((k-i)lg(k-i))

static void Main(string[] args) {
    //create an array of 10 million items that are randomly ordered
    var list = Enumerable.Range(1, 10000000).OrderBy(x => Guid.NewGuid()).ToList();

    var sw = Stopwatch.StartNew();
    var slowOrder = list.OrderBy(x => x).Skip(10).Take(10).ToList();
    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);
    //Took ~8 seconds on my machine

    sw.Restart();
    var smallVal = Quickselect(list, 11);
    var largeVal = Quickselect(list, 20);
    var elements = list.Where(el => el >= smallVal && el <= largeVal).OrderBy(el => el);
    Console.WriteLine(sw.ElapsedMilliseconds);
    //Took ~1 second on my machine
}

public static T Quickselect<T>(IList<T> list , int k) where T : IComparable {
    Random rand = new Random();
    int r = rand.Next(0, list.Count);
    T pivot = list[r];
    List<T> smaller = new List<T>();
    List<T> larger = new List<T>();
    foreach (T element in list) {
        var comparison = element.CompareTo(pivot);
        if (comparison == -1) {
            smaller.Add(element);
        }
        else if (comparison == 1) {
            larger.Add(element);
        }
    }

    if (k <= smaller.Count) {
        return Quickselect(smaller, k);
    }
    else if (k > list.Count - larger.Count) {
        return Quickselect(larger, k - (list.Count - larger.Count));
    }
    else {
        return pivot;
    }
}

这篇关于是否有C#等同于C ++ std :: partial_sort?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！