Как оптимизировать код, который находит максимальную сумму элементов внутри подпрямоугольника (непрерывного блока) 2D-массива?
У меня есть рабочий код, который находит максимальную сумму элементов внутри прямоугольника двумерного массива. Мне интересно, есть ли какие-либо методы оптимизации, которые я мог бы использовать для улучшения его производительности.
Входные данные
- поле: 2D-массив
- fieldRow: размер массива в измерении X
- fieldCol: размер массива в измерении Y
- window_size: размер окна
Выход
- максимальная сумма элементов внутри прямоугольника
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
//TODO if max_sum already found in this windows size
int main()
{ int max_sum = INT_MIN;
int loopCount = 0; // for performance checking
//INPUT for 2D array field
int field[4][5] = {
{0, -5, 3, 4, 9},
{10, 21, 18, -11, 0},
{0, -2, 5, 9, 11},
{12, 7, 8, 3, -1}};
int fieldCol = 5; // INPUT for Y dimension of field
int fieldRow = 4; // INPUT for X simension of field
int window_size = 6; // INPUT for the maximum area of subrectangle
//output 0 and exit program for window_size 0
if (window_size <= 0)
{
printf("0");
exit(0);
}
// incase of window_size larger than area of field
int max_area = (fieldCol * fieldRow);
if (window_size > max_area)
{
window_size = max_area;
}
for (int X = 0; X < fieldRow; X++) // start position of x
{
for (int Y = 0; Y < fieldCol; Y++) // start position of y
{
for (int x = X; x < fieldRow; x++) // end position of x
{
for (int y = Y; y < fieldCol; y++) // end position of y
{
int sum = 0;
int count = 0;
//sum of all elements from starting(X,Y) to ending(x,y) position
for (int c_x = X; c_x <= x; c_x++)
{
for (int c_y = Y; c_y <= y; c_y++)
{
loopCount++; //benchmarking
sum += field[c_x][c_y];
count++; //count for subrectangle area
if (count>window_size){
break;
}
}
}
//set max_sum incase of the area of subrectangle is lower or equal to window_size
if (sum > max_sum && count <= window_size)
{
max_sum = sum;
}
}
}
}
}
printf("%d", max_sum);
printf("\nloop count %d", loopCount);
return 0;
}
Вы сэкономите около 10% итераций, когда выйдете из c_x, когда count достигнет window_size.
Если вы используете «скользящее окно», вы можете исключить множество сумм...
МММ спасибо! @мч. Это действительно сэкономит много времени.
Я подозреваю, что об этом уже спрашивали в Stack Overflow, но на данный момент я не нашел дубликата. Решение O(n^3) здесь.
Я почти уверен, что вы могли бы хранить двумерные совокупные суммы в строках и столбцах, как и для одномерного решения.
Этот вопрос похож на: Максимальный подмассив размером HxW в двумерной матрице. Если вы считаете, что это другое, отредактируйте вопрос, поясните, чем он отличается и/или как ответы на этот вопрос не помогают решить вашу проблему.
@SomeDude Размеры этого подпрямоугольника не фиксированы. Это делает вопрос совсем другим и, очевидно, более сложным.
Ответы 2
Алгоритм можно оптимизировать, сохраняя двумерный массив совокупных сумм. Для эффективности включите начальную строку, содержащую все нули, и начальный столбец, содержащий все нули, и заполните остальные элементы массива, как описано ниже:
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+
| 0 | | | | | |
+---+---+---+---+---+---+
| 0 | | | | | |
+---+---+---+---+---+---+
| 0 | | | | A | B |
+---+---+---+---+---+---+
| 0 | | | | C | X |
+---+---+---+---+---+---+
В приведенном выше примере начальная строка и столбец были установлены на все нули, A, B и C, содержат сумму элементов подпрямоугольника от верхнего левого угла до элемента включительно. Чтобы заполнить элемент X, обратите внимание, что B содержит сумму всех элементов над ним, C содержит сумму всех элементов слева от него, а A содержит сумму всех элементов, которые находятся как над ним, так и слева от него. . Таким образом, совокупная сумма на данный момент равна B + C - A, а значение X — это совокупная сумма плюс входное значение, которое должно быть добавлено к совокупной сумме (B + C - A + input).
Данный входной массив и его массив совокупных сумм показаны ниже:
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | -5| 3 | 4 | 9 | | 0 | 0 | -5| -2| 2 | 11|
+---+---+---+---+---+ +---+---+---+---+---+---+
| 10| 21| 18|-11| 0 | | 0 | 10| 26| 47| 40| 49|
+---+---+---+---+---+ +---+---+---+---+---+---+
| 0 | -2| 5 | 9 | 11| | 0 | 10| 24| 50| 52| 72|
+---+---+---+---+---+ +---+---+---+---+---+---+
| 12| 7 | 8 | 3 | -1| | 0 | 22| 43| 77| 82|101|
+---+---+---+---+---+ +---+---+---+---+---+---+
INPUT CUMULATIVE SUMS
Сумму элементов любого подпрямоугольника можно найти с помощью небольшой арифметики:
· · +------------+ +------+ · +------------+ +------+ ·
| | | | | | | |
| | | | | | | |
· +-----+ = | | - | | · - +------------+ + +------+ ·
| | | | | |
| | | | | |
· +-----+ +------------+ +------+ · · · · · · ·
Другими словами, сумма элементов подпрямоугольника равна сумме элементов до правого нижнего угла подпрямоугольника минус сумма элементов слева от подпрямоугольника минус сумма элементов над подпрямоугольником плюс сумма элементов, которые являются одновременно слева и над подпрямоугольником.
Например:
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | | | | | | | 26| | 40| |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | 5 | 9 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | 8 | 3 | | | | | 43| | 82| |
+---+---+---+---+---+ +---+---+---+---+---+---+
INPUT CUMULATIVE SUMS
5 + 9 + 8 + 3 = 25 82 - 43 - 40 + 26 = 25
Следующий модифицированный код вычисляет двумерный массив совокупных сумм на основе входных данных и использует его при поиске максимальной суммы подпрямоугольника для всех подпрямоугольников, не превышающих размер окна.
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
//TODO if max_sum already found in this windows size
int main()
{ int max_sum = INT_MIN;
int loopCount = 0; // for performance checking
//INPUT for 2D array field
int field[4][5] = {
{0, -5, 3, 4, 9},
{10, 21, 18, -11, 0},
{0, -2, 5, 9, 11},
{12, 7, 8, 3, -1}};
int fieldCol = 5; // INPUT for Y dimension of field
int fieldRow = 4; // INPUT for X dimension of field
int window_size = 6; // INPUT for the maximum area of subrectangle
int sums[fieldRow + 1][fieldCol + 1];
//output 0 and exit program for window_size 0
if (window_size <= 0)
{
printf("0");
exit(0);
}
// Fill in cumulative sums array
for (int Y = 0; Y <= fieldCol; Y++)
{
loopCount++; //benchmarking
sums[0][Y] = 0;
}
for (int X = 1; X <= fieldRow; X++)
{
loopCount++; //benchmarking
sums[X][0] = 0;
for (int Y = 1; Y <= fieldCol; Y++)
{
loopCount++; //benchmarking
sums[X][Y] = sums[X - 1][Y] - sums[X - 1][Y - 1] +
sums[X][Y - 1] + field[X - 1][Y - 1];
}
}
for (int X = 0; X < fieldRow; X++) // start position of x - 1
{
for (int Y = 0; Y < fieldCol; Y++) // start position of y - 1
{
for (int x = X + 1; x <= fieldRow; x++) // end position of x
{
int height = x - X;
int area = 0;
if (height > window_size)
{
// area of width 1 subrectangle is too large
break;
}
for (int y = Y + 1; y <= fieldCol; y++) // end position of y
{
int sum;
loopCount++; //benchmarking
area += height;
if (area > window_size)
{
// area of subrectangle is too large
break;
}
//sum of all elements from starting(X+1,Y+1) to ending(x,y) position
sum = sums[x][y] - sums[X][y] + sums[X][Y] - sums[x][Y];
//set max_sum incase of the area of subrectangle is lower or equal to window_size
if (sum > max_sum)
{
max_sum = sum;
}
}
}
}
}
printf("%d\n", max_sum);
printf("loop count %d\n", loopCount);
return 0;
}
Выход:
57
loop count 165
Приведенное выше количество циклов включает построение массива sums из массива field. Если значения входных элементов считываются из внешнего потока, нет необходимости хранить их в массиве field, поскольку их можно считывать на лету во время создания массива sums.
Это расположение подпрямоугольника размером не больше 6 с максимальной суммой элементов:
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | | | | | | | 0 | | -2| | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | 21| 18| | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | -2| 5 | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+---+
| | 7 | 8 | | | | | 22| | 77| | |
+---+---+---+---+---+ +---+---+---+---+---+---+
INPUT CUMULATIVE SUMS
21 + 18 +
(-2) + 5 +
7 + 8 = 57 77 - 22 - (-2) + 0 = 57
Попробуйте все пары горизонтальных (или вертикальных) границ O(N^2) матрицы (которые фиксируют размер одного измерения подматрицы). Затем запустите любой алгоритм суммы линейного максимального подмассива по другому измерению.
Алгоритм Кадане может быть применен для дополнительного пространства O (1). Альтернативно, решение суммы префикса может использоваться для вариантов задачи, таких как максимальная сумма подматрицы, которая делится на некоторое число.
Общая временная сложность равна O(N^3).
Код могу выложить позже.
Я полагаю, что какой-нибудь гуру математики мог бы придумать что-то вроде «градиентного спуска», чтобы определить, куда следует смотреть. Но минимальное количество сравнений на самом деле не является хорошим показателем производительности, поскольку все зависит от того, в какой системе окажется этот код. Кэш-память будет иметь значение, если она есть.