c++ - Char 数组上的累积按位或

Question

我有一个 7K 的 long char 数组。

char arr[] = "1110010011....." ; // length 7K 

我必须对窗口大小为 3 的数组执行累积或运算。这意味着:

arr[0] | arr[1] | arr[2] ;

arr[1] | arr[2] | arr[3] ;

最好的方法是什么我可以做到小于 O(n) 或者即使复杂度是 O(n) 我们怎样才能让它更快？

Answer 1

如果将 0-1 数组重新打包成一个位集，则可以显着加快速度。它会快大约 32 倍，但仍需要 O(N) 时间。此外，您可以在 64 位机器上使用 64 位字，然后您将获得 64 倍的改进。

但是请注意，对于大的 N 内存带宽将成为主要瓶颈，因此只能实现 8 倍的改进(因为大小减少了 8 倍)。

示例代码如下:

int main() {
    char arr[] = "01000001011111000110010000011000111";
    int n = strlen(arr);

    //preparation: convert to bitset
    uint32_t bitset[sizeof(arr) / 32 + 3] = {0};
    for (int i = 0; i < n; i++)
      bitset[i/32] ^= (arr[i]=='1') << (i % 32);
    //solution: bit operations
    uint32_t result[sizeof(bitset) / sizeof(bitset[0])] = {0};
    for (int i = 0; i < (n + 31) / 32; i++) {
        uint32_t curr = bitset[i], next = bitset[i+1];
        result[i] = curr | (curr >> 1) | (next << 31) | (curr >> 2) | (next << 30);
    }

    printf("%s\n ", arr);
    for (int i = 0; i < n+2; i++)
        printf("%d", (result[i/32] >> (i%32)) & 1);
}

更新

对于可变窗口宽度 W，上述方法需要 O(N W) 时间。对于小 W 它是最快的，但对于大 W 不是很有效。

请注意，对于任何窗口大小，该问题都可以在 O(N) 时间内解决。例如，您可以预先计算 prefix sums在 O(N) 时间内为您的零/一数组。然后对于每个窗口，可以在 O(1) 时间内确定其中的个数作为两个总和值的差值。因此，您会得到一个简单的 O(N) 解决方案。它不使用任何位集，并且是处理非常大的 W 的最快方法。

对于中间窗口大小(如 W = 16)，可以修改基于位集的方法以在 O(N log W) 时间内工作，这可能比 O(N W) 版本更快。该方法有点类似于并行归约。以下是 W = 13 的示例代码:

for (int i = 0; i < (n + 31) / 32; i++) {
    uint64_t curr = *(uint64_t*)&bitset[i];
    curr |= (curr >> 1);
    curr |= (curr >> 2);
    curr |= (curr >> 4);
    curr |= (curr >> 5);
    result[i] = uint32_t(curr);
}