Возврат из нескольких рекурсий
Я делаю решение leetcode 79 C++, где вам нужно найти слово в 2D-матрице. Я делаю это с возвратом
class Solution
{
private:
vector<vector<char>> matrix; //Пример того как можно создать глобальную переменную чтоб не передавать ее каждый раз в аргументах рекурсивной функции
string word;
bool backtrack (int row, int col, int N,
const int num_rows, const int num_cols, const int word_size, vector<vector<bool>>& map_been, bool& result)
{
if (word[N]==matrix[row][col]) //Буква в матрице совпала с текущей буквой word
{
if (N==word_size or result) //Base case: дошли до конца word
return result = true;
//cout<<"Совпала "<<word[N]<<" N = "<<N<<endl;
map_been[row][col] = true;
if (!result and col!=num_cols and map_been[row][col+1]==0) //Идем вправо
backtrack(row, col+1, N+1, num_rows, num_cols, word_size, map_been, result);
if (!result and row!=num_rows and map_been[row+1][col]==0) //Идем вниз
backtrack(row+1, col, N+1, num_rows, num_cols, word_size, map_been, result);
if (!result and col!=0 and map_been[row][col-1]==0) //Идем влево
backtrack(row, col-1, N+1, num_rows, num_cols, word_size, map_been, result);
if (!result and row!=0 and map_been[row-1][col]==0) //Идем вверх
backtrack(row-1, col, N+1, num_rows, num_cols, word_size, map_been, result);
map_been[row][col] = false;
}
return result;
}
bool backtrack_v2 (int row, int col, int N, const int num_rows, const int num_cols, const int word_size, vector<vector<bool>>& map_been)
{
if (row<0 or row>num_rows or col<0 or col>num_cols or word[N]!=matrix[row][col] or map_been[row][col]==true)
return false;
if (N==word_size) //Base case: дошли до конца word
return true;
map_been[row][col] = true;
bool result = backtrack_v2(row, col+1, N+1, num_rows, num_cols, word_size, map_been) //Идем вправо
or backtrack_v2(row+1, col, N+1, num_rows, num_cols, word_size, map_been) //Идем вниз
or backtrack_v2(row, col-1, N+1, num_rows, num_cols, word_size, map_been) //Идем влево
or backtrack_v2(row-1, col, N+1, num_rows, num_cols, word_size, map_been); //Идем вверх
map_been[row][col] = false;
return result;
}
public:
bool exist(vector<vector<char>>& matrix, string word)
{
int num_rows = matrix.size();
int num_cols = matrix[0].size();
int word_size = word.size();
vector<vector<bool>> map_been (num_rows, (vector<bool> (num_cols, false))); //Можно еще писать * в саму matrix, чтоб не создавать map_been
bool result=false;
this->matrix = matrix;
this->word = word;
if (word_size> num_rows*num_cols)
return false;
for (int i=0; i<num_rows; i++)
for (int j=0; j<num_cols; j++)
{
//cout<<"i = "<<i<<" j = "<<j<<endl;
//Первый способ - быстрее выходит из большого количества рекурсий при нахождении word//////////////////////////////////////////
if (backtrack(i, j, 0, num_rows-1, num_cols-1, word_size-1, map_been, result))
return true;
//Второй способ - тоже самое через or (больше рекурсий)////////////////////////////////////////////////////////////////////////
/*
if (backtrack_v2(i, j, 0, num_rows-1, num_cols-1, word_size-1, map_been))
return true;
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
return false;
}
};
На каждом шаге рекурсии у меня есть 4 варианта: вверх, влево, вправо или вниз, каждый шаг создает новую рекурсию. Я хочу знать, как завершить все мои рекурсии, когда я найду целое слово (базовый регистр), потому что прямо сейчас, когда я его нахожу, программа продолжает отсчет влево, вправо и т. д.
Мой вопрос заключается в том, как сразу выйти из нескольких рекурсий, если я нашел правильный ответ где-то глубоко в одной из них.
Обновлено: я сделал 2 варианта: 1-й был мой, 2-й предложил molbdnilo. Но первый вариант работает на 20% быстрее (420 мс против 520). Мой новый вопрос: почему :)
Вы задавали этот вопрос на форумах LeetCode? Если да, не могли бы вы дать ссылку на это обсуждение здесь, в своем вопросе. Если нет, то почему?
Я никогда не пробовал многопоточность ни на одном из этих сайтов. Моим первым решением было бы просто использовать многопоточность. Разделите строки на фрагменты, которые передаются потокам, затем каждая строка просматривается до тех пор, пока не будет найдена первая буква слова, а затем создаются новые потоки для просмотра в каждом направлении. Если когда-либо вернется true, мне понадобится способ немедленно выйти, но это не может быть слишком сложно.
Вы говорите, что это медленно, но это не значит, что вы говорите нам, насколько велики ваша доска и слово, верно? То, что современное оборудование может обработать за 0,5 секунды, огромно -> Вы хоть близко к этому? С другой стороны, ваша версия backtrack_v2 выглядит так, будто она неправильно управляет индексами.
Тестовые примеры @Atmo предоставлены сайтом leetcode, они говорят 1 <= m, n <= 6 1 <= word.length <= 15, но я не знаю, сколько тестовых примеров они выполняют (обычно около 100). Вам следует попробовать решить проблемы с лит-кодом, это отличный инструмент, чтобы стать программистом.
@john Джон Спасибо, я отредактировал свой вопрос (функция backtrack_v2), как вы предложили, избавьтесь от результата в аргументах. Но почему оно работает медленнее, чем мое первое решение?
Полезны ли эти сайты или нет – здесь спорное мнение. Вы не делаете очень сильных аргументов, если в коде, который вы придумали, вы пытаетесь прочитать символ word по индексу word.size(), или если вы делаете то же самое для вектора... Разве сайт не сообщает вам об этом? ошибки?
Для справки: я закодировал ваш backtrack_v2, добавил исправления и незначительные изменения и попытался запустить его на сетке 25x25 (т. е. в 17 раз больше символов по сравнению с вашей самой большой доской) и слове длиной 25. Для расчета требуется <1 мс. -> Требуется гораздо больше, чем 100 тестов самого большого размера, чтобы время выполнения достигло 400 мс, не говоря уже о 500 мс для тестов меньшего размера.
Продолжение Но без возможности профилировать ваш код (я полагаю, это невозможно на этих сайтах) или полного списка тестов, чтобы убедиться, что их не 1000 абсурдных размеров, как вы ожидаете, что мы скажем вам, что не так? Это не то, как должна проводиться оптимизация, и в лучшем случае мы сможем использовать только варианты ваших функций, надеясь, что одна из них будет иметь приемлемую производительность. Видите проблему?
Слышали ли вы о longjmp?
Ответы 1
Используйте результат рекурсий и возвращайтесь, как только она будет успешной.
Вы также можете переместить проверки достоверности, чтобы упростить поток, и использовать размеры аргументов вместо их передачи.
Вот другое предложение:
bool backtrack(int row,
int col,
int N,
const vector<vector<char>>& matrix,
const string& word,
vector<vector<bool>>& map_been)
{
if (row < 0 || row >= matrix.size() || col < 0 || col >= matrix[0].size() || N > word.size()) {
return false;
}
if (N == word.size()) {
return true;
}
map_been[row][col] = true;
bool result = backtrack(row-1, col, N+1, matrix, word, map_been)
|| backtrack(row, col+1, N+1, matrix, word, map_been)
|| backtrack(row+1, col, N+1, matrix, word, map_been)
|| backtrack(row, col-1, N+1, matrix, word, map_been);
map_been[row][col] = false;
return result;
Хорошее решение, но в будущем мне придется использовать карту (vector<vector<bool>> map_been) уже используемых ячеек. Как обновить карту примерно понятно, а как ее очистить, если рекурсия в этом случае не удалась?
Я обновил свой вопрос с помощью вектора Map_been, чтобы прояснить мой вопрос выше.
Это требует некоторой реструктуризации. Смотрите обновление.
Спасибо, братан, я получил твое решение.
Еще один вопрос - стоит ли делать глобальные переменные для: word,matrix,num_rows,num_cols,word_size,map_been и задавать их так: this->matrix=matrix; Поэтому вам не нужно каждый раз передавать их рекурсивной функции. Это ускоряет работу программы? В каких случаях следует это делать? Только если переменная не изменяется внутри рекурсии или?
Глобальные переменные ничего не стоят, они требуют затрат и часто вызывают ошибки, которые трудно отследить. Передача примитивов, ссылок и указателей в качестве аргументов на практике ничего не стоит.
Хорошо, но что, если первый возврат (строка-1, столбец, N+1, матрица, слово, Map_been) вернет true, остальные три возврата все равно будут запущены и запустят свои подобратные пути, не так ли?
Вам нужно прочитать о том, как || и && работают в вашей любимой книге по C++. Это должно быть в одной из первых глав.
Да, я в принципе знаю, что если первый операнд истинен, то остальные не следует запускать. Но... Я обновил свой главный вопрос - теперь у него есть мой первоначальный возврат и ваш backtrack_v2. Ваш литкод на 20% медленнее, не могли бы вы объяснить почему?
Нет, но ваш исходный код имеет неопределенное поведение из-за индексации за пределами границ, так что это довольно бессмысленное сравнение.
Только что проверил - работает, сначала возврат 430 мс против вашего варианта 520 мс В любом случае, спасибо за ваши ответы
Чтобы остановить рекурсию, нужно обратить внимание на возвращаемое значение. Вы возвращаете true, когда находите совпадение, но никогда не используете это значение для остановки рекурсивных вызовов. Кстати, я думаю, вам будет проще писать код, если вы перестанете передавать
resultв функцию. Это значение, которое вы возвращаете из функции, поэтому просто используйте возвращаемое значение функции и отбросьте этот параметр.