Оптимизировать код методов Java

118

25 декабря 2019, 15:30

Есть такая задача: найти максимальную последовательность единиц в матрице. Последовательность может быть как горизонтальной так и вертикальной. Написал код, который работает, но он выглядит слишком нелепым. Также смущает практически идентичный код в методах "seqRow" и "seqCol".

Дайте пару советов, ка можно улучшить данный пример

public class Task {
public static void main(String[] args) {
    int[][] a =  createMatrix();
    int lengthRow = seqRow(a);
    int lengthCol = seqCol(a);
    System.out.println(lengthCol > lengthRow ? lengthCol : lengthRow);
}
private static int[][] createMatrix() {
    int row = (int) (Math.random()*5+2);
    int col = (int) (Math.random()*5+2);
    int[][] matrix = new int[row][col];
    fillArray(matrix);
    return matrix;
}
private static int[][] fillArray(int[][] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[0].length; j++) {
            array[i][j] = (int) (Math.random()*2);
            System.out.print(array[i][j] + "\t");
        }
        System.out.println();
    }
    return array;
}
private static int seqRow(int[][] a) {
    int max = 0;
    for (int i = 0; i < a.length; i++) {
        int count = 0;
        for (int j = 0; j < a[0].length; j++) {
            if (a[i][j] == 1) {
                count++;
                max = max < count ? count : max;
            } else {
                count = 0;
            }
        }
    }
    return max;
}
private static int seqCol(int[][] a) {
    int max2 = 0;
    for (int i = 0; i < a[0].length; i++) {
        int count2 = 0;
        for (int k = 0; k < a.length; k++) {
            if (a[k][i] == 1) {
                count2++;
                max2 = max2 < count2 ? count2 : max2;
            } else {
                count2 = 0;
            }
        }
    }
    return max2;
}

}

Answer 1

Код не кажется мне таким уж нелепым. Код выполняет простую задачу и хорошо читается. Отдельные моменты можно улучшить, но я бы не сказал, что код остро нуждается в рефакторинге/оптимизации.

Math.random

Первое, что бросилось в глаза это шаблон Math.random()*x + y для генерации числа из [x; x+y). Для этих целей и удобнее и надежнее использовать Random.nextInt:

int row = random.nextInt(5)+2;
int col = random.nextInt(5)+2;
//также можно объявить константы MIN_SIZE = 5, MAX_SIZE = 7 вместо магических цифр

Math.max

Math.max субъективно кажется мне более читаемым нежели тернарный оператор:

max = Math.max(max, count);

и наоборот, тернарный оператор подойдет для обработки простых операций по условию (обновление счетчика).

Названия

Теперь перейдем к методам: переминуем сами методы, приведем названия переменных к общему виду, дадим говорящие названия счетчикам. Получим несколько более компактный код вроде:

private static int findInRows(int[][] a) {
    int max = 0;
    for (int row = 0; row < a.length; row++) {
        int count = 0;
        for (int column = 0; column < a[0].length; column++) {
            count = a[row][column] == 0 ? 0 : count + 1;
            max = Math.max(max, count);
        }
    }
    return max;
}
private static int findInColumns(int[][] a) {
    int max = 0;
    for (int column = 0; column < a[0].length; column++) {
        int count = 0;
        for (int row = 0; row < a.length; row++) {
            count = a[row][column] == 0 ? 0 : count + 1;
            max = Math.max(max, count);
        }
    }
    return max;
}

Часть кода в методах совпадает, но не стоит напрямую «выносить» дублирующиеся куски, т.к. это может повредить компактности и удобочитаемости кода.

Динамическое программирование

Можно пересмотреть подход и объявить два новых массива такой же размерности как a, которые будут использоваться исключительно для предварительных расчетов:

в массиве horizontal[i][j] будет рассчитываться длина последовательности единиц в строке i, которая заканчивается элементом a[i][j] (0 если элемент равен 0);
в массиве vertical[i][j] будет рассчитываться длина последовательности единиц в столбце j, которая заканчивается элементом a[i][j] (0 если элемент равен 0).

Рассчитывать эти значения можно на основе предыдущих. Например, horizontal[row][column]:

если a[row][column] = 0 равно 0;
в противном случае (единица) если column=0 (в первом столбце) равно 1;
в противном случае равно horizontal[row][column-1]+1 (увеличивается значение предыдущего столбца).

Массивы потребуют дополнительной памяти, но для данных размеров массива это не должно быть критично. horizontal и vertical можно рассчитывать во время одного прохода, что позволит использовать один метод:

private static int findTheLongestSequence(int[][] a) {
    int rowsCount = a.length;
    int columnsCount = a[0].length;
    int[][] horizontal = new int[rowsCount][columnsCount];
    int[][] vertical = new int[rowsCount][columnsCount];
    int max = 0;
    for(int row = 0; row<rowsCount; row++) {
        for(int column=0; column<columnsCount; column++) {
            if(a[row][column]==1) {
                horizontal[row][column] = column==0 ? 1 : horizontal[row][column-1] + 1;
                vertical[row][column] = row==0  ? 1 : vertical[row-1][column] + 1;  
                max = Math.max(max, Math.max(horizontal[row][column], vertical[row][column]));
            } //т.к. по умолчанию массив содержит нули, то обнулять значения не нужно
        }
    }
    return max;
}

Проще ли этот код оригинального — решать Вам. Мне первый вариант нравится больше.

В качестве упражнения можно вынести всю задачу расчета последовательности в отдельный класс, который будет занимается одной задачей — получать массив и вести в нем поиск. Такой класс можно будет тестировать отдельно от остального кода (генерации и распечатки массива).

Также рекомендую почитать про шаблон «Итератор», который используется для гибко настраиваемого обхода коллекции. Для текущей задачи писать свой итератор — перебор, но шаблон может пригодиться если потребуется универсальный метод обхода.