Как оптимизировать алгоритм?

Question

[Андрей Романов]

В проекте на Python, предназначенном для работы с изображениями, есть такой код:

for i in range(1, width - 1):
        for j in range(1, height - 1):
            r = 0
            g = 0
            b = 0
            current_matrix = [[0] * 3 for n in range(3)]

            for k in range(3):
                for m in range(0, 3):
                    for m2 in range(0, 3):
                        current_matrix[m][m2] = pix[i - 1 + m, j - 1 + m2][k]
                if k == 0:
                    r = draw_effects_functions.change_color_effects(l, current_matrix, matrix_type_dict)
                elif k == 1:
                    g = draw_effects_functions.change_color_effects(l, current_matrix, matrix_type_dict)
                elif k == 2:
                    b = draw_effects_functions.change_color_effects(l, current_matrix, matrix_type_dict)

            draw.point((i, j), (r, g, b))

Ссылка на файл с алгоритмом

Ссылка на проект

UPD: Сложность алгоритма, на самом деле, O(n^2).
Можно ли как-либо его упростить?

Comments

[iegor]

N^5? Как посчитали? Я насчитал n^2, не беря в расчёт что делают вызываемые методы

[Андрей Романов]

iegor: Возможно, я ошибся в расчетах, но вот:
В цикл по i вложен цикл по j
В цикл по j вложен цикл по k
В цикле по k - по m, в m - по m2

[Alexander Movchan]

Андрей Романов: k, m и m2 - количество итераций не зависит от входных данных. У вас сложность O(width * height).

[Андрей Романов]

Александр: Ой, точно, спасибо

[Андрей Романов]

Александр: Вы не знаете, можно ли как-либо алгоритм упростить?

[Andy_U]

Если cделаете pix 3-х мерным numpy массивом, то вместо покомпонентного вычислегния матрицы 3x3 можно воспользоваться слайсами и получить что-то типа:

rgb = np.zeros(3)

    for i in range(1, width - 1):
            for j in range(1, height - 1):
                for k in range(3):
                    rgb[k] = draw_effects_functions.change_color_effects(l,  pix[i-1:i+2, j-1:j+2, k], matrix_type_dict)
                
                draw.point((i, j), rgb)

Должно стать чуть быстрее.

[Andy_U]

Не туда...

Answer 1

[Andy_U]

Если cделаете pix 3-х мерным numpy массивом, то вместо покомпонентного вычислегния матрицы 3x3 можно воспользоваться слайсами и получить что-то типа:

rgb = np.zeros(3)

for i in range(1, width - 1):
    for j in range(1, height - 1):
        for k in range(3):
            current_matrix = pix[i-1:i+2, j-1:j+2, k]
            rgb[k] = draw_effects_functions.change_color_effects(l, current_matrix, matrix_type_dict)

        draw.point((i, j), rgb)

Comments

[Andy_U]

Можно еще распараллелить...