比较两个位图的最快方法是什么？（关于C语言实现）

Question

有两个以char数组形式存在的位图数组，包含数百万条记录。使用C语言比较它们的最快方法是什么？

我可以想象使用按位运算符在for循环中每次异或1字节。

关于位图的重要点：

1%到10%的时间，算法运行时位图可能会有所不同。大多数情况下它们将是相同的。当它们不同时，它们可以相差100%。连续串中的位可能会发生变化。

两个位图的长度相同。

目标：

检查它们是否不同，如果是，则确定它们的不同之处。

每次都正确（如果有错误，则检测错误的概率应为1）。

- user648129

---

你能分享一下你目前最好的方法吗？ - zw324

那么你进行了基准测试并得出结论，这就是瓶颈，对吧？ - user529758

我会相信 memcmp 已经针对你的处理器做了优化。 - Mark Ransom

使用处理器字长可能比使用字节更快。尝试以“int”大小的块来执行。分析应该会显示一些改进。 - luser droog

当您进行比较时，您想知道什么信息？您只需要知道它们是否相同或不同，还是需要知道它们的差异在哪里，有多少位不同等等？它们长度总是相同吗？ - Jonathan Leffler

Answer 1

这个答案假定您所说的“位图”是一个由0/1值组成的序列，而不是“位图图像格式”

如果您只是有两个长度相同的位图，并希望快速比较它们，像评论中建议的那样使用memcmp()会很有效。如果您想尝试使用SSE类型的优化，但这些不像 memcmp()那么容易。 memcmp()假设您只想知道“它们是否不同”，仅此而已。

如果您想知道它们有多少位不同，例如615个位不同，那么除了异或每个字节并计算差异的数量之外，没有其他选择。正如其他人所指出的那样，您可能想要以32/64甚至256位为一组进行比较，具体取决于您的平台。但是，如果数组有数百万个字节长，则最大的延迟（使用当前CPU）将是将主存传输到CPU的时间，无论CPU执行什么操作都不太重要（这里有很多警告）

如果您的问题更多地询问A与B的比较，但实际上您要多次执行此操作，例如A与B和C、D、E等，则可以执行以下几个操作：

• A. 存储每个数组的校验和，并首先比较校验和，如果相同，则这些数组相同的可能性很高。显然，存在这样一个风险，即校验和可以相等，但是数据可能不同，因此请确保在这种情况下的错误结果不会产生重大的副作用。而且，如果您不能承受错误的结果，请勿使用此技术。
• B. 如果数组具有结构，例如它们是图像数据，则利用特定的工具进行处理，如何超出了本答案的解释范围。
• C. 如果可以有效地压缩图像数据，则压缩每个数组并使用压缩形式进行比较。如果您使用ZIP类型的压缩，则无法直接从zip中知道有多少位差异，但是其他技术，如RLE，可以快速计算位差异（但需要大量工作来构建和获取正确和快速）
• D. 如果(a)的风险是可接受的，则可以对每个262144位的块进行校验和，并仅在校验和不同的情况下计算差异。这将大大减少主存访问并提高速度。

所有选项A..D都是为了减少主存访问，因为这是任何性能提升的关键（对于所述问题）

- rlb

---

我喜欢将图像分成块并对这些块进行校验和比较的想法。然后再比较校验和。不幸的是，这只能告诉你图像是否相等，但仍有可能具有相同校验和的图像并不相同。您需要对所有位进行第二次比较以确保它们相同。鉴于原帖作者表示图像在90％以上的时间内是相等的，这种优化实际上可能会更慢。 - Mark Ransom

@mark ransom。我已经扩展了有关此事的警告，以使其更加明确。你是正确的，如果偶尔出现错误结果不会对事情产生太大影响，那么你确实只想使用这种方法。谢谢。 - rlb

@rlb 这个需要每次都准确。已经更新了问题并提供了相关信息。谢谢。 - user648129