4

There are two arrays of bitmaps in the form of char arrays with millions of records. What could be fastest way to compare them using C.

I can imagine to use bitwise operator xor 1 byte at a time in a for loop.

Important point about bitmaps:

  • 1% to 10% of times algorithm is run, bitmaps can differ. Most of the time they will be same. When hey can differ, they can as much as 100%. There is high probability of change of bits in continuous streak.
  • Both bitmaps are of same length.

Aim:

  • Check do they differ and if yes then where.
  • Be correct every time (probability of detecting error if there is one should be 1).
4

1 回答 1

2

这个答案假设你的意思是“位图”作为 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 都是关于减少主内存访问，因为这是任何性能提升的关键（对于所述问题）

于 2013-06-21T21:21:36.743 回答