Оптимизировать эту рекурсивную функцию [Boggle resolver]

Измените свой алгоритм с рекурсивного на итеративный (с циклом). Обычно это быстрее. После этого другие оптимизации связаны с алгоритмом и структурами данных, чтобы уменьшить сложность. Гораздо сложнее найти такие оптимизации (но возможно).

РЕДАКТИРОВАТЬ: некоторые мысли о коде, а затем версия поиска слова, которую я сделал сегодня:

• Вы хотите только английские слова (или итальянские, и т.д …). Чтобы проверить это, вы должны использовать словарь, это наиболее эффективная структура для поиска слов, как с точки зрения памяти и производительности
• комментарий сказал, что этот алгоритм сильно рекурсивный. Я не согласен, я сделал итеративный, с гораздо меньшим количеством копий векторов и проверкой слов. Переход от рекурсивного алгоритма к итеративному обычно уменьшает количество копий. Но я все еще согласен с одним пунктом этого комментария: некоторые алгоритмы могут быть быстрее в рекурсивной форме (но они не так распространены). Кроме того, этот алгоритм было не просто найти;)
• Вы должны разделить свой код. Это будет намного удобочитаемее и проще для оптимизации.
• Вы кодируете ошеломляющий распознаватель, поэтому вам следует помнить, что ваш словарь должен быть точным и содержать все формы глаголов (например, для «быть»: я, есть, есть, было, и т. Д … ). Я проверил это по-французски, потому что список английских слов у меня всего 850 слов, что слишком мало.
• Условия для букв с акцентами в словаре не важны, они здесь просто для того, чтобы не использовать больше слотов для акцентов. Кроме того, я чередовал каждое составленное слово (с кареткой в ​​нем) из текстового файла.
• На моем компьютере загрузка словаря (неисчерпывающие 350000 французских слов, 3 Мб) и поиск всех слов длиной 5,6 и 7 длин занимают примерно 0,6 секунды (i7 2660K, 8 Гб ОЗУ, выпуск с / 0x, измеренный мной, а не на компьютере;)). Измерение производительности будет актуально только для вашей машины, для сравнения.

Итак, вот код. Он автономный, вам просто нужно скомпилировать его, выполнить с английским (или итальянским или французским) файлом слов (текст, одно слово в строке):

#include <string>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <time.h>
#include <map>
#include <algorithm>

// **************************************************** //
//                                                      //
// Data structure for the words : dictionnary           //
//                                                      //
// **************************************************** //
struct DicNode
{
const char l;
bool isEndOfWord;
DicNode* children[26]; // a - z, case insensitive
DicNode* parent;
unsigned int min, max, level;

DicNode(char c, DicNode* p = 0, bool end = false) : l(c),isEndOfWord(end),parent(p),min((unsigned int)(-1)),max(0), level(parent ? parent->level + 1 : 0)
{
for(unsigned int t = 0; t < 26; t++)
children[t] = 0;
}

~DicNode()
{
for(unsigned int t = 0; t < 26; t++)
if(children[t])
delete children[t];
}

DicNode*& at(char l)
{
if(l == 'à' || l == 'ä' || l == 'â')
l = 'a';
if(l == 'é' || l == 'è' || l == 'ê' || l == 'ë')
l = 'e';
if(l == 'ï' || l == 'î')
l = 'i';
if(l == 'ö' || l == 'ô')
l = 'o';
if(l == 'ü' || l == 'û' || l == 'ù')
l = 'u';
if(l == 'ç')
l = 'c';
if(l <= 'Z')
l = 'a' + l - 'A';

// Note: undefined behavior if l > 'Z' or l < 'A'.
return children[(unsigned int)(l - 'a')];
}

bool inRange(unsigned int n) const
{
return n <= max && n >= min;
}

void print(std::string str = "") const
{
// Here recursive algorithm is way better because of the object-oriented structure
if(isEndOfWord)
std::cout << (str + l) << "\n";

for(unsigned int t = 0; t < 26; t++)
if(children[t])
children[t]->print(str + l);
}

std::string toString() const
{
std::string str(level, '0');
const DicNode* node = this;
while(node && node->level > 0)
{
str[node->level - 1] = node->l;
node = node->parent;
}
return str;
}
};

void addWord(DicNode* root, const std::string& str)
{
if(!root || str == "") return;
DicNode* node = root;
unsigned int i = 0;
while(i != str.size())
{
if(str.size() - i > node->max) node->max = str.size() - i;
if(str.size() - i < node->min) node->min = str.size() - i;

char c = tolower(str[i]);
DicNode*& n = node->at(c);
if(!n) n = new DicNode(c,node);
node = n;
i++;
}
node->isEndOfWord = true;
}

