Реализация алгоритма C рыцарских туров производительности

Question

Я играл с реализацией алгоритма Knight Tour на Java. Все это время я был полностью уверен, что реализация на C должна быть быстрее. Итак, после прочтения GNU C Reference код будет готов, и логика будет реализована так же, как на Java.

Можете ли вы представить себе мое удивление, когда вариант C занял больше времени для обработки платы 6x6.

Так что мой вопрос в том, как можно оптимизировать приведенный ниже код с технической точки зрения (т. Е. Без эвристической оптимизации).

Некоторые замечания по производительности: на моем ноутбуке i5 с Ubuntu предоставленная реализация заняла более 4 часов для решения платы 6x6. Программа на Java может решить эту задачу за 3 часа 18 минут с помощью однопоточного подхода.

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

EDIT: код, скомпилированный без какой-либо оптимизации, с помощью следующей команды

gcc knight_tour.c -o knight-tour

#include "stdio.h"

#define BOARD_SIZE 5
#define MAX_MOVE_COUNT BOARD_SIZE*BOARD_SIZE

void printBoard(int[][BOARD_SIZE], int);
void clearBoard(int[][BOARD_SIZE], int);
int knight_move(int[][BOARD_SIZE], int, int, int);
int is_valid_position(int, int);
void calc_all_knight_jumps();

static int ALL_KNIGHT_COL_JUMPS[BOARD_SIZE][BOARD_SIZE][9];
static int ALL_KNIGHT_ROW_JUMPS[BOARD_SIZE][BOARD_SIZE][8];

int main() {

    int board[BOARD_SIZE][BOARD_SIZE];
    clearBoard(board, BOARD_SIZE);

    calc_all_knight_jumps();

    int result[BOARD_SIZE][BOARD_SIZE];
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            result[i][j] = knight_move(board, i, j, 1);
        }
    }
    printBoard(result, BOARD_SIZE);

    return 0;
}

int knight_move(int board[][BOARD_SIZE], int cpos, int rpos, int level) {
    if (level == MAX_MOVE_COUNT) return 1;

    board[cpos][rpos] = level;

    int solved_count = 0;
    int jump_count = ALL_KNIGHT_COL_JUMPS[cpos][rpos][8];
    for (int i = 0; i < jump_count; i++) {
        int next_cpos = ALL_KNIGHT_COL_JUMPS[cpos][rpos][i];
        int next_rpos = ALL_KNIGHT_ROW_JUMPS[cpos][rpos][i];

        if (board[next_cpos][next_rpos] == 0) {
            solved_count += knight_move(board, next_cpos, next_rpos, level + 1);
        }
    }

    board[cpos][rpos] = 0;
    return solved_count;
}

void clearBoard(int board[][BOARD_SIZE], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
              board[i][j] = 0;
        }
    }
}

void printBoard(int board[][BOARD_SIZE], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("%8d", board[i][j]);
        }
        printf("\n");
    }
}

int is_valid_position(int cpos, int rpos) {
    if (cpos < 0 || cpos >= BOARD_SIZE) return 0;
    if (rpos < 0 || rpos >= BOARD_SIZE) return 0;

    return 1;
}

void calc_all_knight_jumps() {
    int col_jumps[] = { 1,  2,  2,  1, -1, -2, -2, -1};
    int row_jumps[] = { 2,  1, -1, -2, -2, -1,  1,  2};

    int next_cpos, next_rpos;
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {

            int jump_count = 0;
            for (int k = 0; k < 8; k++) {
                next_cpos = i + col_jumps[k];
                next_rpos = j + row_jumps[k];
                if (is_valid_position(next_cpos, next_rpos) == 1) {
                    ALL_KNIGHT_COL_JUMPS[i][j][jump_count] = next_cpos;
                    ALL_KNIGHT_ROW_JUMPS[i][j][jump_count] = next_rpos;
                    jump_count++;
                }
            }

            ALL_KNIGHT_COL_JUMPS[i][j][8] = jump_count;
        }
    }
}

Answer 1

Учитывая все комментарии, я немного изменил исходный код.

