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

Question

我必须使用 C/C+ 找到一种非常优化的方法来查找包含单词的非常长的文件中字符的频率（忽略大小写，应同时计算小写和大写） +。我已经知道一个是这个（这里我正在终端读取用户的输入，但在我的例子中我将从文件中读取，所以请不要转到 gets() 函数，请关注我的主要 objective 哪个是为了获得比这更优化的方式（如果可能的话））：

int main()
{
   char string[100];
   int c = 0, count[26] = {0};

   printf("Enter a string\n");
   gets(string);

   while (string[c] != '[=10=]')
   {
      /** 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 时间完全可以忽略不计。

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

The best optimal way to find the frequency in a very very long string

c

algorithm

data-structures

lookup-tables