1

私がやりたいことは次のとおりです。

入力: n、たとえば n = 3

出力: {000, 001, 010, 011, 100, 101, 110, 111}、すべてのサブセットを生成し、サブセットの順序は気にしません

私はアルゴリズムを実装しました：

for (long i = 0, max = 1 << n; i < max; i++) {
    for (int j = 0; j < n; j++) {
        // check if the j bit is set to 1
        int isSet = (int) i &  1 << j;
        if (isSet > 0) {
            // if yes, set the corresponding jth bit of x as 1.
        }
    }
    // add x to results;
}

私は、Gray Code がこのようなことを実行できることを知っています。しかし、サブセットを生成する最も効率的な方法はどれですか?

4

1 に答える 1

2

「最も効率的」という正確な意味はわかりませんが、速度の最適化を探している場合、より高速なアルゴリズムを見つけることができるとは思えないため、いくつかの小さな最適化のみを期待できます。

速度を向上させたい場合は、試してみてください (これによりコードが実際に速度が向上する場合は、常にプロファイルを作成してください! ):

  • 外側のループ: ifが に収まるほど小さい場合intの代わりに使用するバージョンを作成します。これはもっと速いかもしれません。longmaxint
  • 内側のループ: 両方のループの外側ですべてのビット テスト マスクを計算し、それらを配列に格納できます。このように1 << jして、配列ルックアップで置き換えます。[これで速度が向上するかどうかはわかりませんが、試してみる価値はあります]

あなたも交換する必要があります

int isSet = (int) i &  1 << j;
if (isSet > 0) {
    // if yes, set the corresponding jth bit of x as 1.
}

に：

if (0!=(int) i &  1 << j) {
    // if yes, set the corresponding jth bit of x as 1.
}

変数が別の場所で再び必要な場合を除きますisSet。

グレイ コードについて: これによりビット変更の数が最小限に抑えられますが、それによってすべてのサブセットの生成がどのように改善されるかはわかりません。それらを繰り返しながら、1 つの要素だけが異なります。

于 2015-12-21T10:16:18.653 に答える