Блог

В настоящее время я создаю программу на C , которая решает судоку. Чтобы сделать это, я часто вычисляю «энергию» судоку (количество ошибок). К сожалению, это вычисление занимает много вычислительного времени. Я думаю, что это можно значительно ускорить, используя указатели и ссылки в вычислении, но мне трудно понять, как это реализовать.

В моем классе solver у меня есть vector<vector<int> элемент данных с именем _sudoku , который содержит значения каждого сайта. В настоящее время при вычислении энергии я вызываю множество функций с передачей по значению. Я попытался добавить amp; в аргументы функций и a * при создании переменных, но это не сработало. Как я могу ускорить работу этой программы, используя передачу по ссылке?

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

Я использовал загрузку процессора, чтобы отследить 80% времени вычисления до функции, в которой вызываются векторы.

 int SudokuSolver::calculateEnergy() {
    int energy = 243 - (rowUniques()   colUniques()   blockUniques());//count number as faults
    return energy;
}


int SudokuSolver::colUniques() {
    int count = 0;
    for (int col = 0; col < _dim; col  ) {
        vector<int> colVec = _sudoku[col];
        for (int i = 1; i <= _dim; i  ) {
            if (isUnique(colVec, i)) {
                count  ;
            }
        }
    }
    return count;
}
int SudokuSolver::rowUniques() {
    int count = 0;
    for (int row = 0; row < _dim; row  ) {

        vector<int> rowVec(_dim);
        for (int i = 0; i < _dim; i  ) {
            rowVec[i] = _sudoku[i][row];
        }
        for (int i = 1; i <= _dim; i  ) {
            if (isUnique(rowVec, i)) {
                count  ;
            }
        }
    }
    return count;
}

int SudokuSolver::blockUniques() {
    int count = 0;
    for (int nBlock = 0; nBlock < _dim; nBlock  ) {
        vector<int> blockVec = blockMaker(nBlock);
        for (int i = 1; i <= _dim; i  ) {
            if (isUnique(blockVec, i)) {
                count  ;
            }
        }
    }
    return count;
}

vector<int> SudokuSolver::blockMaker(int No) {
    vector<int> block(_dim);
    int xmin = 3 * (No % 3);
    int ymin = 3 * (No / 3);
    int col, row;
    for (int i = 0; i < _dim; i  ) {
        col = xmin   (i % 3);
        row = ymin   (i / 3);
        block[i] = _sudoku[col][row];
    }
    return block;
}

bool SudokuSolver::isUnique(vector<int> v, int n) {
    int count = 0;
    for (int i = 0; i < _dim; i  ) {
        if (v[i] == n) {
            count  ;
        }
    }
    if (count == 1) {
        return true;
    } else {
        return false;
    }
}
  

Конкретные строки, которые требуют много времени на вычисления, — это такие:
vector<int> colVec = _sudoku[col];
и каждый раз, когда isUnique() вызывается.

Я ожидаю, что если я переключусь на использование передачи по ссылке, мой код значительно ускорится. Может ли кто-нибудь помочь мне в этом, если это действительно так?

Заранее спасибо.

Если вы измените свой SudokuSolver::isUnique на take vector<int> amp;v , это единственное изменение, которое вам нужно сделать, чтобы передать по ссылке вместо передачи по значению. Передача с помощью указателя будет аналогична передаче по ссылке, с той разницей, что указатели могут быть переназначены или иметь значение NULL, в то время как ссылки не могут.

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

Надеюсь, это поможет!

vector<int> colVec = _sudoku[col]; копирует / переносит все элементы, в то время как const vector<int>amp; colVec = _sudoku[col]; не будет (он создает псевдоним только для правой части).

То же самое с bool SudokuSolver::isUnique(vector<int> v, int n) { по сравнению bool SudokuSolver::isUnique(const vector<int>amp; v, int n) {

Отредактировано по предложению Йеспера Юла: const Добавление гарантирует, что вы не измените содержимое ссылки по ошибке.

Редактировать 2: Еще одна вещь, на которую следует обратить внимание, это то, что vector<int> rowVec(_dim); эти векторы непрерывно распределяются и нераспределяются на каждой итерации, что может стать дорогостоящим. Вы могли бы попробовать что-то вроде

 int SudokuSolver::rowUniques() {
    int count = 0;
    vector<int> rowVec(_maximumDim); // Specify maximum dimension       
    for (int row = 0; row < _dim; row  ) {
        for (int i = 0; i < _dim; i  ) {
            rowVec[i] = _sudoku[i][row];
        }
        for (int i = 1; i <= _dim; i  ) {
            if (isUnique(rowVec, i)) {
                count  ;
            }
        }
    }
    return count;
}
  

если это не испортит вашу реализацию.