Эффективно оценить функцию значений массива _and_ indexices

Question

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

Например,

In [135]: import numpy as np
     ...: A = np.array([[1, 2, 1, 1],
     ...:               [1, 1, 6, 5],
     ...:               [3, 2, 4, 2]])
     ...: print(A)
[[1 2 1 1]
 [1 1 6 5]
 [3 2 4 2]]

Поскольку A [0,1] = 2, для следующих элементов (внизу и справа)>> 2: A [0,2], A [0 , 3], A [1,1].

Точно так же, поскольку A [1,2] = 6, следующие элементы (внизу и справа) должны быть> = 6: A [1, 3], A [2,2], A [2,3].

Мне нужно сделать это для каждого элемента в массиве. Конечный результат:

[[1 2 2 2]
 [1 2 6 6]
 [3 3 6 6]]

Вот код, который работает, но я бы предпочел использовать меньше циклов. Я хотел бы использовать векторные операции или применить функцию set_val ко всем элементам массива A. Я посмотрел на meshgrid и vectorize, но не увидел, как передать индекс массива (т.е. row,col) в функцию.

def set_val(A, cur_row,cur_col,min_val):
    for row_new in range(cur_row,A.shape[0]):
        for col_new in range(cur_col,A.shape[1]):
            if A[row_new,col_new] < min_val:
                A[row_new,col_new] = min_val

A_new = A.copy()

#Iterate over every element of A
for row,row_data in enumerate(A):
    for col,val in enumerate(row_data):
        #Set values to the right and below to be no smaller than the given value
        set_val(A, row, col, val)

print(A_new)                    

Мой вопрос: есть ли более эффективный (или хотя бы более Pythoni c) подход?

Answer 1

Вы можете использовать два кумулятивных максимальных вызова:

from np.mx import maximum as mx

mx.<b>accumulate(</b>mx.<b>accumulate(</b>A<b>)</b>, axis=1<b>)</b>

mx.accumulate вычисляет кумулятивный максимум. Это означает, что для axis=0 значение для B = накапливать (A) таково, что b _ij = max _k≤j a _ик . Для axis=1 то же самое происходит, но по столбцам.

Делая это два раза, мы знаем, что для результата R значение для r _ij будет максимумом r _ij = max _{k≤i, l≤ j} a _kl .

Действительно, если такой самый большой элемент существует в этом под прямоугольнике, то первый mx.accumulate(..) скопирует это значение вправо и, таким образом, в конечном итоге в тот же столбец, что и «цель». Затем следующий mx.accumulate(.., axis=1) скопирует это значение в ту же строку, что и «target», и, таким образом, передаст это значение в правильную ячейку.

Для данного примера ввода мы получим:

>>> A
array([[1, 2, 1, 1],
       [1, 1, 6, 5],
       [3, 2, 4, 2]])
>>> mx.accumulate(mx.accumulate(A), axis=1)
array([[1, 2, 2, 2],
       [1, 2, 6, 6],
       [3, 3, 6, 6]])

Тесты : если мы запустим вышеупомянутый алгоритм для случайной матрицы 1000 × 1000 и повторим эксперимент 100 раз, мы получим следующий тест:

>>> timeit(lambda: mx.accumulate(mx.accumulate(A), axis=1), number=100)
1.5123104000231251

Таким образом, это означает, что он вычисляет одну такую ​​матрицу приблизительно за 151 миллисекунду.