// **************************************************** //
//                                                      //
// Data structures for the algorithm                    //
//                                                      //
// **************************************************** //

enum Direction
{
INVALID,
NORTH,
NORTH_EAST,
EAST,
SOUTH_EAST,
SOUTH,
SOUTH_WEST,
WEST,
NORTH_WEST,
FINISHED
};

Direction incDir(Direction d)
{
switch(d)
{
case NORTH:         return NORTH_EAST;
case NORTH_EAST:    return EAST;
case EAST:          return SOUTH_EAST;
case SOUTH_EAST:    return SOUTH;
case SOUTH:         return SOUTH_WEST;
case SOUTH_WEST:    return WEST;
case WEST:          return NORTH_WEST;
case NORTH_WEST:    return NORTH;
default:            return INVALID;
}
}

Direction operator-(Direction d)
{
switch(d)
{
case NORTH:         return SOUTH;
case NORTH_EAST:    return SOUTH_WEST;
case EAST:          return WEST;
case SOUTH_EAST:    return NORTH_WEST;
case SOUTH:         return NORTH;
case SOUTH_WEST:    return NORTH_EAST;
case WEST:          return EAST;
case NORTH_WEST:    return SOUTH_EAST;
default:            return INVALID;
}
}

std::string toString(Direction d)
{
switch(d)
{
case NORTH:         return "NORTH";
case NORTH_EAST:    return "NORTH_EAST";
case EAST:          return "EAST";
case SOUTH_EAST:    return "SOUTH_EAST";
case SOUTH:         return "SOUTH";
case SOUTH_WEST:    return "SOUTH_WEST";
case WEST:          return "WEST";
case NORTH_WEST:    return "NORTH_WEST";
default:            return "INVALID";
}
}

struct Cell
{
char l;
DicNode* node;
Direction dir, dirParent;
Cell(char l_ = 'A') : l(l_),node(0),dir(INVALID),dirParent(INVALID) {}
};

struct ProbLetter
{
char letter;
float proba;
};

class Map
{
public:
Map(unsigned int w, unsigned int h) : width(w), height(h)
{
data = new Cell[width * height];
for(unsigned int t = 0; t < width * height; t++)
data[t] = randomEnglishLetter();
}

static char randomEnglishLetter()
{
// Frequency of english letters
static ProbLetter probas[26] =
{
{ 'Z', 0.074f },
{ 'Q', 0.095f },
{ 'X', 0.150f },
{ 'J', 0.153f },
{ 'K', 0.772f },
{ 'V', 0.978f },
{ 'B', 1.492f },
{ 'P', 1.929f },
{ 'Y', 1.974f },
{ 'G', 2.015f },
{ 'F', 2.228f },
{ 'W', 2.360f },
{ 'M', 2.406f },
{ 'U', 2.758f },
{ 'C', 2.782f },
{ 'L', 4.025f },
{ 'D', 4.253f },
{ 'R', 5.987f },
{ 'H', 6.094f },
{ 'S', 6.327f },
{ 'N', 6.749f },
{ 'I', 6.966f },
{ 'O', 7.507f },
{ 'A', 8.167f },
{ 'T', 9.056f },
{ 'E', 12.702f }
};

// Random number between 0 and 1
float p = 100.0f * float(rand() % 10000) / 9999.0f;
float sum = 0.0f;
for(unsigned int t = 0; t < 26; t++)
{
sum += probas[t].proba;
if(p < sum) return probas[t].letter;
}
return probas[25].letter;
}

Cell& operator()(unsigned int x, unsigned int y)
{
return data[x + y * width];
}

bool inRange(int x, int y)
{
return x >= 0 && x < (int)width && y >= 0 && y < (int)height;
}

void print()
{
for(unsigned int y = 0; y < height; y++)
{
for(unsigned int x = 0; x < width; x++)
std::cout << "  " << data[x + y * width].l;
std::cout << "\n";
}
}

unsigned int getWidth() const { return width; }
unsigned int getHeight() const { return height; }

private:
unsigned int width, height;
Cell* data;
};// **************************************************** //
//                                                      //
// Word-search algorithm                                //
//                                                      //
// **************************************************** //

inline void advance(int& x, int& y, Direction d)
{
switch(d)
{
case NORTH:
y--;
return;
case NORTH_EAST:
x++;
y--;
return;
case EAST:
x++;
return;
case SOUTH_EAST:
x++;
y++;
return;
case SOUTH:
y++;
return;
case SOUTH_WEST:
x--;
y++;
return;
case WEST:
x--;
return;
case NORTH_WEST:
x--;
y--;
return;
default:
return;
}
}

