7

これは、「アプローチ」または概念的な質問のほうが多いかもしれません。

基本的に、私はPythonのような多次元リストを持っています:

my_list = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]]

私がしなければならないことは、配列を反復処理し、リストがマトリックスとして配置されているかのように、各要素を直接周囲の要素と比較することです。

たとえば、最初の行の最初の要素 が与えられた場合、とのmy_list[0][0]値を知る必要があります。「周辺」要素の値によって、現在の要素をどのように操作するかが決まります。もちろん、配列の中心にある要素の場合、8 回の比較が必要になります。my_list[0][1]my_list[1][0]my_list[1][1]

これで、上記のように、配列を単純に反復処理して、インデックス付きの値と比較できることがわかりました。必要な反復の量を制限するより効率的な方法があるかどうかについて興味がありましたか? 配列をそのまま反復処理するか、値のみを反復して比較し、配列を転置して再度実行する必要があります。ただし、これは対角線の値を無視します。同じ要素の値を何度も決定し続けないように、要素検索の結果を保存する必要がありますか?

これはコンピュータ サイエンスの基本的なアプローチであると思われます。私の問題に対する具体的な答えを探すのではなく、Python を使用した最善のアプローチについてフィードバックを得たいと思っています。

4

1 に答える 1

6

numpyやその他の代替手段を使用することで、より高速で、場合によってはさらに単純なコードを取得できます(詳細については、以下を参照してください)。しかし、理論的な観点からは、アルゴリズムの複雑さに関して、得られる最高のものは O(N*M) であり、設計でそれを行うことができます (私が正しく理解している場合)。例えば：

def neighbors(matrix, row, col):
    for i in row-1, row, row+1:
        if i < 0 or i == len(matrix): continue
        for j in col-1, col, col+1:
            if j < 0 or j == len(matrix[i]): continue
            if i == row and j == col: continue
            yield matrix[i][j]

matrix = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]]

for i, row in enumerate(matrix):
    for j, cell in enumerate(cell):
        for neighbor in neighbors(matrix, i, j):
            do_stuff(cell, neighbor)

これには、N * M * 8 のステップが必要です (実際には、多くのセルの隣接セルが 8 未満になるため、それよりも少し少なくなります)。アルゴリズム的には、O(N * M) よりも優れた方法はありません。これで完了です。

(場合によっては、イテレータ変換の観点から考えると、どちらの方法でもパフォーマンスに大きな変化がなく、物事をより単純にすることができます。たとえばa、、、、aおよびこれを隣接する 2 次元ノネットに拡張することができます.しかし、この場合、明示的なイテレータと行列の明示的なループを記述することは、コードをより複雑にするだけだと思います.)a[1:]a[2:]neighborsfor

ただし、実際には、さまざまな方法で大幅に高速化できます。例えば：

  • を使用numpyすると、桁違いに高速になる場合があります。タイトなループを反復して単純な演算を行う場合、これは Python が特に遅いことの 1 つであり、numpy代わりに C (または Fortran) で実行できます。
  • お気に入りの GPGPU ライブラリを使用して、操作を明示的にベクトル化できます。
  • を使用multiprocessingすると、マトリックスを断片に分割し、複数の断片を別々のコア (または別々のマシン) で並行して実行できます。

もちろん、単一の 4x6 マトリックスの場合、これらのどれも実行する価値はありません…おそらく を除いてnumpy、マトリックス/ブロードキャストの用語で操作を自然に表現できる限り、コードがより単純で高速になる可能性があります。

実際、そのように物事を簡単に表現できない場合でも、行列を格納numpyするために使用するだけで、物事が少し簡単になる可能性があります (それが重要な場合は、メモリを節約できます)。たとえば、行列から 1 つの列に自然にアクセスできるようにすることができますが、純粋な Python では.numpy[row[col] for row in matrix]

では、どのようにこれに取り組みますnumpyか?

まず、さらに先に進む前に、 numpy.matrixand ufunc(または、より高度なチュートリアルですが、お勧めするものはありません) を読み直してください。

とにかく、それは隣人の各セットで何をしているかによって異なりますが、基本的なアイデアが 3 つあります。

まず、操作を単純な行列演算に変換できれば、それが常に最も簡単です。

そうでない場合は、行列を各方向にシフトするだけで 8 つの「隣接行列」を作成し、各隣接に対して簡単な操作を実行できます。場合によっては、外側の縁に適切な「空の」値 (通常は 0 または nan) を持つ N+2 x N+2 行列から始める方が簡単な場合があります。または、行列をシフトして空の値を入力することもできます。または、一部の操作では、同じサイズのマトリックスは必要ないため、マトリックスをトリミングして隣接するマトリックスを作成できます。それは本当にあなたがしたい操作に依存します。

たとえば、入力をGame of Lifeの固定 6x4 ボードとして使用すると、次のようになります。

def neighbors(matrix):
    for i in -1, 0, 1:
        for j in -1, 0, 1:
            if i == 0 and j == 0: continue
            yield np.roll(np.roll(matrix, i, 0), j, 1)

matrix = np.matrix([[0,0,0,0,0,0,0,0],
                    [0,0,1,1,1,0,1,0],
                    [0,1,1,1,0,0,1,0],
                    [0,1,1,0,0,0,1,0],
                    [0,1,1,1,1,1,1,0],
                    [0,0,0,0,0,0,0,0]])
while True:
    livecount = sum(neighbors(matrix))
    matrix = (matrix & (livecount==2)) | (livecount==3)

(これはこの問題を解決するための最良の方法ではないことに注意してください。しかし、比較的理解しやすく、実際の問題が何であれ明らかになる可能性が高いと思います。)

于 2013-05-13T19:58:03.940 に答える