以下是函数每个部分的最坏情况:
while
等于9时,size
循环运行53,402次。find_square()
的每次调用都会将find_square()
本身调用53,402次,直到row == size
,在本例中为9。因此,对find_square()
的呼叫总数(53,402)^ 10 = 188 quattuordecillion。
这甚至不是最终功能的全部,但如果它已经慢了,我想先解决这个问题。显然这是一个非常荒谬的电话,但我真的看不到它的方法。我对任何想法持开放态度,这里的任何帮助都会很棒,谢谢!
void find_square(char*** hashed_dict, char*** grouped_dict, char** square, int size, int row) {
if (row == size) {
return;
}
int i = 0;
while (grouped_dict[size - 1][i] != NULL) {
fill_row(square, row, size, grouped_dict[size - 1][i]);
find_square(hashed_dict, grouped_dict, square, size, row + 1);
i++;
}
}
void fill_row(char** square, int row, int size, char* word) {
for (int i = 0; i < size; i++) {
square[row][i] = word[i];
}
}
您关于创建“单词正方形”的注释意味着您要打印或以其他方式报告9⨉9个正方形,其中每行和每列都是grouped_dict
中的单词。在这种情况下,当到目前为止填充的字符包含无法用单词填充的部分行或列时,您至少应该从find_square
返回。
一种方法是在调用find_square
检查列之后在fill_row
中添加代码。在fill_row
之后,每列至少部分填充。对于每一列,检查grouped_dict
中至少有一个与目前列匹配的单词。如果没有,请从find_square
返回而不再尝试填写。
这将极大地加速您的程序,但其他优化也许是可能的。你应该考虑的事项包括:
grouped_dict
进行排序,以便在其中搜索匹配很快。grouped_dict
以更快地搜索匹配。grouped_dict
找到的部分匹配来限制填充下一行或列时尝试的可能性。grouped_dict
中不常见的字母作为关键点。