実験するために、私は（ずっと前に）コンウェイのライフゲームを実装しました（そして、この関連する質問を知っています！）。
私の実装は、「最後の状態」と「更新中の状態」を表す2つのブール値の配列を保持することで機能しました（2つの配列は各反復で交換されます）。これはかなり高速ですが、これを最適化する方法についてよく疑問に思います。
たとえば、1 つのアイデアは、反復 (N+1) で変更できるゾーンを反復 N で事前計算することです (そのため、セルがそのようなゾーンに属していない場合、そのセルは変更の対象とは見なされません)。反復 (N+1))。これが非常に漠然としていることは承知しており、詳細に入る時間はありませんでした...
Game of Life のイテレーションを (速度のために) 最適化する方法についてのアイデア (または経験!) はありますか?
私が言及する章にはいくつかの非常に興味深く微調整された解決策があるので、私は他の質問から私の答えを引用するつもりです。実装の詳細の一部はcおよび/またはアセンブリにありますが、ほとんどの場合、アルゴリズムは任意の言語で機能します。
MichaelAbrashのGraphicsProgrammer'sBlack Bookの第17章と第18章は、私がこれまでに読んだ中で最も興味深い読み物の1つです。それは、既成概念にとらわれずに考えることの教訓です。本全体は本当に素晴らしいですが、人生ゲームの最終的な最適化されたソリューションは、プログラミングの信じられないほどのビットです。
（メモリから）8つ以上の隣接する正方形のセルをビットパターンとして表し、それを事前に計算された値の大きな配列へのインデックスとして使用して、セルが生きているか死んでいるかを単一のマシン命令で判断する超高速の実装がいくつかあります。
ここをチェックしてください：
http://dotat.at/prog/life/life.html
また、XLife：
ArbashのBlackBookで述べたように、大幅な高速化を実現するための最も簡単で簡単な方法の1つは、変更リストを保持することです。
セルグリッド全体を毎回繰り返すのではなく、変更したすべてのセルのコピーを保持します。
これにより、各反復で実行する必要のある作業が絞り込まれます。
アルゴリズム自体は本質的に並列化可能です。最適化されていない CUDA カーネルで同じダブル バッファ方式を使用すると、4096x4096 でラップされた世界で 1 世代あたり約 25 ミリ秒になります。
最も効率的なアルゴリズムは、主に初期状態に依存します。
セルの大部分が死んでいる場合は、空の部分をスキップし、セルごとにスタッフを計算しないことで、CPU 時間を大幅に節約できます。
私の意見では、最初の状態が「ランダムですが、ライフの可能性が 5% 未満」のような場合は、最初に完全にデッド スペースをチェックするのが理にかなっています。
マトリックスを半分に分割し、最初に大きなものをチェックし始めます。
したがって、フィールドが 10,000 * 10,000 の場合、最初に左上 4 分の 5,000 * 5,000 の状態を累積します。
状態の合計が第 1 四半期でゼロの場合は、この第 1 四半期を完全に無視して、右上の 5,000 * 5,000 で次の生命を確認できます。
状態の合計が 0 より大きい場合は、第 2 四半期を再び 4 つの部分に分割します。これらの部分空間のそれぞれについて、このチェックをライフに対して繰り返します。
8*8 または 10*10 のサブフレームに下げることができます (ここで何が最も理にかなっているのかわかりません)。
生命を見つけるたびに、これらのサブスペースを「生命がある」とマークします。
「生命がある」スペースのみを小さなサブスペースに分割する必要があります。空のスペースはスキップできます。
「has life」属性を可能なすべてのサブスペースに割り当て終わったら、サブスペースのリストができあがります。これを各方向に +1 ずつ拡張するだけで、空のセルを使用して、次の通常の (または変更された) ゲームを実行します。人生のルール。
10,000*10,000 の空間を 8*8 の部分空間に分割することは、かなりのタスクであると考えるかもしれませんが、実際には、状態値を累積することは、各セルとその 8 つの隣接セルに GoL アルゴを実行するよりもはるかに少ない計算作業です。数値を比較し、ネット反復の新しい状態をどこかに保存します...
しかし、上で述べたように、人口が 30% のランダムな初期状態の場合、これはあまり意味がありません。完全に死んでいる 8*8 サブスペースを見つける必要はあまりないからです (死んでいる 256*256 サブスペースはそのままにしておきます)。
そしてもちろん、完璧な最適化の方法は持続しますが、言語によって異なります。
-110
2つのアイデア：
（1）多くの構成は、ほとんどが空きスペースです。生細胞のリンクリストを保持し（必ずしも順番に並べる必要はありませんが、時間がかかります）、更新中は生細胞の周囲のみを更新します（これは漠然とした提案であるOysterDに似ています:)
（2）3つの位置（左-中央-右）の各行に生細胞の数を格納する追加の配列を保持します。これで、セルの新しいデッド/ライブ値を計算するときに、4つの読み取り操作（上/下の行と中央側の位置）と4つの書き込み操作（影響を受ける3つの行の要約値とデッド/新しいセルのライブ値）。これは、書き込みが読み取りより遅くないと仮定すると、8回の読み取りと1回の書き込みからわずかに改善されます。私はあなたがそのような構成でより賢くなり、これらの線に沿ってさらに良い改善に到達することができるかもしれないと推測しています。
これがどのように行われるかは正確にはわかりませんが、私の友人の何人かは、このゲームのグリッドを割り当てのために Quadtree で表現しなければならなかったことを覚えています。基本的に占有セルのみを表すため、グリッドのスペースを最適化するのに非常に適していると思います。ただし、実行速度についてはわかりません。
これは 2 次元オートマトンなので、おそらく最適化手法を調べることができます。あなたの考えは、各ステップでチェックする必要があるセルの数を圧縮することについてのようです。占有されているセルまたは占有されているセルに隣接するセルのみをチェックする必要があるため、そのようなセルすべてのバッファーを保持し、各セルを処理するたびに各ステップで更新することができます。
フィールドが最初に空の場合、これははるかに高速になります。おそらく、すべてのセルを処理するよりもバッファーを維持する方がコストがかかるバランス ポイントを見つけることができます。
これには、各テーブル ルックアップで複数のセルを解決するテーブル駆動型のソリューションがあります。Google クエリでいくつかの例が得られるはずです。