• опробовал опции оптимизации -O2 и -O3 с компилятором gcc;
• уменьшено количество вызовов верхнего уровня для метода knight_move (). так что теперь только уникальные результаты вычисляются и затем отражаются по горизонтали, вертикали и диагонали;
• добавлен код для измерения производительности без использования printf();
• проверил, что варианты C и Java максимально идентичны;

И, наконец, я ожидал результатов - код на C быстрее (но с опциями оптимизации)

• код C с опцией -O2: длительность - 1348 с (22:28)
• Java-код: продолжительность - 1995 с (33:15)
• C-код без оптимизации: длительность - 3518 с (58:38)
• код C с опцией -O3: длительность - 2143 с (35:43)

Вот обе реализации на тот случай, если кого-то заинтересует алгоритм рыцарского тура на C и Java: -)

GNU C

#include "stdio.h"
#include "time.h"

#define BOARD_SIZE 6
#define MAX_MOVE_COUNT BOARD_SIZE*BOARD_SIZE

int knight_move(int[][BOARD_SIZE], int, int, int);
void pre_calc_all_knight_jumps();
void print_result(int[][BOARD_SIZE]);

static int ALL_KNIGHT_COL_JUMPS[BOARD_SIZE][BOARD_SIZE][9];
static int ALL_KNIGHT_ROW_JUMPS[BOARD_SIZE][BOARD_SIZE][8];

int main() {
    // init board
    int board[BOARD_SIZE][BOARD_SIZE];
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            board[i][j] = 0;
        }
    }

    pre_calc_all_knight_jumps();

    int result[BOARD_SIZE][BOARD_SIZE];

    struct timespec s_time, e_time;
    clock_gettime(CLOCK_MONOTONIC, &s_time);

    int border = BOARD_SIZE - 1;
    int center = BOARD_SIZE / 2.0 + 0.5;
    for (int i = 0; i < center; i++) {
        for (int j = i; j < center; j++) {
            int res = knight_move(board, i, j, 1);
            result[i][j] = res;
            result[border - i][j] = res;
            result[i][border - j] = res;
            result[border - i][border - j] = res;
            if (i != j) result[j][i] = res;
        }
    }
    clock_gettime(CLOCK_MONOTONIC, &e_time);
    printf("Duration in seconds: %ld\n", e_time.tv_sec - s_time.tv_sec);

    print_result(result);
    return 0;
}

int knight_move(int board[][BOARD_SIZE], int cpos, int rpos, int level) {
    if (level == MAX_MOVE_COUNT) return 1;

    board[cpos][rpos] = level;

    int solved_count = 0;
    int valid_move_count = ALL_KNIGHT_COL_JUMPS[cpos][rpos][8];
    for (int i = 0; i < valid_move_count; i++) {
        int next_cpos = ALL_KNIGHT_COL_JUMPS[cpos][rpos][i];
        int next_rpos = ALL_KNIGHT_ROW_JUMPS[cpos][rpos][i];

        if (board[next_cpos][next_rpos] == 0) {
            solved_count += knight_move(board, next_cpos, next_rpos, level + 1);
        }
    }

    board[cpos][rpos] = 0;
    return solved_count;
}

void print_result(int board[][BOARD_SIZE]) {
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            printf("%8d", board[i][j]);
        }
        printf("\n");
    }
}

void pre_calc_all_knight_jumps() {
    int col_jumps[] = { 1,  2,  2,  1, -1, -2, -2, -1};
    int row_jumps[] = { 2,  1, -1, -2, -2, -1,  1,  2};

    int next_cpos, next_rpos;
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {

            int jump_count = 0;
            for (int k = 0; k < 8; k++) {
                next_cpos = i + col_jumps[k];
                next_rpos = j + row_jumps[k];
                if (next_cpos < 0 || next_cpos >= BOARD_SIZE) continue;
                if (next_rpos < 0 || next_rpos >= BOARD_SIZE) continue;

                ALL_KNIGHT_COL_JUMPS[i][j][jump_count] = next_cpos;
                ALL_KNIGHT_ROW_JUMPS[i][j][jump_count] = next_rpos;
                jump_count++;
            }

            ALL_KNIGHT_COL_JUMPS[i][j][8] = jump_count;
        }
    }
}

