Python – сравнение элементов списка с элементами «соседа»

Это может быть скорее «подход» или концептуальный вопрос.

В принципе, у меня есть 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] , мне нужно знать значение my_list[0][1] , my_list[1][0] и my_list[1][1] . Значение «окружающих» элементов определит, как должен работать текущий элемент. Разумеется, для элемента в сердце массива потребуется 8 сравнений.

Теперь я знаю, что могу просто перебирать массив и сравнивать с индексированными значениями, как указано выше. Мне было любопытно, был ли более эффективный способ ограничения количества итераций? Должен ли я проходить через массив как есть, или перебирать и сравнивать только значения с каждой стороны, а затем транспонировать массив и запускать его снова. Это, однако, игнорирует эти значения для диагонали. И должен ли я хранить результаты поиска элементов, поэтому я не буду постоянно определять значение одного и того же элемента?

Я подозреваю, что это может иметь фундаментальный подход в области компьютерных наук, и я очень хочу получить обратную связь о наилучшем подходе, используя Python, а не искать конкретный ответ на мою проблему.

Любая помощь очень ценится.

One Solution collect form web for “Python – сравнение элементов списка с элементами «соседа»”

Вы можете получить более быстрый и, возможно, даже более простой код, используя 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[1:] и a[2:] , и вы можете расширить его до смежных двухмерных нонет. Но я думаю, что в этом случае это просто сделает ваш код более сложным, написав янтарный итератор neighbors и явный for циклов матрица.)


Однако, практически , вы можете получить намного быстрее, по-разному. Например:

  • Используя numpy , вы можете получить порядок или быстрее. Когда вы повторяете жесткий цикл и выполняете простую арифметику, это одна из тех вещей, на которых Python особенно медленна, и numpy может сделать это в C (или Fortran).
  • Используя вашу любимую библиотеку GPGPU, вы можете явно векторизовать свои операции.
  • Используя multiprocessing , вы можете разбить матрицу на кусочки и параллельно выполнять несколько частей на отдельных ядрах (или даже на отдельных машинах).

Конечно, для одной матрицы 4×6 ни один из них не стоит делать … кроме, возможно, для numpy , что может сделать ваш код более простым и быстрым, если вы можете естественным образом выражать свои операции в терминах матрицы / вещания.

На самом деле, даже если вы не можете легко выразить такие вещи, просто используя 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) 

(Обратите внимание, что это не лучший способ решить эту проблему, но я думаю, что это относительно легко понять и, вероятно, осветить всю вашу фактическую проблему.)

  • Сделать список уникальных объектов в Python
  • Преобразование списков
  • Манипуляция списком в Python с pop ()
  • Python объединяет массивы различных размеров, хранящиеся в списке
  • Разделить список на более мелкие списки
  • подпоследовательности массива, которые не равны нулю
  • Фильтровать максимум 20 значений из списка целых чисел
  • Понимание переменных нескольких переменных
  • Лучший pythonic способ заполнить список, содержащий данные типа даты?
  • Создайте пустой список в python с определенным размером
  • Перемеживающие списки в Python
  • Python - лучший язык программирования в мире.