问题标签 [partial-sort]

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

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

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

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

我知道有numpy.percentile(myArray,5)，但我知道在幕后这将首先对数组进行完整排序，如果我只需要排序最小的 5% 的值，这是低效的。我还读到堆排序方法对这个部分排序问题很有用，但我似乎找不到适用于 2D numpy 数组的实现。

这是我尝试过的：

这在我的系统上大约需要 15 毫秒（对于我的实时应用程序来说太慢了）。

尝试堆：

在我的系统上花费 300 毫秒；我希望 heapq 可以加快速度！

我读了那个博客，其中一个 C# 程序员展示了如何使用 LINQ 从 3 个不同的数组中提取 5 个最高数字。

我尝试用 C++ 做同样的事情并编写了以下代码，使用向量和排序只有 5 行代码。输出88 89 110 888 921符合预期。

但问题是，你有更好的解决方案吗？

任何有关如何解决以下问题的帮助将不胜感激。我也发布了一些关于这个问题的想法。

你是一个有 n 名学生的班级的助教。您有他们的最终分数（未排序），您必须为他们分配 G 可用等级之一（A、B、C 等）。约束是（假设 n 是 G 的倍数）：

• 恰好 (n/G) 名学生获得每个成绩（例如，如果 n = 30，并且 G = {A,B,C}，则正好 10 名学生获得 A，10 名学生获得 B，10 名学生获得 C）
• 分数较低的学生不会比分数较高的学生获得更高的分数（但是，他们可能会得到相同的分数）假设每个学生获得不同的分数，推导出一个有效的算法并给出其复杂度G. 任何首先对分数进行排序的算法都将获得零分。

我的回答：好的，问题的最后一行说，如果我尝试先对数组进行排序并将数组分成 G 等份，我就不好了。当使用最佳排序算法时，这将花费 O(n log n)。所以，我想到了一个复杂的解决方案。我认为这个问题是快速排序可以派上用场的一个例子，因为我们不需要对属于同一年级的学生进行排序，我们可以有 k 个关键元素，并且关键元素都是等距的。但是，我们没有得到学生的分数，我们也被告知每个学生都有不同的分数。

首先，我使用 MaxMin Divide and Conquer Algorithm 计算最大和最小分数，这将花费 O(n) 时间。使用最大值和最小值，我们可以通过计算粗略地找到每个等级的关键要素。(Max-Min)/k = 最低等级，2*(Max-Min)/k = 第二最低等级。k-1*(Max-Min)/k = 最高等级。

现在使用这些作为关键元素，我们可以只执行快速排序的分区方法，第一次需要 n 时间，第二次需要 n-(Max-Min)/k 等等。因此算法的时间复杂度为 O(n)，因为 min-max 问题的复杂度为 O(n)，而快速排序中的 Partition 的复杂度为 O(n)。

请分享你的想法。

任务是对具有重复 st 的向量进行部分排序，如果向量已排序，则中值（第 n 个元素）位于它的位置。所有较小的元素都应该在左边，所有较大的元素都应该在右边。与中值相同的所有元素都必须按原始顺序排列 - 但只有这些元素不是其余元素。

你会如何解决这个问题？

我最初的解决方案：

1. 使用 std::nth_element() 查找中值元素
2. 遍历向量并仅对与其索引具有相同值的元素进行排序。我将如何有效地做到这一点？

有两个数组，一个用于 ids，一个用于分数，我想将这两个数组存储到 a std::map，并使用std::partial_sort找到五个最高分数，然后打印它们的 id 那么，有没有可能使用std::partial_sorton std::map？

以下两种方法之间是否存在显着差异？方式 1 使用sort或partial_sort，具体取决于向量的大小，而方式 2 始终使用partial_sort。我发现方式 2 更有吸引力，因为我的谓词比示例中的要复杂一些，所以我不想重复它。但我想知道partial_sort性能是否比sort因为它不打算用于对整个范围进行排序，这就是我倾向于使用方式 1 的原因。

一些测试表明，如果必须对整个范围进行排序，partial_sort 比 sort 差得多（在我的用例中是 4 倍）。这表明方式 1 是首选。似乎 partial_sort 仅用于对整个范围的一小部分进行排序。我在 Visual Studio 2010 中进行了测试。

是否可以使用插入排序原则仅对k数组中的第一个元素进行排序？

因为当算法在数组上运行时，它会相应地排序。

由于需要检查所有元素（找出谁是最小的），它最终会对整个事物进行排序。

例子：

原始数组：{5, 3, 8, 1, 6, 2, 8, 3, 10}

预期输出k = 3：{1, 2, 3, 5, 8, 6, 8, 3, 10}（仅对前 k 个元素进行了排序，其余元素未排序）

我需要从Vec生产中相当大的 a 中获取前 N 个项目。目前我这样做是这样低效的：

在 C++ 中，我会使用，但在Rust 文档std::partial_sort中找不到等效项。

我只是忽略了它，还是它不存在（还）？

“列表”是指英文单词，不是必需的链表。您可以使用任何数据结构。但是，PHP 内置了对某些数据结构的支持：https ://www.php.net/manual/en/spl.datastructures.php从中最小堆似乎适合我的问题。虽然我不知道如何使用 PHP 的最小堆设施。

假设一个循环正在从数据库中读取并输出一些用户 ID，并且每个用户 ID 都会对用户名与输入单词的相似程度进行比较。循环结束后，我想按分数降序查看前 10 名用户。分数计算在循环内完成。

对我来说最简单的方法是：在计算分数时（在循环内），将所有用户 ID 及其分数存储在一个数组中。存储所有分数后，使用 PHP 的内置排序工具对数组进行排序。显示数组中的前 10 个元素。
但是，当我只想要 10 个顶级用户时，为什么还要麻烦（系统）存储和排序所有分数。那么，有什么好的方法吗？

我想象的另一个可能的解决方案是，请随意忽略：

维护一个按降序排列的分数链表。达到长度10后，接收到一个新的score时，检查它是否小于最右边节点（第10个节点）的score，如果是则丢弃它，如果不是则丢弃最右边的节点并插入新的通过检查它是否小于链表的第 5 个（中间）元素，在适当的位置得分，如果它与第 7 个（第 5 和第 9 的中间）相同，依此类推。

PS：我对前 k 个元素在全部被选中后进行排序没有问题。