0

2 つの N ビットの数値 (0< N< 100000) があります。これらの数値に対して q 個のクエリ (0< q<500000) を実行する必要があります。クエリには、次の 3 つのタイプがあります。

  • set_a idx x: A[idx] を x に設定します。ここで、0 <= idx < N であり、A[idx] は A の idx 番目の最下位ビットです。

  • set_b idx x: B[idx] を x に設定します。ここで、0 <= idx < N です。

  • get_c idx: C[idx] を出力します。ここで、C=A+B、および 0<=idx です。

これで、できる限りコードを最適化しました。

  • まず、a、b、c の int 配列を試してみました。更新ごとに c を計算し、照会すると i 番目のビットを返します。めちゃくちゃ遅かった。4/11のテストケースのみクリア。

  • ブール配列の使用に移行しました。int 配列アプローチよりも約 2 倍高速でした。7/11 テストケースをクリアした。

  • 次に、A+B の idx 番目のビットを計算するために c を計算する必要がないことがわかりました。a[i]=b[i]=0 または a[i]=b[i]=1 が見つかるまで、idx から右に向かって A と B をスキャンします。a[i]=b[i]=0 の場合、最初のキャリー = 0 から idx 番目のビットまで左に向かって加算します。そして、a[i]=b[i]=1 の場合、最初のキャリー = 1 から idx 番目のビットまで左に向かって加算します。これは高速でしたが、8/11 テストケースのみをクリアしました。

  • 次に、私は一度考え出しました、私は位置i、a [i] = b [i] = 0またはa [i] = b [i] = 1に到達し、idx番目の位置に向かって合計する必要はありません。a[i]=b[i]=0 の場合、答えは (a[idx]+b[idx])%2 となり、a[i]=b[i]=1 の場合、答えは (a[ idx]+b[idx]+1)%2. 約 40% 高速化されましたが、それでも 8/11 のテストケースしかクリアできませんでした。

ここで私の質問は、これら 3 つの「難しい」テストケースをどのように解決するかということです。それらが何であるかはわかりませんが、プログラムは問題を解決するのに 3 秒以上かかります。

コードは次のとおりです。http://ideone.com/LopZf

4

2 に答える 2

0

可能な最適化の1つは、置き換えることです

(a[pos]+b[pos]+carry)%2

と

a[pos]^b[pos]^carry

XOR演算子（^）は2を法とする加算を実行するため、コストがかかる可能性のあるmod演算（％）は不要です。言語とコンパイラーによっては、コンパイラーが2の累乗でmodを実行するときに最適化を行う場合があります。ただし、マイクロ最適化を行うのは簡単な変更であり、最適化の背後で行われている最適化への依存を排除​​します。シーン。

http://en.wikipedia.org/wiki/Exclusive_or

これは、簡単に作成できる提案の1つにすぎません。他の人が示唆しているように、ビット配列を表すためにパックされたintを使用すると、コードのおそらく最悪の場合のテストも改善される可能性があります。これが最上位ビットのget_c関数であり、他のすべての位置ではAまたはB（両方ではない）のいずれかが1であり、キャリーを決定するためにすべてのビット位置を最下位ビットまでスキャンする必要があります。ビットにパックされたintを使用している場合、必要な操作の数は約1/32になります（32ビットのintを想定）。ただし、パックされたintの使用は、単純なブール配列（実際にはバイトの配列である可能性が高い）を使用するよりも多少複雑になります。

C /C++ビット配列またはビットベクトル

ビット配列をuintまたは同様のパック値に変換します

http://en.wikipedia.org/wiki/Bit_array

Stackoverflowとネットには、ビット配列であるかのようにintを使用するための例が他にもたくさんあります。

于 2012-05-15T15:32:24.363 に答える
0

これは、アルゴリズムに少し似たソリューションです。私はバイトでそれを示していますが、もちろん、32ビットワードを使用してアルゴリズムを簡単に最適化できます（最近のマシンには64ビット演算があると思います）。

void setbit( unsigned char*x,unsigned int idx,unsigned int bit)
{
   unsigned int digitIndex = idx>>3;
   unsigned int bitIndex = idx & 7;
   if( ((x[digitIndex]>>bitIndex)&1) ^ bit) x[digitIndex]^=(1u<<bitIndex);
}
unsigned int getbit(unsigned char *a,unsigned char *b,unsigned int idx)
{
   unsigned int digitIndex = idx>>3;
   unsigned int bitIndex = idx & 7;
   unsigned int c = a[digitIndex]+b[digitIndex];
   unsigned int bit = (c>>bitIndex) & 1;
   /* a zero bit on the right will absorb a carry, let's check if any */
   if( (c^(c+1))>>bitIndex )
   {
      /* none, we must check if there's a carry propagating from the right digits */
      for(;digitIndex-- > 0;)
      {
         c=a[digitIndex]+b[digitIndex];
         if( c > 255 ) return bit^1; /* yes, a carry */
         if( c < 255 ) return bit;   /* no carry possible, a zero bit will absorb it */
      }
   }
   return bit;
}

何か謎めいたものを見つけたら、聞いてください。編集：おっと、ゼロビット状態を反転させました...

于 2012-06-29T21:43:14.390 に答える