12

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

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

编辑：这是我要做什么的一个例子：

假设我需要根据一些排序标准获取 1000 个元素集中的第 21-40 个元素。为了加快排序，因为我每次都必须遍历整个数据集（这是一个通过 HTTP 的 Web 服务，它是无状态的），我不需要订购整个数据集。我只需要正确订购元素 21-40。创建 3 个分区就足够了：元素 1-20，未排序（但都小于元素 21）；元素 21-40，已排序；和元素 41-1000，未排序（但都大于元素 40）。

4

3 回答 3

5

好的。根据您在回复我的评论时所说的话，这是我将尝试的。

我希望能够说“第 4 到第 6”并得到类似：3、2、1（未排序，但都小于正确的第 4 个元素）；4, 5, 6（已排序并且在相同的位置，它们将用于排序列表）；8, 7, 9（未排序，但都大于正确的第 6 个元素）。

让我们将 10 添加到我们的列表中以使其更容易：10、9、8、7、6、5、4、3、2、1。

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

所以，我相信总运行时间最终是 O(N) + O((ki)lg(ki))

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;
    }
}
于 2013-03-13T21:19:43.167 回答
-1

您可以使用List<T>.Sort(int, int, IComparer<T>)：

inputList.Sort(startIndex, count, Comparer<T>.Default);
于 2013-03-13T20:11:44.207 回答
-2

Array.Sort()具有接受的重载index和length允许您对数组的子集进行排序的参数。对于List.

当然，你不能IEnumerable直接排序。

于 2013-03-13T20:12:57.837 回答