排序算法正确性验证

Question

我正在尝试验证一个排序算法的正确性。S 对一个大数组进行排序 A 的至少4GB。假设 S 按非递减顺序排序，只检查 A[i - 1] <= A[i] for 1 <= i < n 是不够的。这是因为由 S即使经过排序，也可能会包含一个或多个不属于原 A.

我可以想到至少有两种琐碎的方法来测试正确性。

1. 复制一份... A 到 A_copy 之前 A 是排序的，使用 std::sort 关于 A_copy，并检查 A[i] == A_copy[i] for 0 <= i < n 排序后。
2. 保持一个 std::unordered_map 来存储键的频率，以 A 排序前，除了进行非递减顺序检查外，还要与排序后的频率进行验证。

上述方法存在明显的问题。std::sort 对于大数据来说是非常慢的，而且需要 O(n) 额外的内存。使用地图应该更快，但也需要额外的 O(n) 内存，如果键是唯一的。

我的问题是：有没有更好的方法来执行这种正确性检查，既快速又使用了 O(1) 额外的内存？

谢谢。

Answer 1

你可以把你的算法当作一个在不可靠信道上传输的消息，并利用误差 检测校正方法. 主要不同的是，你的数据是得到了原来的顺序，而大多数纠错是敏感的位置，虽然不是所有的位置。

一个简单的解决方法是存储XOR值的 hash(a) 对于所有 a 在 A虽然它只能可靠地检测到是否添加了一个元素（例如，如果一个元素添加了两次，它将无法识别它）。

int verification = 0;
for (const auto& a : A) {
  verification ^= hash(a)
}
mySort(A);
for (const auto& a : A) {
  verification ^= hash(a)
}

if (verification != 0) {
  // invalid
} else {
  // valid
}

文献中包含了更多你可以利用的识别甚至纠正错误的线的选项。这些将使你在你使用的额外内存量和你能够发现的错误数量之间有一个很好的权衡。