1

バイナリシーケンスを考えてみましょう:

11000111

このシリーズの合計を見つける必要があります（実際には並行しています）

合計 =1+1+0+0+0+1+1+1= 5

これはリソースの無駄です。なぜ 0 の追加に時間を費やすのでしょうか。

不必要な追加を避けるために、このシーケンスを合計する賢い方法はありますか?

4

4 に答える 4

2

ビット レベルではなく、バイト レベルで動作します。小さな LUT を使用して、バイトを人口カウントに変換します。そうすれば、8 ビットごとに 1 回のルックアップと 1 回の加算のみを行うことができます。データが非常にまばらでない限り、これは非常に効率的です。

于 2012-10-02T12:24:53.360 に答える
0

最初のコメントから質問へのリンクを調べていなくても、なぜ人々が答えているのかわかりません。あなたは簡単にそれを下に作ることができますO(size_of_bitset)。それが一定の要因になると、最悪の場合。

この方法を使用できます（JFセバスティアンのリンクにあります）。

inline int count_bits(int num){
int sum = 0;
for (; bitset; sum++) bitset &= bitset-1;
return sum;
}

int main (void){
  int array[N];
  int total_sum = 0;
  #pragma omp parallel for reduction(+:total_sum)
  for (size_t i = 0; i < N, i++){
     total_sum += count_bits(array[i]);
  }
}

array並列のメモリ範囲のビット数をカウントします。インラインは、不要なコピーを回避するために重要です。また、コンパイラーは、インラインをより適切に最適化する必要があります。

count_bits整数のビットをカウントするより良いものと交換して、何かが見つかった場合に高速化することができます。このバージョンの複雑さはO(bits_set)（ビットセットのサイズではありません！）です。

並列構造を呼び出すと、補償するためにかなり大きくする必要がある単一の合計と比較して、かなり多くのオーバーヘッドが発生します。

並列処理はOpenMPを介して行われます。各スレッドの部分的な合計は、並列ループの最後で合計され、に格納されtotal_sumます。削減句によりtotal_sum、各スレッドのループ内でプライベートになることに注意してください。reduction

コードを変更して、任意のメモリ領域に設定されたビットをカウントするようにすることもできますが、このような低レベルで操作を実行する場合は、メモリを揃えることが非常に重要です。

于 2012-10-02T12:51:31.040 に答える
0

ビットセットの保管方法によって異なります。配列の場合、単純な for 以上のことはできません。これを並行して行いたい場合は、配列をチャンクに分割して同時に処理します。

ビットセット (ネイティブ (32/64 ビット) 整数型でビットを格納する) について話している場合、ビットをカウントする最も簡単な方法は次のとおりです。

int bitset;
int s = 0;
for (; bitset; s++)
    bitset &= bitset-1;

これにより、すべてのステップで 1 の最後のビットが削除されるため、O(s) になります。

もちろん、32/64 ビット以上が必要な場合は、これら 2 つの方法を組み合わせることができます。

于 2012-10-02T12:15:53.043 に答える
-1

私が見る限り、ゼロを特別に処理しようとするのは無駄です。@bdaresが言ったように、追加は本当に安いです。少なくとも、N ビット シーケンスを合計するには、N 命令を実行する必要があります。これは、ビットを無条件に合計する場合です。ビットが 0 か 1 かを確認するテストを追加すると、それは各ビットに対して実行する必要がある別の命令になります。分岐ペナルティがなくても、ビットごとに最小 1 つの命令を実行し (条件テスト)、1 に等しいビットに対して元の命令 (加算) も実行します。したがって、分岐がなくてもペナルティ、これは実行に時間がかかります。

@bdares は、コンパイラが分岐を最適化すると述べていますが、それはコンパイル時に各ビットの値がわかっている場合のみであり、コンパイル時にビットの値がわかっている場合は、事前にそれらを自分で追加する必要があります。

ちょっといじってみるとかわいいものができるかも。たとえば、一度に 2 つのビットを取得すると、0、1、2、または 3 の値を合計することになり、実行する追加の数は半分しかありません。結果を必要な値に変換するために何かできることがありますが、実際にそれを行う方法については考えていません。

于 2012-10-02T12:20:51.347 に答える