c - 在非常长的字符串中查找频率的最佳方法

Question

我必须找到一种非常优化的方法来使用 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;
}

但我想对其进行更多优化，因为它必须适用于包含很多单词的非常非常长的文件，有人可以给我任何建议或想法吗？谢谢。

Answer 1

渐近复杂度并没有得到任何改善，而且一般来说算法已经处于最低限度。

您可以做出的最重要的改变是减少调用 IO 函数的频率(并且您不会真正调用gets)；使用 fread 并在大缓冲区(例如 4 KB)中读取 - 较大的缓冲区通常没有好处。

根据 CPU 和缓存的不同，如果内存中已经有整个字符串，那么将 count 元素长度设置为 256 个元素并避免使用 if 可能会给您带来一些好处字母字符(用少一个分支预测点来换取更大的缓存占用)。但我怀疑这是否是可测量的 - 您的代码现在应该完全受 IO 限制，与等待磁盘读取相比，处理所需的 CPU 时间完全可以忽略不计。