Java

import java.util.Arrays;

public class KnightTour1 {

    private final static int BOARD_SIZE     = 6;
    private final static int MAX_MOVE_COUNT = BOARD_SIZE * BOARD_SIZE;

    private static final int[][][] ALL_KNIGHT_COL_MOVES;
    private static final int[][][] ALL_KNIGHT_ROW_MOVES;

    static {
        final int[] knightColJumps = { 1,  2,  2,  1, -1, -2, -2, -1};
        final int[] knightRowJumps = { 2,  1, -1, -2, -2, -1,  1,  2};

        ALL_KNIGHT_COL_MOVES = new int[BOARD_SIZE][BOARD_SIZE][];
        ALL_KNIGHT_ROW_MOVES = new int[BOARD_SIZE][BOARD_SIZE][];

        int[] tmpColMoves = new int[8];
        int[] tmpRowMoves = new int[8];
        for (int c = 0; c < BOARD_SIZE; c++) {
            for (int r = 0; r < BOARD_SIZE; r++) {
                int jumpCount = 0;
                for (int i = 0; i < 8; i++) {
                    int nextColPos = c + knightColJumps[i];
                    int nextRowPos = r + knightRowJumps[i];
                    if (isValidBoardPos(nextColPos, nextRowPos)) {
                        tmpColMoves[jumpCount] = nextColPos;
                        tmpRowMoves[jumpCount] = nextRowPos;
                        jumpCount++;
                    }
                }

                ALL_KNIGHT_COL_MOVES[c][r] = Arrays.copyOf(tmpColMoves, jumpCount);
                ALL_KNIGHT_ROW_MOVES[c][r] = Arrays.copyOf(tmpRowMoves, jumpCount);
            }
        }
    }

    private static boolean isValidBoardPos(int colPos, int rowPos) {
        return colPos > -1 && colPos < BOARD_SIZE && rowPos > -1 && rowPos < BOARD_SIZE;
    }

    public static void main(String[] args) {
        long sTime = System.currentTimeMillis();
        int[][] result = findNumberOfTours();
        long duration = (System.currentTimeMillis() - sTime) / 1000;

        System.out.println("Duration in seconds: " + duration);
        printResult(result);
    }

    private static int knightMove(int[][] board, int colPos, int rowPos, int level) {
        if (level == MAX_MOVE_COUNT) return 1;

        board[colPos][rowPos] = level;

        final int[] validColMoves = ALL_KNIGHT_COL_MOVES[colPos][rowPos];
        final int[] validRowMoves = ALL_KNIGHT_ROW_MOVES[colPos][rowPos];
        final int validMoveCount = validColMoves.length;

        int solvedTourCount = 0;
        for (int i = 0; i < validMoveCount; i++) {
            final int nextColPos = validColMoves[i];
            final int nextRowPos = validRowMoves[i];
            if (board[nextColPos][nextRowPos] == 0) {
                solvedTourCount += knightMove(board, nextColPos, nextRowPos, level + 1);
            }
        }

        board[colPos][rowPos] = 0;
        return solvedTourCount;
    }

    private static int[][] findNumberOfTours() {
        final int[][] result = new int[BOARD_SIZE][BOARD_SIZE];
        final int[][] board = new int[BOARD_SIZE][BOARD_SIZE];

        final int border = BOARD_SIZE - 1;
        final int center = (int)(BOARD_SIZE / 2f + 0.5);
        for (int i = 0; i < center; i++) {
            for (int j = i; j < center; j++) {
                int res = knightMove(board, i, j, 1);
                result[i][j] = res;
                result[border - i][j] = res;
                result[i][border - j] = res;
                result[border - i][border - j] = res;
                if (i != j) result[j][i] = res;
            }
        }

        return result;
    }

    private static void printResult(int[][] res) {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                System.out.print(String.format("%8d", res[i][j]));
            }
            System.out.println();
        }
    }
}