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 のサブセットが含まれることがわかるようにすることができます (現在のバイト）など。

する方法を見つける必要があります。

  • 同じキーで複数のサブセットを管理する (例: 01011010)
  • 左バイトと右バイトを考慮し、サブセット長の一部としてキーの長さを追加する必要があるように、すべて 1 のキーを管理します。

ただし、最初と最後のビットが 0 であるすべてのキーは簡単に管理されるため、一部の可能なキーに必要な処理量を削減できます。

開発するのは難しいと思いますが、面白いかもしれません。他のすべてはルックアップ テーブルにハードコーディングされているため、最終的にはキーの比較を行うだけで済みます。もちろん、最終的なアルゴリズムが単純なアプローチよりも優れているかどうかはわかりませんが、私の意見では、チャンスを与える価値があります。

于 2012-06-04T14:30:49.087 に答える