4

我想找出两个相等长度的字符串有多少个不同的字符。我发现异或算法被认为是最快的，但它们返回以位表示的距离。我想要用字符表示的结果。假设“pet”和“pit”以字符表示的距离为 1，但 'e' 和 'i' 可能有两个不同的位，因此 xoring 返回 2。

我写的函数是：

// na = length of both strings
unsigned int HammingDistance(const char* a, unsigned int na, const char* b) {

    unsigned int num_mismatches = 0;
    while (na) {
        if (*a != *b)
            ++num_mismatches;

        --na;
        ++a;
        ++b;
    }

    return num_mismatches;
}

它可以变得更快吗？也许使用一些较低级别的命令或实现不同的算法？

系统：英特尔至强 X5650 上的 Gcc 4.7.2

谢谢

4

4 回答 4

1

循环展开怎么样：

while (na >= 8){
  num_mismatches += (a[0] != b[0]);
  num_mismatches += (a[1] != b[1]);
  num_mismatches += (a[2] != b[2]);
  num_mismatches += (a[3] != b[3]);
  num_mismatches += (a[4] != b[4]);
  num_mismatches += (a[5] != b[5]);
  num_mismatches += (a[6] != b[6]);
  num_mismatches += (a[7] != b[7]);
  a += 8; b += 8; na -= 8;
}
if (na >= 4){
  num_mismatches += (a[0] != b[0]);
  num_mismatches += (a[1] != b[1]);
  num_mismatches += (a[2] != b[2]);
  num_mismatches += (a[3] != b[3]);
  a += 4; b += 4; na -= 4;
}
if (na >= 2){
  num_mismatches += (a[0] != b[0]);
  num_mismatches += (a[1] != b[1]);
  a += 2; b += 2; na -= 2;
}
if (na >= 1){
  num_mismatches += (a[0] != b[0]);
  a += 1; b += 1; na -= 1;
}

此外，如果您知道有很长一段相等的字符，您可以一次将指针转换为long*并比较它们 4 个，并且只有在不相等时才查看各个字符。此代码基于memset并且memcpy速度很快。它将字符串复制到long数组中以 1) 消除对齐问题，以及 2) 用零填充字符串到整数longs。当它比较每对longs 时，如果它们不相等，它会将指针转换为char*并计算不相等的字符。与上述类似，主循环也可以展开。

long la[BIG_ENOUGH];
long lb[BIG_ENOUGH];
memset(la, 0, sizeof(la));
memset(lb, 0, sizeof(lb));
memcpy(la, a, na);
memcpy(lb, b, nb);
int nla = (na + 3) & ~3; // assuming sizeof(long) = 4
long *pa = la, *pb = lb;
while(nla >= 1){
  if (pa[0] != pb[0]){
    num_mismatches += (((char*)pa[0])[0] != ((char*)pb[0])[0])
                    + (((char*)pa[0])[1] != ((char*)pb[0])[1])
                    + (((char*)pa[0])[2] != ((char*)pb[0])[2])
                    + (((char*)pa[0])[3] != ((char*)pb[0])[3])
                    ;
  }
  pa += 1;pb += 1; nla -= 1;
}
于 2013-04-13T13:54:35.673 回答
1

如果字符串用零填充以始终为 32 字节并且它们的地址是 16 对齐的，您可以执行以下操作：（代码既未测试也未分析）

movdqa xmm0, [a]
movdqa xmm1, [a + 16]
pcmpeqb xmm0, [b]
pcmpeqb xmm1, [b + 16]
pxor xmm2, xmm2
psadbw xmm0, xmm2
psadbw xmm1, xmm2
pextrw ax, xmm0, 0
pextrw dx, xmm1, 0
add ax, dx
movsx eax, ax
neg eax

但是如果字符串通常很小，它会做很多不必要的工作，并且可能不会更快。不过，如果字符串通常（接近）32 个字节，它应该会更快。

编辑：我在看到您更新的评论之前写了这个答案 - 如果字符串通常那么小，这可能不是很好。一个 16 字节的版本可能（也许）有用（有条件地运行第二次迭代，应该很好地预测它的分支，因为它很少被采用）。但是对于这么短的字符串，普通代码很难被击败。

movdqa xmm0, [a]
pxor xmm1, xmm1
pcmpeqb xmm0, [b]
psadbw xmm0, xmm1
pextrw ax, xmm0, 0
movsx eax, ax
neg eax
于 2013-04-13T15:27:35.197 回答
1

您可以通过对本机整数大小执行按位运算符来一次比较更多字节。

在您的代码中，您一次比较一个字节的相等性，但是您的 CPU 可以在一个周期内至少比较一个字，如果它是 x86-64，则可以比较 8 个字节。当然，确切的性能能力取决于 CPU 架构。

但是，如果您以 8 的步幅通过两个指针，在某些情况下肯定会更快。当它必须从主内存中读取字符串时，内存加载时间实际上将主导性能。但是如果字符串在 CPU 缓存中，您可能可以进行 XOR，并通过测试 64 位值中位更改的位置来解释结果。

可以使用从 0x33333333 而不是 0x55555555 开始的 SWAR 算法的变体来计算不为 0 的桶。

该算法将更难使用，因为它需要使用具有正确内存对齐的 uint64_t 指针。您需要涵盖剩余字节的序言和后记。也许你应该阅读编译器输出的程序集，看看它是否在你尝试更复杂的代码之前没有做一些更聪明的事情。

于 2013-04-13T12:30:14.253 回答
1

代替

if (*a != *b)
    ++num_mismatches;

这在某些架构（使用 8 位字节）上会更快，因为它避免了分支：

int bits = *a ^ *b;
bits |= bits >> 4;
bits |= bits >> 2;
bits |= bits >> 1;
num_mismatches += bits & 1;
于 2013-04-13T12:56:29.293 回答