0

私の問題は次のとおりです。

95 個の要素のすべての可能性 (0 または 1) を反復処理する必要があります。

たとえば、要素が 2 つある場合、可能性は次のようになります: 00、01、10、11

可能性の合計数は 2^n であるため、非常に急速に増加します。2^95 = 39614081257132168796771975168

0 から 2^95 まで効果的に反復するにはどうすればよいですか?

PS プログラミング言語の選択は重要ではありませんが、C または C++ が最速の選択であると思います。

PPS BigInt の実装はプリミティブ型よりもかなり遅いように思われるため、数を X 個のプリミティブに分割することをお勧めします。しかし、これまでのところ運がありませんでした。

PPS 0 から 2^95 までの数値を指定することで可能性を生み出す関数があります

4

4 に答える 4

2

量子コンピューターを持っていない限り、範囲全体を繰り返すことから逃れることはできません。最も簡単な方法は、95 ビットを一連のプリミティブに分割することです。たとえば、システムが 64 ビットの数値で動作している場合、そのうちの 2 つを取得できます。擬似コードは次のようになります。

lowBound <-- 2^64-1
highBound <-- 2^31-1
for highIdx = 0 up to highBound
    for lowIdx = 0 up to lowBound
         ; Do your thing here, if you need the actual index,
         ; it's combinable from lowIdx and highIdx

最も速いのはAssembly、アーキテクチャ固有の命令を使用して、プロセスの高速化のためにシステム リソース (レジスタ、キャッシュなど) をより有効に活用することです。GPU の使用を検討することもできます。GPU はタスクの並列化に非常に優れているため、反復ごとに操作が類似している場合は、優れたパフォーマンスが得られます。

ただし、これはすべて役に立たないため、@ KeithThompson の回答に記載されているように、反復ではなく、行っていることに対してより良いアルゴリズムを考案する必要があります。

于 2013-10-26T18:38:02.780 に答える