Преобразование рекурсивного в итеративное - PullRequest
Новая
       42

Преобразование рекурсивного в итеративное

0 голосов
/ 28 октября 2019

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

Мне интересно, есть ли способ преобразовать мой алгоритм в итеративный безиспользуя стек .

Вот что я сделал до сих пор с моей рекурсией. 

    int[][] maze = new int[Integer.valueOf(dimensions[1])]
                         [Integer.valueOf(dimensions[0])];

    int colA = maze[0].length;
    int colB = colA;
    int rowA = 0;
    int rowB = 0;

    for (int i = 0; i < maze.length; i++) {
        String currLine = lines.get(i+1);
        int j = 0;
        for (char c : currLine.toCharArray()) {
            maze[i][j] = c == '*' ? -1 : 0;
            if (c == 'A') {
                maze[i][j] = 1;
                rowA = i;
                colA = j;   
            } else if (c == 'B') {
                maze[i][j] = 2;
                rowB = i;
                colB = j;
            }
            j++;
        }
    }
    return getAllPaths(maze, rowA, colA);
}

private static int getAllPaths(int[][] maze, int i, int j) throws IOException {

    if(maze[i][j] == -1) {
        return 0;
    }

    if(maze[i][j] == 2) {
        return 1;
    }

    return getAllPaths(maze, i+1, j) + getAllPaths(maze, i, j+1);
}

Любые советы или предложения, с которых я должен начать отсюда, чтобы преобразовать это витерация будет принята с благодарностью!

1 Ответ

1 голос
/ 28 октября 2019

Итеративное и рекурсивное не будет иметь заметного различия в производительности.

Вам нужно сделать так, чтобы код запомнил , чтобы вы не делали один и тот же расчет несколько раз.

Для иллюстрации: в матрице 3x5 вы будете ходить так: 

X → X → X → X → X
↓   ↓   ↓   ↓   ↓
X → X → X → X → X
↓   ↓   ↓   ↓   ↓
X → X → X → X → X

Заменив X на количество раз, которое getAllPaths будет вызываться для этой координаты, вы получите: 

1 → 1 → 1 →  1 →  1
↓   ↓   ↓    ↓    ↓
1 → 2 → 3 →  4 →  5
↓   ↓   ↓    ↓    ↓
1 → 3 → 6 → 10 → 15

Как видите, без напоминания координата 4,2 вызывается 15 раз. Это очень плохо для производительности. Если результат был сохранен, он делает рекурсивные вызовы только один раз, вы получите гораздо лучшую производительность.

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

ОБНОВЛЕНИЕ

Цитирование Википедии:

Заметки - это метод оптимизации, используемый в основном для ускорения компьютерных программ с помощьюхранение результатов дорогостоящих вызовов функций и возвращение кэшированного результата при повторном вводе тех же данных.

Итак, вам необходимо кэшировать результаты вызова метода, а это означает, что вам нужен кеш того же самогоРазмер как лабиринт. 

private static int getAllPaths(int[][] maze, int row, int col) {
    int[][] cache = new int[maze.length][maze[0].length];
    for (int i = 0; i < cache.length; i++) {
        Arrays.fill(cache[i], -1);
    }
    return getAllPaths(maze, cache, row, col);
}

private static int getAllPaths(int[][] maze, int[][] cache, int row, int col) {
    // Check cache
    if (cache[row][col] != -1)
        return cache[row][col];

    // Normal logic
    int paths;
    if (maze[row][col] == -1) {
        paths = 0;
    } else if (maze[row][col] == 2) {
        paths = 1;
    } else {
        paths = getAllPaths(maze, cache, row+1, col) + getAllPaths(maze, cache, row, col+1);
    }

    // Save result in cache
    cache[row][col] = paths;

    return paths;
}
...