最も効率的なアルゴリズムは、主に初期状態に依存します。
セルの大部分が死んでいる場合は、空の部分をスキップし、セルごとにスタッフを計算しないことで、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