こんにちは、現在の状態を維持する配列と次の状態を維持する配列の 2 つの配列を使用する単純なゲーム オブ ライフ コードを作成しました。メモリ消費のためにこのプログラムを最適化する方法を誰でも提案できますか? 理想的には、スペースの複雑さを RC よりも小さくしたいと考えています。
質問する
2017 次
5 に答える
4
それは、あなたの競技場がどれほどまばらであるかによって異なります。競技場が密集している場合、ストレージ アルゴリズムのスペースの複雑さはRC に向かう傾向にあります。(具体的には、RC/2 です。アクティブでないセルよりも多くのアクティブなセルを取得すると、最適なスペースの使用を本当に気にかけている場合は、代わりに非アクティブなセルを格納することができます。)
競技場がまばらな場合は、アクティブ セルごとの座標ペアまたは他の疎行列構造を格納するだけで、代わりにアクティブ セルの数に応じてスケーリングするものを取得できます。
于 2010-08-24T08:12:09.337 に答える
2
私はGOLについてあまり知りませんが、空の「正方形」がたくさんあると仮定して、Sparse Matrixesを見ましたか?
于 2010-08-24T08:11:55.547 に答える
1
遅い答えですが、それでも。
golly のソースコードをチェックしてください: http://golly.sourceforge.net/
しかし、それを行う前に、http
://www.ibiblio.org/lifepatterns/lifeapplet.html にアクセス
して、そこでコードを見てください。これは Java ですが、非常に高速です。
Alan Hensel の Web サイトからのこの引用は、あなたの質問に答えるはずです。
どうやってそんなに速く走らせたの？ふつうの観察者は、私のアプレットが非常に高速であることに気付かないかもしれません。「ワープ速度」ボタンを見つけられなかったり、使用したことがなかったり、あまり印象に残っていない可能性があります。次のセクションにスキップできます。
しかし、一体どうやってそんなに速く走らせたの?!と尋ねる人もいます。好奇心旺盛な人、または独自の超高速セル オートマトン プログラムを作成しようと考えている人に説明します。
セルオートマトンの最適化は、データ圧縮に関連していると考える傾向があります。これも単純な解決策のない単純な概念であり、最適な解決策は処理されるデータの種類によって異なります。Conway's Life では、パターンがぼんやりする傾向があります。
ぼんやりしたユニバースの場合、ユニバースをほぼブロブのサイズのブロックに分割することを検討する必要があります。Life の場合、4x4 から 8x8 が妥当なようです。便宜上、上限の 8x8 を選択しました。1 バイトはたまたま 8 ビットです。4x4を強く考えましたが、うまくいきませんでした....
宇宙の空の部分で時間を無駄にしないように、ブロックをある種のリストに入れる必要があります。
すでに複雑なことに注意してください。パターンがブロックの境界を超えて成長する場合、リスト内の新しい要素を導入する必要がありますが、ブロックの隣接要素が既に存在するかどうかを知る必要があります。リストの単純な線形検索、またはバイナリ検索を実行するか、何らかのマップを保持することができます。ハッシュテーブルを作成することにしました。これは、新しいブロックの隣接ブロックを見つけるためにのみ使用されます。既存の各ブロックは、頻繁に参照されるため、隣接するブロックへのポインターを既に保持しています。
ブロック内には効率的なアルゴリズムも必要です。私は主に各ブロックを真っ直ぐに通過することを選択しました。ブロック内のすべてのセルが処理されるまで、内部ループはありません。また、高速ルックアップ テーブルが採用されています。内側の 2x2 を決定するために 4x4 ブロックを調べます。
注: 通常、CA プログラムは 2 つのメイン ループ (および表示ループ) で構成されます。これは、マイクロプロセッサが概念的にシリアルであるのに対し、CA ルールはセルに対して並列に動作するためです。これは、次世代を作成する過程で重要な情報が破壊されないように、効果的に宇宙の 2 つのコピーが存在する必要があることを意味します。多くの場合、これら 2 つのコピーは対称ではありません。1 つのループから何かを取り出して高速化するたびに、別のループに別の何かを追加する必要があったため、これは私にとって大きな苦労でした。ほぼ毎回、つまり; その規則の例外は、最良の最適化につながります。特に、ビット操作で考慮すべき適切なトレードオフがあります: シフト、マスキング、ルックアップ テーブル内のアドレスを形成するための再結合....
また、場合によっては、ブロックの内容が安定し、それ以上の処理を必要としない場合もあると考えられます。ブロックをリストから外して「ハイバネーション」状態にし、隣接するブロックになんらかのアクティビティが流れ込んでいる場合にのみ再アクティブ化することができます。これらのブロックは、宇宙の空白の領域と同じように、処理時間がゼロになります。
周期 2 オシレータも、検出がそれほど難しくなく、処理時間から除外される場合があります。ウインカーは最も一般的な種類のランダムな破片であるため、これは人生において価値があるかもしれません。より高い周期オシレータは、はるかにまれです。グライダーを検出してシミュレートすることも可能です。極端にしない限り、この種の最適化から得られる利益は減少します (HashLife を参照)。
また、完全に空のセルのブロックは、しばらくの間、割り当てを解除してハッシュ テーブルから削除する価値がない場合があります。これにはある程度の処理時間がかかります。これは、振動子がその空間に繰り返し出入りする場合に重要になる可能性があります。メモリが少なくなった場合にのみ、「遺体安置所」からの最も古いブロックをリサイクルする必要があります。
プログラムが十分に高速である場合、目に見えるよりも速く世代を表示する価値はなく、少なくともモニターのリフレッシュ レートよりもはるかに高速ではないことを考慮する必要があります。特にウィンドウ環境では、表示時間が実際のボトルネックになる可能性があります。
次に、このソースコードを読んでください: http://www.ibiblio.org/lifepatterns/src.41d/LifeCell.java
これには、アランのライフ ユニバースを保持するデータ構造が含まれています。
hashlife のことは忘れてください。頭が回転するほど複雑です。
于 2011-05-28T23:00:48.257 に答える
0
他の回答者は、あなたの州の他のデータ構造を探すのに良い点があります。しかし、それとは関係なく、状態への 2 つのポインターを使用する単純な最適化が機能している可能性があります (既に実行している可能性があります)。したがって、2 つの配列コピーを行う代わりに、1 つのコピーと 3 つのポインター割り当てを行います。
state curr, next;
[...]
for (;;) {
next = advance(curr);
curr = copy(next);
}
これに：
state s1, s2;
state *curr, *next;
[...]
for (;;) {
*next = advance(*curr);
/* swap pointers */
state *tmp = curr;
curr = next;
next = tmp;
}
于 2010-08-24T08:26:50.517 に答える
0
nonnb と Amber が推奨するように、疎行列をお勧めします。書き込むプロセッサの能力がある場合、またはディスクにシリアル化したい場合は、エンコーディングを調べることもできます。RLE またはトークン ベースの圧縮を使用すると、問題が解決する可能性があります。
于 2010-08-24T08:28:40.337 に答える