struct Data
{
Map& map;
int x;
int y;
};

bool descend(Data& dat, unsigned int n)
{
DicNode* parent = dat.map(dat.x, dat.y).node;
if(n == parent->level) return false;

Direction dir = dat.map(dat.x, dat.y).dir;
if(dir == FINISHED) return false;
else if(dir == INVALID) dir = NORTH;

int pX = dat.x, pY = dat.y;
bool firstIteration = true;
for(; firstIteration || dir != NORTH; dir = incDir(dir))
{
firstIteration = false;
pX = dat.x;
pY = dat.y;
advance(pX, pY, dir);

if(dat.map.inRange(pX, pY) // (pX, pY) is not outside the map
&& dat.map(pX, pY).node == 0 // The cell is not already used
&& parent->at(dat.map(pX, pY).l) != 0) // An entry in the dictionary exists
{
// We found the next node
dat.map(dat.x, dat.y).dir = dir;
dat.map(pX, pY).node = parent->at(dat.map(pX, pY).l);
dat.map(pX, pY).dirParent = -dir;
dat.x = pX;
dat.y = pY;

return true;
}
}

return false;
}

bool ascend(Data& dat)
{
// Go back on the previous node

Direction dp = dat.map(dat.x, dat.y).dirParent;
if(dp == INVALID) return false;

dat.map(dat.x, dat.y).dir = INVALID;
dat.map(dat.x, dat.y).dirParent = INVALID;
dat.map(dat.x, dat.y).node = 0;
advance(dat.x, dat.y, dp);

dat.map(dat.x, dat.y).dir = incDir(dat.map(dat.x, dat.y).dir);
if(dat.map(dat.x, dat.y).dir == NORTH)
dat.map(dat.x, dat.y).dir = FINISHED;

return true;
}

void findWordsFromPosition(Map& map, DicNode* parent, unsigned int x, unsigned int y, unsigned int n, std::vector<std::string>& output)
{
if(!parent) return;

bool ok = true;

// Setup first node
map(x, y).node = parent;
map(x, y).dir = NORTH;

// while we can find next node with direction
// If marked node has right order and is end of word, or if condition on n is not verified:
//     add it to the output (if condition on n is verified)
//     no need to go further (because of n), so advance direction of parent cell, reset current cell, and go up for the current position
Data dat = { map, x, y };
while(ok)
{
if(map(dat.x,dat.y).node->toString() == "ane")
std::cout << "ok\n";
if(!descend(dat, n))
ok = ascend(dat);
else
{
DicNode* node = dat.map(dat.x, dat.y).node;
if(node->level == n && node->isEndOfWord)
{
std::string str = node->toString();
if(std::find(output.begin(), output.end(), str) == output.end())
output.push_back(str);
ok = ascend(dat);
}
else if(!node->inRange(n - node->level))
ok = ascend(dat);
}
}

// Clean first node
map(x, y).dir = INVALID;
map(x, y).dirParent = INVALID;
map(x, y).node = 0;
}

void getWords(Map& map, DicNode& dic, unsigned int n, std::vector<std::string>& output)
{
if(n > dic.max || n < dic.min) return;

// Search words for every position
for(unsigned int y = 0; y < map.getHeight(); y++)
for(unsigned int x = 0; x < map.getWidth(); x++)
findWordsFromPosition(map,dic.at(map(x,y).l),x,y,n,output);
}

#include <fstream>

int main()
{
srand((unsigned int)time(0));
// Prepare the words, for example, load them from a real dictionary
DicNode dictionary(0);
unsigned int maxSize = 0;

// Note: the following code make sense only if you load words from a file
{
std::ifstream dico("english.txt");
std::string str;
int count = 0;
while(dico >> str)
{
if(str.size() > maxSize) maxSize = str.size();
addWord(&dictionary,str);
count++;
}
std::cout << "Read " << count << " words from dictionary, longest with " << maxSize << " letters.\n";
}

// Prepare the matrix
Map mat(4,4);
/*
mat(0,0) = 'A';
mat(1,0) = 'N';
mat(2,0) = 'F';
mat(3,0) = 'N';
mat(0,1) = 'S';
mat(1,1) = 'L';
mat(2,1) = 'E';
mat(3,1) = 'R';
mat(0,2) = 'G';
mat(1,2) = 'O';
mat(2,2) = 'R';
mat(3,2) = 'R';
mat(0,3) = 'S';
mat(1,3) = 'I';
mat(2,3) = 'U';
mat(3,3) = 'I';
*/
std::cout << "\nMatrix:\n";
mat.print();

// Search words
std::vector<std::string> words;
for(unsigned int t = 5; t <= 7; t++)
getWords(mat,dictionary,t,words);
std::cout << "\nWords:\n";
if(words.size() == 0)
std::cout << " (no words)\n";
else
for(unsigned int t = 0; t < words.size(); t++)
std::cout << " " << words[t] << "\n";
}

