4

有长度为 N 的位集（大约为 500-700）。我需要计算每个仅包含 1 的子集的数量

例子

N = 32

设置 = 0* 11 *0* 111 *00* 1 *0* 1 *00* 1111 *0* 11 *00* 111 *000* 1 *0* 1 *

输出 = { [1] = 4, [2] = 2, [3] = 2, [4] = 1, [5] = 0, ... [32] = 0 }

void get_count(int tab[], int len) {
int *out = calloc(1, sizeof(*out) * INT_BIT * len);
int i, j, k;
int cur;
int count = 0;

for(i = 0; i < len; i++) {
    cur = tab[i];
    for(j = 0; j < INT_BIT; j++) { 
        count += (cur & 1);
        if(!(cur & 1)) { 
            out[count]++; 
            count = 0; 
        }
        cur >>= 1;
    }
}

for(i = 0; i < INT_BIT * len; i++) {
    printf("%d ", out[i]);
}
printf("\n");
free(out);
}

这个简单的操作将执行大约数十亿次。迭代每一位太慢了。如何优化这个算法？

4

1 回答 1

2

我会使用查找表来选择适当的维度（可能是 8 位或 16 位键）。

在这个查找表中，我会将每个键与 4 个值相关联：

  • 附加到左侧的 1 位数
  • 附加到右侧的 1 位数
  • 中间未附加任何东西的子集数
  • 中间子集的大小

例如，您可以将密钥11011011与 2,2,2 相关联，这样您就知道右侧至少附加 1 位的左侧相邻字节将包含其大小 + 2 的子集（当前的左侧附加长度）字节）等等。

你需要找到一种方法

  • 在同一个键中管理超过 1 个子集（例如01011010）
  • 管理一个全为 1 的密钥，以便您必须考虑左字节和右字节，并将密钥长度添加为子集长度的一部分。

但是第一个和最后一个位为 0 的每个键都被简单地管理，因此您可以减少某些可能的键所需的处理量。

我想开发起来很棘手，但它也可能很有趣，最后你只需要对键进行比较，因为其他所有内容都在查找表中进行了硬编码。当然，我不确定最终的算法是否会优于简单的方法，但我认为值得给它一个机会。

于 2012-06-04T14:30:49.087 回答