排序算法正确性验证

Question

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

的键

我能想到至少两种简单的方法来测试正确性：

在 A 排序之前将 A 复制到 A_copy，在 A_copy 上使用 std::sort，并在之后检查 A[i] == A_copy[i] for 0 <= i < n排序。
排序前维护一个std::unordered_map存放key在A出现的频率，排序后除了非降序校验外还要用频率验证

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

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

谢谢。

Answer 1

您可以将您的算法视为通过不可靠通道传输的消息，并利用错误 detection/correction methods。主要不同是您的数据不按原始顺序排列，而大多数纠错对位置敏感，但不是全部。

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

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
}

该文献包含更多选项，可用于识别甚至纠正您可以使用的电线错误。这些将允许您在使用的额外内存量和能够发现的错误数量之间做出很好的权衡。

排序算法正确性验证

Sorting algorithm correctness verification

c++

sorting

hash

correctness

bigdata