字符数组上的累积BitWise OR

Question

我有一个7K的长字符数组。

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

我必须在窗口大小为3的数组上执行累积OR。这意味着：

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)时间内解决。例如，您可以在O(N)时间内预先计算0/1数组的prefix sums。然后，对于每个窗口，可以将O(1)时间内的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);
}

Answer 2

如果你有一个大小为N的数组，其中只包含0和1，并且你想要ORing每K个项目的结果(其中K是窗口大小)，那么你所要做的就是跟踪最后一个“1”的位置。

int last1 = -1;
int range_start = 0;
int range_end = window_size - 1;
for (int i = 0; i < array_size; ++i)
{
    if (a[i] == '1')
    {
        last1 = i;
    }
    if (i == range_end)
    {
        if (last1 >= range_start)
            // output 1
        else
            // output 0
    }
    ++range_start;
    ++range_end;
}

这里的想法是，如果窗口中有一个或多个1，则任何窗口大小的累积OR都将为1。如果窗口包含全0，则结果为0。

通过在单独的循环中查看第一个window_size - 1值，从而消除range_end变量，您可以对此进行一点优化，但这会使您的循环稍微复杂一些。我不知道这会不会是一场胜利。

Answer 3

为了清楚起见，您希望输出数组中有n个元素，每个元素的值都是arrn-1 | arrn | arrn+1。(可能的例外是第一个和最后一个元素，它们分别没有arrn-1和arrn+1。

如果这是正确的，那么不可能在少于O(n)的时间内做到这一点。您需要至少查看数组中的每个元素一次，仅此一项就需要O(n)时间。

幸运的是，即使是最天真的方法也能满足这个O(n)目标：

int size = strlen(arr);
char arr2[size];
for (int i=1; i<size-1; i++) { //ignore first and last element
    if (arr[i-1] == '1' || arr[i] == '1' || arr[i+2] == '1') {
        arr2[i] = '1';
    } else {
        arr2[i] = '0';
    }
}

在这一点上，你必须决定你所说的“高效”是什么意思。您需要决定是否要减少比较或分配。根据您的情况，这两种选择中的任何一种都可能是有效的选择，并会产生截然不同的解决方案。