我必须找到一种非常优化的方法来使用 C/C++ 查找包含单词的非常长的文件中的字符频率(忽略大小写,应该同时计算小写和大写)。 我已经知道这是一个(这里我正在终端读取用户的输入,但在我的情况下,我将从文件中读取,所以请不要转到 gets() 函数,请专注于我的主要目标,即获得比这更优化的方式(如果有可能的话):
int main()
{
char string[100];
int c = 0, count[26] = {0};
printf("Enter a string\n");
gets(string);
while (string[c] != '\0')
{
/** Considering characters from 'a' to 'z' only
and ignoring others */
if (string[c] >= 'a' && string[c] <= 'z')
count[string[c]-'a']++;
c++;
}
for (c = 0; c < 26; c++)
{
/** Printing only those characters
whose count is at least 1 */
if (count[c] != 0)
printf("%c occurs %d times in the entered string.\n", c + 'a', count[c]);
}
return 0;
}
但我想对其进行更多优化,因为它必须适用于包含很多单词的非常非常长的文件,有人可以给我任何建议或想法吗?谢谢。
最佳答案
渐近复杂度并没有得到任何改善,而且一般来说算法已经处于最低限度。
您可以做出的最重要的改变是减少调用 IO 函数的频率(并且您不会真正调用gets
);使用 fread
并在大缓冲区(例如 4 KB)中读取 - 较大的缓冲区通常没有好处。
根据 CPU 和缓存的不同,如果内存中已经有整个字符串,那么将 count
元素长度设置为 256 个元素并避免使用 if
可能会给您带来一些好处字母字符(用少一个分支预测点来换取更大的缓存占用)。但我怀疑这是否是可测量的 - 您的代码现在应该完全受 IO 限制,与等待磁盘读取相比,处理所需的 CPU 时间完全可以忽略不计。
关于c - 在非常长的字符串中查找频率的最佳方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33007156/