50

「0」と「1」を書き込む非常に大きな配列を作成したいと考えています。ランダムシーケンシャル吸着と呼ばれる物理プロセスをシミュレートしようとしています。このプロセスでは、長さ 2 のユニットである二量体が、互いに重なり合うことなく、ランダムな位置で n 次元格子に堆積します。格子上にさらに二量体を堆積する余地がなくなると、プロセスは停止します (格子が詰まります)。

最初にゼロのラティスから始めます。二量体は 1 のペアで表されます。各二量体が堆積すると、二量体が重ならないという事実により、二量体の左側のサイトがブロックされます。そこで、格子上に「1」のトリプルを配置することで、このプロセスをシミュレートします。シミュレーション全体を何度も繰り返してから、平均カバレッジ % を計算する必要があります。

1D および 2D ラティスの文字の配列を使用して、これを既に行っています。現時点では、3D の問題とより複雑な一般化に取り組む前に、コードをできるだけ効率的にしようとしています。

これは基本的にコードが 1D でどのように見えるかを簡略化したものです:

int main()
{
    /* Define lattice */
    array = (char*)malloc(N * sizeof(char));

    total_c = 0;

    /* Carry out RSA multiple times */
    for (i = 0; i < 1000; i++)
        rand_seq_ads();

    /* Calculate average coverage efficiency at jamming */
    printf("coverage efficiency = %lf", total_c/1000);

    return 0;
}

void rand_seq_ads()
{
    /* Initialise array, initial conditions */
    memset(a, 0, N * sizeof(char));
    available_sites = N;
    count = 0;

    /* While the lattice still has enough room... */
    while(available_sites != 0)
    {
        /* Generate random site location */
        x = rand();

        /* Deposit dimer (if site is available) */
        if(array[x] == 0)
        {
            array[x] = 1;
            array[x+1] = 1;
            count += 1;
            available_sites += -2;
        }

        /* Mark site left of dimer as unavailable (if its empty) */
        if(array[x-1] == 0)
        {
            array[x-1] = 1;
            available_sites += -1;
        }
    }

    /* Calculate coverage %, and add to total */
    c = count/N
    total_c += c;
}

私が行っている実際のプロジェクトでは、二量体だけでなく、三量体、四量体、およびあらゆる種類の形状とサイズ (2D および 3D) が含まれます。

バイトではなく個々のビットで作業できることを望んでいましたが、読んでいる限り、一度に1バイトしか変更できないため、複雑なインデックス作成を行う必要がありますまたはそれを行う簡単な方法はありますか？

回答ありがとうございます

4

5 に答える 5

56

手遅れでなければ、このページは素晴らしい説明を例とともに提供します。

の配列をint使用して、 の配列を処理できますbits。のサイズを とintすると4 bytes、 について話すときはintを扱ってい32 bitsます。があるとしますint A[10]。これは、作業中であることを意味し10*4*8 = 320 bits、次の図はそれを示しています: (配列の各要素には 4 つの大きなブロックがあり、それぞれが a を表しbyte、小さいブロックはそれぞれ a を表しますbit)

ここに画像の説明を入力

したがって、k配列の th ビットを設定するには、次のようにしAます。

// NOTE: if using "uint8_t A[]" instead of "int A[]" then divide by 8, not 32
void  SetBit( int A[],  int k )
{
    int i = k/32;        //gives the corresponding index in the array A
    int pos = k%32;      //gives the corresponding bit position in A[i]

    unsigned int flag = 1;   // flag = 0000.....00001

    flag = flag << pos;      // flag = 0000...010...000   (shifted k positions)

    A[i] = A[i] | flag;      // Set the bit at the k-th position in A[i]
}

または短縮版で

void  SetBit( int A[],  int k )
{
    A[k/32] |= 1 << (k%32);  // Set the bit at the k-th position in A[i]
}

同様にkビットをクリアします。

void  ClearBit( int A[],  int k )                
{
    A[k/32] &= ~(1 << (k%32));
}

k番目のビットかどうかをテストするには：

int TestBit( int A[],  int k )
{
    return ( (A[k/32] & (1 << (k%32) )) != 0 ) ;     
}

上記のように、これらの操作はマクロとしても記述できます。

