Ускорение вычислений с использованием векторов в C ++ с использованием указателей / ссылок

Question

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

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

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

Я использовал использование ЦП для отслеживанияна 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().

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

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

Answer 1

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

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

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

Answer 2

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

То же самое с bool SudokuSolver::isUnique(vector<int> v, int n) { против bool SudokuSolver::isUnique(const vector<int>& 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;
}

если это не мешает вашей реализации.