Как можно увеличить скорость программы?

Question

Код в самом внизу.

У меня есть матрица размером n x m. В ней нужно найти подматрицу наибольшей площади состоящих из отрицательных чисел. Программа выводит координаты верхнего левого угла подматрицы и правого нижнего угла подматрицы. Например, у меня матрица

 1 -9 -2   8   6  1
 8 -1 -11 -7   6  4
10 12 -1  -9 -12 14
 8 10 -3  -5  17  8
 6  4 10 -13 -16 19

и вывод

1 2
3 3

Код работает, но для матриц гигантских размеров, код работает слишком медленно. Хотелось бы, чтобы программа считала за O(n*log(n)) или O(n^2) (n - это количество элементов в матрице.

def check_matrix(matrix, i0, j0, size_x, size_y):
    for j in range(j0, j0 + size_y):
        for i in range(i0, i0 + size_x):
            if matrix[j][i] >= 0:
                return False
    return True



def main():
    f = open("matrix.txt", "r")
    matrix=[]
    for line in f:
        matrix.append(list(map(int, line.split())))

    size_max, data = 0, (-1, -1, 0, 0)

    for j in range(len(matrix)-1):
        for i in range(len(matrix[j])-1):
            if matrix[j][i] < 0:
                for size_y in range(1, len(matrix) - j):
                    for size_x in range(1, len(matrix[j]) - i):
                        if check_matrix(matrix, i, j, size_x, size_y):
                            if size_max < size_x * size_y:
                                size_max = size_x * size_y
                                data = j, i, i+size_x-1,j+size_y-1

    print(data[0], data[1])
    print(data[2], data[3])

main()

Answer 1

можно вот так оптимизировать:

основная идея - мы сразу проверяем подматрицу на неотрицательные числа и если такие числа в подматрице попадаются, мы перестаём рассматривать подматрицы большего размера

данный подход также позволяет избавиться от функции check_matrix

size_max, data = 0, (-1, -1, 0, 0)

for j in range(len(matrix) - 1):
    for i in range(len(matrix[j]) - 1):
        if matrix[j][i] < 0:
            for size_y in range(1, len(matrix) - j):
                if matrix[j + size_y][i] >= 0:
                    break

                for size_x in range(1, len(matrix[j]) - i):

                    if matrix[j + size_y][i + size_x] >= 0:
                        break

                    square = size_x * size_y

                    if size_max < square:
                        size_max = square
                        data = i, j, j + size_x, size_y

print(data[1], data[0])
print(data[2], data[3])

проверял на случайной матрице 1000x1000

Еще в несколько раз можно ускорить, если минимальный размер подматрицы (длину) выбирать исходя из максимальной площади:

for j in range(len(matrix) - 1):
    for i in range(len(matrix[j]) - 1):
        for size_y in range(1, len(matrix) - j):
            if matrix[j + size_y][i] >= 0:
                break

            for size_x in range(size_max // size_y, len(matrix[j]) - i): # оптимизация тут

                if matrix[j + size_y][i + size_x] >= 0:
                    break

                square = size_x * size_y

                if size_max < square:
                    size_max = square
                    data = i, j, j + size_x, size_y

Answer 2

Код в вопросе работает за O((n*m)**3). Могу предложить простое решение за O((n*m)**2):

Составляем матрицу того же размера с 1 в ячейке, если соответствующее число отрицательно и 0 если нет.
Эту матрицу пересчитываем в матрицу частичных сумм (в принципе, можно сделать сразу на первом шаге).
Теперь чтобы проверить, что матрица заданная углами l,t,r,b содержит только отрицательные числа, достаточно проверить, что сумма по ней равна её площади. Cумма считается в два вычитания и сложение примерно так: s[b,r] - s[b,l] - s[t,r] + s[t,l], тольно надо подогнать сдвиги на 1 в зависимости от того, считаются границы включительно или нет и есть ли защитная рамка для предотвращения выхода за пределы матрицы.

Насчёт потенциальных дальнейших оптимизаций: модно попытаться применить метод сканирующей прямой и сближения left и right за счёт увеличения bottom при фиксированном top. Но я не очень понимаю, как это применить.

Answer 3

Метод с линейным временем O(nm), требует использования непростого в понимании субалгоритма.

Заводим новую матрицу, или, если не жалко, работаем внутри имеющейся. Обходим матрицу по строкам, положительные числа заменяем на 0, отрицательные на 1+значение в верхней ячейке. Таким образом, в каждой ячейке получаем высоту столбика от текущей ячейки до верхнего нуля.

А для задачи нахождения максимальной площади под столбиками ("под гистограммой")

есть хитрый алгоритм на основе (мотононного) стека.

Применив его к каждой строке матрицы, получим максимальную площадь.

Полный код с площадью и позицией:

A = [[ 1, -9, -2,   8,   6 , 1],
     [8, -1, -11, -7,   6,  4],
     [10, 12, -1,  -9, -12, 14],
     [8, 10, -3,  -5,  17,  8],
     [6,  4, 10, -13, -16, 19]]

def maxAreaInHist(arr):
    best = 0
    bstart = 0
    blen = 0
    bhgt = 0
    stack = []
    for i in range(len(arr)):
        while (len(stack) > 0) and (arr[stack[-1]] >= arr[i]):
        #нашли меньший столбик, удаляем все бОльшие
            smallest = arr[stack.pop()]
            if len(stack) == 0:
                start = 0
            else:
                start = stack[-1]+ 1
            #range_length * smallest_weight_in_range
            ar = smallest * (i - start)
            if ar > best:
                best = ar
                bstart = start
                blen = i - start
                bhgt = smallest
        stack.append(i)
    return best, bstart, blen, bhgt

def maxar(A):
    r = len(A)
    c = len(A[0])
    for i in range(c):
        A[0][i] = 1 if A[0][i] < 0 else 0
    for y in range(1, r):
       for i in range(c):
           A[y][i] = 1 + A[y-1][i] if A[y][i] < 0 else 0
    maxarea = 0
    for y in range(r):
        best, bstart, blen, bhgt = maxAreaInHist(A[y])
        if best > maxarea:
            maxarea = best
            y0, x0, y1, x1 = y - bhgt + 1, bstart, y, bstart + blen - 1
    print(maxarea, y0, x0, y1, x1)

maxar(A)

>>6 1 2 3 3

БЛОГ НА HUSL

Как можно увеличить скорость программы?

Ответы (3 шт):