// Due order of operation wrap 'k' in parentheses in case it
// is passed as an equation, e.g. i + 1, otherwise the first
// part evaluates to "A[i + (1/32)]" not "A[(i + 1)/32]"
#define SetBit(A,k)     ( A[(k)/32] |= (1 << ((k)%32)) )
#define ClearBit(A,k)   ( A[(k)/32] &= ~(1 << ((k)%32)) )
#define TestBit(A,k)    ( A[(k)/32] & (1 << ((k)%32)) )
于 2015-06-02T08:11:47.030 に答える
11 
typedef unsigned long bfield_t[ size_needed/sizeof(long) ];
// long because that's probably what your cpu is best at
// The size_needed should be evenly divisable by sizeof(long) or
// you could (sizeof(long)-1+size_needed)/sizeof(long) to force it to round up

これで、bfield_tの各longはsizeof（long）*8ビットを保持できます。

必要なビッグのインデックスは、次の方法で計算できます。

bindex = index / (8 * sizeof(long) );

とあなたのビット番号

b = index % (8 * sizeof(long) );

次に、必要な時間を調べて、必要な部分をマスクします。

result = my_field[bindex] & (1<<b);

また

result = 1 & (my_field[bindex]>>b); // if you prefer them to be in bit0

最初のものは、一部のCPUでより高速であるか、複数のビット配列の同じビット間で操作を実行する必要があるため、シフトバックを節約できる場合があります。また、2番目の実装よりも、フィールドでのビットの設定とクリアをより厳密に反映しています。セットする：

my_field[bindex] |= 1<<b;

クリア：

my_field[bindex] &= ~(1<<b);

フィールドを保持するlongに対してビット単位の演算を使用できることを覚えておく必要があります。これは、個々のビットに対する演算と同じです。

可能であれば、ffs、fls、ffc、およびflc関数も調べてください。ffsは常にで利用可能である必要がありますstrings.h。それはこの目的のためだけにあります-ビットの文字列。とにかく、それは最初のセットを見つけ、本質的に：

int ffs(int x) {
    int c = 0;
    while (!(x&1) ) {
        c++;
        x>>=1;
    }
    return c; // except that it handles x = 0 differently
}

これは、プロセッサが命令を受け取るための一般的な操作であり、コンパイラは、私が書いたような関数を呼び出すのではなく、おそらくその命令を生成します。ちなみに、x86にはこれに関する指示があります。ああ、ffslとffsllは、それぞれlongとlong longを除いて、同じ関数です。

于 2010-03-26T19:52:32.690 に答える
7

& (ビットごとの AND) と << (左シフト) を使用できます。

たとえば、(1 << 3) は 2 進数で "00001000" になります。したがって、コードは次のようになります。

char eightBits = 0;

//Set the 5th and 6th bits from the right to 1
eightBits &= (1 << 4);
eightBits &= (1 << 5);
//eightBits now looks like "00110000".

次に、文字の配列でそれを拡大し、最初に変更する適切なバイトを見つけます。

効率を高めるために、事前にビットフィールドのリストを定義し、それらを配列に入れることができます。

#define BIT8 0x01
#define BIT7 0x02
#define BIT6 0x04
#define BIT5 0x08
#define BIT4 0x10
#define BIT3 0x20
#define BIT2 0x40
#define BIT1 0x80

char bits[8] = {BIT1, BIT2, BIT3, BIT4, BIT5, BIT6, BIT7, BIT8};

次に、ビットシフトのオーバーヘッドを回避し、ビットにインデックスを付けて、前のコードを次のように変換できます。

eightBits &= (bits[3] & bits[4]);

あるいは、C++ を使用できる場合はstd::vector<bool>、ビットのベクトルとして内部的に定義された を使用して、直接インデックスを作成することもできます。

于 2010-03-26T17:34:10.793 に答える
2

それはトレードオフです：

(1) 2 ビット値ごとに 1 バイトを使用 - シンプルで高速ですが、4 倍のメモリを使用します

(2) ビットをバイトにパック - より複雑で、いくらかのパフォーマンス オーバーヘッドがあり、最小限のメモリしか使用しません

利用可能なメモリが十分にある場合は (1) に進み、それ以外の場合は (2) を検討してください。

于 2010-03-26T17:35:31.137 に答える