优化这个小功能,它将在C中运行很多次[关闭]

问题描述 投票:-1回答:1

以下是函数每个部分的最坏情况:

  • 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];
    }
}
c algorithm performance optimization
1个回答
1
投票

您关于创建“单词正方形”的注释意味着您要打印或以其他方式报告9⨉9个正方形,其中每行和每列都是grouped_dict中的单词。在这种情况下,当到目前为止填充的字符包含无法用单词填充的部分行或列时,您至少应该从find_square返回。

一种方法是在调用find_square检查列之后在fill_row中添加代码。在fill_row之后,每列至少部分填充。对于每一列,检查grouped_dict中至少有一个与目前列匹配的单词。如果没有,请从find_square返回而不再尝试填写。

这将极大地加速您的程序,但其他优化也许是可能的。你应该考虑的事项包括:

  • grouped_dict进行排序,以便在其中搜索匹配很快。
  • 以复杂的方式索引grouped_dict以更快地搜索匹配。
  • 交替填充行和列以尝试增加可能更快地揭示不可能完成状态的冲突。
  • 使用通过检查grouped_dict找到的部分匹配来限制填充下一行或列时尝试的可能性。
  • 专注于grouped_dict中不常见的字母作为关键点。
© www.soinside.com 2019 - 2024. All rights reserved.