Примечание: предыдущий код был решателем поиска кода. Теперь он удален из ответа, но вы все равно можете получить его, выполнив поиск по редакции этого ответа.

EDIT2:
Некоторые устные объяснения

Словарь. Это своего рода Radix-дерево, но у каждого узла есть только одно письмо для хранения. У него может быть до 26 детей (больше, если вы используете акценты и / или цифры), по одному на каждую букву рассматриваемого алфавита. Основная компоновка следующая:

Дерево слов http://img571.imageshack.us/img571/2281/wtree.png

Пример:

Пример словаря http://img706.imageshack.us/img706/1244/wordsr.png

Каждый узел также содержит логическое значение, которое указывает, является ли это концом слова.
Кроме того, каждый узел хранит минимальный и максимальный размер своих дочерних ветвей, своего родителя и своего уровня от корня (= размер префикса). Это позволяет остановить поиск слов, когда мы видим, что ни одна дочерняя ветвь не может дать слово определенной длины.

Матрица. Матрица представляет собой двойной массив букв. Но для большей эффективности я добавил некоторые данные: соответствующий ему узел в словаре (см. Алгоритм), направление к его дочерним элементам (см. Алгоритм) и его родителю (см. Алгоритм).

Алгоритм Идея состоит в том, чтобы «кружить» на карте путем «убывания» (увеличивая путь, представляющий текущую найденную строку). Когда спуск невозможен, мы должны «подняться»:

FIND WORD:
----------

while(we can continue)
try descend
if(failed to descend)
ascend
else
node = node of current cell
if node is end of word
add it to the found words, then ascend
else if node is out of range (ie, n = 5, but with node you can only have words with 3 characters)
ascend

DESCEND:
--------

we're from cell (x,y), with node D
for each direction (from cell.direction to north-west, clockwise)
advance position (x,y) with direction
if the position is valid
and we haven't already visited the cell for this word
and the node got with D.children[cell.letter] exists
set the current position of the algorithm to the result of the advance
set the direction of the old cell to the direction used to advance
set the direction of the new cell to the opposite (pointing to the old cell)
set the node of the new cell by the found one
return

ASCEND:
-------

we're at (x,y)
cell.node = 0 (the cell is not considered as visited anymore)
advance the parent direction by one clockwise (if this direction is north-west, we use a special direction that say that we cannot rotate anymore: FINISHED)
cell.dir = INVALID
advance (x,y) following cell.direction_to_parent
cell.direction_to_parent = INVALID
set the current position to the result of advance

Объяснение изображения:

Алгоритм развернут http://img822.imageshack.us/img822/1374/algow.png

Шаги (число указано в лозангах):

1. Вот наша матрица. Я проверил это с французским словарем. Допустим, мы начинаем с ячейки (0,0) (алгоритм работает везде, где вы начинаете).
2. Первое правильное направление (слово + на карте) — восток. Мы продвигаемся вслед за этим. Узел не является концом слова и все еще действует.
3. Первое действительное направление (слово + на карте) — юго-восток. Мы продвигаемся вслед за этим. Узел не является концом слова и все еще действует.
4. Первое правильное направление (слово + на карте) — восток. Мы продвигаемся вслед за этим. Узел не является концом слова и все еще действует.
5. Действительных указаний нет (вне карты, уже посещенная ячейка (E) или нет в словаре), поэтому мы поднимаемся
6. Первое действительное направление (слово + на карте) — юго-восток. Мы продвигаемся вслед за этим. Узел не является концом слова и все еще действует.
7. Первое правильное направление (слово + на карте) — юг. Мы продвигаемся вслед за этим. Узел не является концом слова и все еще действует.
8. Первое правильное направление (слово + на карте) — запад. Мы продвигаемся вслед за этим. Узел является концом слова (что является «анерией»), поэтому мы добавляем его в список найденных слов и поднимаемся. Для информации, «ânerie» по-французски это «ерунда» или «глупость» по-английски.
9. И так далее…