algorithm - 当已排序的超集可用时对一组数字进行排序

Question

我有一组 A = {5,4,2,8}

我有一组 B = {1,2,4,5,7,8,9} 已排序

A 被指定为 B

的子集

我想对 A 进行排序(可能使用 B(甚至使用一些合理的预处理))。一般来说，我希望能够为给定的 B 对许多这样的任意“As”(B 的所有子集)进行排序。实现这一目标的最佳时间是什么？

我想到了两个幼稚的解决方案。

独立排序 A (O(A log A))

扫描 B 并获取出现在 A (O(B)) 中的元素。

当 A 小时，第一个明显更好，当 A 几乎和 B 一样大时，第二个更好。但是，当 B 有 10^10 个元素而 A 有 10^5 个元素时，我们能比这两种方法做得更好吗？

Answer 1

顺便说一句，目前尚不清楚您的第二个解决方案如何实现 O(|B|)。当您扫描 B 时，您如何“获取出现在 A 中的元素”？听起来应该在某处有一个 log A 因素。

我能贡献的最好的是一个离线算法，它在 O(|B| + L) 中对许多 A 进行排序，其中 L 是所有 A 的长度之和。 “离线”是指您可以提前阅读所有 A。

预处理 B 并构建一个哈希表，将 B 中的值映射到它们的位置。对于您的示例，哈希表是 (1 -> 1, 2 -> 2, 4 -> 3, 5 -> 4, 7 -> 5, 8 -> 6, 9 -> 7)。

为 B 中的每个元素存储一个链表，最初为空。

扫描所有 A。如果 A_i[j] = k，则将 i 附加到 k 的链表中。我们可以使用哈希表快速找到 k 的链表(也就是 k 在 B 中的位置)。在您的示例中，假设 A 是我们从输入中读取的第一个向量，并且由于 A_1[4] = 8，我们将 1 附加到 B 中 8 的链表。

刷新 A 数组。

扫描 B 并将元素插入 A 数组。例如，如果 8 的链表包含值 1、4 和 20，则将值 8 压入第 1、第 4 和第 20 个数组。

实际上，这是一个内存 pig 。您对 10^10 64 位数字的限制已经假定 80 GB 可用 RAM。哈希表至少需要该数量的三倍。将所有 A 存储在内存和链表中也需要至少 3 L 64 位值。

我非常怀疑是否存在一种实用的在线算法，可以很好地利用 B 一次处理一个 A。即使假设您可以在 O(1) 中查找 B 中的位置(例如使用哈希表)，这会将 A 中元素的域从 64 位缩小到 34(向上取整 10^10)。所以计数排序仍然无法使用，因为最后一步需要扫描 10^10 个值的域来对一个 10^5 元素的数组进行排序。离线算法所做的基本上是通过一次对所有数组进行排序来为巨大的扫描带来返回。