Вы можете получить более быстрый и, возможно, даже более простой код, используя 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,, и a[2:], и вы можете расширить его до смежных двухмерных нонет. Но я думаю, что в этом случае он просто сделает ваш код более сложным, написав явный итератор neighbors и явную for петли над матрица.)
Однако практически, вы можете получить намного быстрее, различными способами. Например:
- Используя
numpy, вы можете получить заказ или увеличить его. Когда вы повторяете жесткий цикл и выполняете простую арифметику, это одна из тех вещей, в которой Python особенно медленна, и numpy может сделать это в C (или Fortran).
- Используя вашу любимую библиотеку GPGPU, вы можете явно векторизовать свои операции.
- Используя
multiprocessing, вы можете разбить матрицу на части и выполнить несколько частей параллельно на отдельных ядрах (или даже отдельных машинах).
Конечно для одной матрицы 4х6, ни один из них не стоит делать ... кроме, возможно, numpy, что может сделать ваш код проще и быстрее, до тех пор, как вы можете выразить свои операции, естественно, в матрице/трансляции сроки.
В самом деле, даже если вы не можете легко выразить то, что путь, просто используя numpy к магазин матрица может сделать вещи немного проще (и сэкономить память, если это имеет значение). Например, может позволить вам получить доступ к одному столбцу из матрицы, естественно, в чистом Python вам нужно написать что-то вроде [row[col] for row in matrix].
Итак, как бы вы справились с этим с помощью numpy?
Во-первых, вы должны прочитать за numpy.matrix и ufunc (или, лучше, какой-то учебник более высокого уровня, но мне нечего рекомендовать), прежде чем идти слишком много дальше.
В любом случае, это зависит от того, что вы делаете с каждым набором соседей, но есть три основные идеи.
Во-первых, если вы можете преобразовать свою операцию в простую математическую матрицу, это всегда проще всего.
Если нет, вы можете создать 8 "соседних матриц", просто сдвинув матрицу в каждом направлении, а затем выполните простые операции против каждого соседа. В некоторых случаях легче начать с матрицы N + 2 x N + 2 с подходящими «пустыми» значениями (обычно 0 или нан) во внешнем ободе. Кроме того, вы можете переместить матрицу и заполнить пустые значения. Или для некоторых операций вам не нужна матрица одинакового размера, поэтому вы можете просто обрезать матрицу для создания соседа. Это действительно зависит от того, какие операции вы хотите сделать.
Например, принимая свой вклад в виде фиксированной платы 6х4 для Game of Life:
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)
(Обратите внимание, что это не самый лучший способ решить эту проблему, но я думаю, что это относительно легко понять, и, вероятно, осветит, какова ваша фактическая проблема.)
Можете ли вы использовать здесь «numpy»? Потому что это полный набор способов делать подобные матрице операции естественным образом подобным матрице образом (и часто на порядок быстрее, чем чистый Python, для загрузки). – abarnert
В любом случае, насколько алгоритмическая сложность: итерация через матрицу в одном (двухуровневом) проходе при проверке 3-8 окружающих элементов на каждом шаге - это O (N * M), что является лучшим, делать. Итак, в чем проблема? – abarnert
Истинно, но операции с матрицами можно отлично распараллелить на вашем графическом процессоре. Это экономит много времени! –