有两个字符数组形式的位图数组，有数百万条记录。使用 C 来比较它们的最快方法是什么？
我可以想象在 for 循环中一次使用按位运算符异或 1 个字节。
关于位图的重要一点：
- 算法运行的 1% 到 10% 次中，位图可能会有所不同。大多数时候它们都是一样的。当它们可以不同时，它们可以达到 100%。连续条纹中比特发生变化的可能性很高。
- 两个位图的长度相同。
Aim:
- 检查它们是否不同，如果是，那么在哪里。
- 每次都正确（如果有错误，检测到错误的概率应该为 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 都是关于减少主内存访问，因为这是任何性能增益的关键（对于所述问题）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
