前端之家

  1. 首页
  2. 问答

排序算法正确性验证

• 问答

我正在尝试验证排序算法S的正确性，该算法正在对至少4 GB的大型数组A进行排序。假设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)额外内存的排序正确性检查？

谢谢。

iCMS 回答：排序算法正确性验证

您可以将算法视为通过不可靠通道传输的消息，并利用错误detection/correction methods。主要区别在于您的数据已脱离原始顺序，而大多数纠错对位置都敏感，尽管不是全部。

一个简单的解决方案是将hash(a)中所有a的{​​{1}}的XOR值存储在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
}

文献中包含更多选项，可用来识别甚至纠正导线上的错误。这些将使您在使用的额外内存量与能够发现的错误数量之间进行很好的权衡。

bigdatac++correctnesshashsorting
本文链接：https://www.f2er.com/2172797.html

大家都在问