3

私の大学のプロセスでは、ランダムシーケンシャル吸着と呼ばれるプロセスをシミュレートしています。私がしなければならないことの 1 つは、正方形 (重なり合うことはできません) をラティス上にランダムに配置し、残りのスペースがなくなるまで、このプロセスを数回繰り返して、平均の「ジャミング」カバレッジ % を見つけることです。

基本的に、整数の大きな配列に対して操作を実行しています。そのうちの 3 つの可能な値は、0、1、および 2 です。「0」でマークされたサイトは空で、「1」でマークされたサイトはいっぱいです。最初に、配列は次のように定義されます。

int i, j;
int n = 1000000000;
int array[n][n];

for(j = 0; j < n; j++)
{
    for(i = 0; i < n; i++)
    {
        array[i][j] = 0;
    }
}

正方形が「1」で表されるように、5*5 の正方形を配列にランダムに配置したいとします (オーバーラップできません)。これは、x 座標と y 座標をランダムに選択し、その点から始まる正方形の左上点で '1' の 5*5 正方形を作成することによって行われます。次に、広場に近いサイトを「2」とマークします。これらのサイトに正方形を配置すると、既存の正方形と重なってしまうため、これらは利用できないサイトを表しています。このプロセスは、アレイに正方形を配置する余地がなくなるまで続きます (基本的に、アレイに「0」がなくなる)。

とにかく、ポイントに。ビット単位の操作を使用して、このプロセスをできるだけ効率的にしたいと考えています。正方形の近くのサイトをマークする必要がなければ、これは簡単です。「2」でマークされたサイトを説明できるように、2ビットの数値を作成できるかどうか疑問に思っていました.

これが本当に複雑に聞こえる場合は申し訳ありませんが、これを行う理由を説明したかっただけです。

4

4 に答える 4

11

アドレスできないため、サイズが2ビットのデータ型を作成することはできません。あなたができることは、いくつかの2ビットの数値をより大きなセルにパックすることです。

   struct Cell {
      a : 2;
      b : 2;
      c : 2;
      d : 2;
   };

これは、メンバー、、、のそれぞれがaメモリb内の2ビットを占める必要cがあることを指定します。d

編集：これは2ビット変数を作成する方法の単なる例です。問題の実際の問題の場合、最も効率的な実装は、おそらく配列を作成し、いくつかの/メソッドintでビットをいじることをまとめることです。setget

于 2010-03-23T12:58:55.280 に答える
4

2 ビット配列の代わりに、2 つの別個の 1 ビット配列を使用できます。1 つは塗りつぶされた正方形を保持し、もう 1 つは隣接する正方形 (または、より効率的な場合は使用可能な正方形) を保持します。

2ビットフィールドを単語に詰め込むよりも利点があるかどうかはよくわかりません。あなたが本当にメモリ不足でない限り、私はバイト配列を選びます。

于 2010-03-23T13:06:53.070 に答える
3

基本的な考え方

残念ながら、C でこれを行う方法はありません。1 バイト、2 バイトなどの配列を作成できますが、ビットの領域を作成することはできません。

したがって、あなたができる最善の方法は、自分用に新しいライブラリを作成することです。これにより、2 ビットの配列を扱っているように見えますが、実際には多くの困難な作業が行われます。文字列ライブラリが「文字列」(C では単なる配列) で動作する関数を提供するのと同じ方法で、「ビット配列」(実際には整数の配列) で動作する新しいライブラリを作成します。それらをビットの配列であるかのように処理するためのいくつかの特別な関数を使用します)。

注: C を初めて使用し、「新しいライブラリ/モジュールを作成する」という考え方や「抽象化」の概念をまだ学んでいない場合は、このプロジェクトを続行する前にそれらについて学ぶことをお勧めします。それらを理解することは、プログラムを最適化して使用するスペースを少し減らすよりも重要です。

この新しい「ライブラリ」またはモジュールを実装する方法

あなたのニーズに合わせて、「2ビット配列」と呼ばれる新しいモジュールを作成します。これは、必要に応じて2ビット配列を処理するための関数をエクスポートします。

ビットの設定/読み取りを処理する関数がいくつかあるため、実際のビット配列があるかのように操作できます（実際には整数の配列などがありますが、モジュールはそれをビットの配列があるように）。

このモジュールを使用すると、次のようになります。

// This is just an example of how to use the functions in the twoBitArray library.
twoB my_array = Create2BitArray(size); // This will "create" a twoBitArray and return it.
SetBit(twoB, 5, 1); // Set bit 5 to 1 // 
bit b = GetBit(twoB, 5); // Where bit is typedefed to an int by your module.

モジュールが実際に行うことは、整数の通常の古い配列を使用してこれらすべての関数を実装することです。

たとえば、関数GetBit()forGetBit(my_arr, 17)は、それが配列の 4 番目の整数の 1 番目のビットであることを計算し (明らかに に依存しますsizeof(int))、ビット演算を使用してそれを返します。

于 2010-03-23T13:16:37.483 に答える
2

配列の 1 つの次元をサブ整数セルに圧縮できます。座標 (たとえば x としましょう) をバイト内の位置に変換するには:

byte cell = array[i][ x / 4 ];
byte mask = 0x0004 << (x % 4);
byte data = (cell & mask) >> (x % 4);

データを書き込む 逆を行う

于 2010-03-23T13:08:24.300 に答える