2

first長さ(<32) の特定のビット ベクトルについてbitnum、同じ長さのすべての辞書式連続ビット ベクトルを反復処理する必要があります。

たとえば、first011001 (バイナリ) でbitnum6 の場合、連続するものはすべて 011011、011101、011111、111001、111011、111101、111111 です。また、011001 も繰り返す必要があります。

私が辞書編集的連続を意味するもの：

  • の i 番目のビットfirstが「1」の場合、の i 番目のビットは「1」でnextなければなりません
  • の i 番目のビットfirstが「0」の場合、の i 番目のビットはnext「0」または「1」になります。

そのようなビットベクトルを生成する最速の方法は何ですか?

今、私はこの最適化されていないコードを使用します。可能なすべてのビットベクトルを生成することで機能し、すべてのベクトルがfirst辞書式の方法で指定されているかどうかを確認します。

uint32_t loop_over_all_lex_succ(int bitnum, uint32_t first) {
    uint32_t next = first;
    uint32_t tmp;
    do { 
      target_function(next);

      do {
        next++;
        tmp = (~first|next); // sets the 0 bit at offset iff `next` has a 0 bit and `first` has 1
        tmp = ~tmp; // invert tmp; now all invalid bits are marked with '1'
        tmp = tmp & ((1<<bitnum)-1); // mask the tmp with target bit number

      } while( (next < (1<<bitnum))  && tmp );

    } while ( next < (1<<bitnum) );
}

コードが連続するビットベクトルのみを生成する場合、より高速になると思います。

Firstベクトルは、このビット長の任意のベクトルです。

生成されたベクトルの順序は異なる場合があります。

この関数またはそのバージョンのベンチマークを実行する場合は、小さなベンチマーク ツールがあります。ループを追加するだけです。関数コード:

#include <stdio.h>
#include <stdint.h>
uint32_t count =0;
void target_function(uint32_t a) { count++; }
/* loop_over_all_lex_succ() here */
int main() {
    uint32_t f;
    int bitnum=16;  // you can increase it up to 31
    for(f=0;f<(1<<bitnum);f++)
        loop_over_all_lex_succ(bitnum,f);
    printf("bits: %d,  count of pairs: %u\n",bitnum,count);
}

たとえば、bitnum=16 の場合、このコードは PC で 6 秒間実行されます。この関数を、最大 31 までのより高いビット数で使用する必要があります。

最適化を手伝ってくださいloop_over_all_lex_succ。

4

2 に答える 2

2

元の質問のものよりも単純で、おそらくより効率的なブルート フォース アプローチを提案します。

uint32_t loop_over_all_lex_succ(int bitnum, uint32_t first) {
    const uint32_t last = 1 << bitnum;
    uint32_t value;

    for (value = first;
         value < last;
         value = (value + 1) | first)
    {
        target_function(value);
    }
    return value;
}

私の 2.67 GHz Core i7 MacBook Pro では、問題のコードは 2.1 秒で実行されますが、上記のコードは 0.04 秒で実行され、約 50 倍のスピードアップになります。

于 2011-03-09T11:19:52.207 に答える
2 
uint32_t loop_over_all_lex_succ(int bitnum, uint32_t first) {
    uint32_t next = first;
    uint32_t tmp;
    do { 
      target_function(next);
      next = (next +1 ) |first;
    } while ( next < (1<<bitnum) );
}

ここではインクリメントを行いますが、すべてのfirstステップですべての 1 ビットをリセットします。0このようなコードでは、最初にあったビットのみをインクリメントします。

于 2011-03-09T12:45:30.383 に答える