c语言 - 给定一个 FILE * ，如何有效地找到"abc"第一次出现的偏移量？

Question

如何在C语言中高效地完成这类工作?

我能想到的是首先将整个文件加载到内存中，然后在其中进行搜索。

但是有没有更有效的方法呢?

如果文件非常大，将整个文件装入内存是不可能的。

Answer 1

将整个文件加载到内存中是不必要且低效的。试试这样做:

FILE *fl;
int cc = getc(fl);
while (cc != EOF)
{
   if (cc=='a')
   {
     cc = getc(fl);
     if (cc=='b')
     {
       cc = getc(fl);
       if (cc=='c')
          return "FOUND";
      }
    }
    cc = getc(fl);
  }
  return "NOT FOUND";

显然你永远不会真正使用这样的代码。您应该编写一个接受任意字符串进行搜索的函数，但算法基本上是相同的。此外，I/O将由系统缓冲，因此您不必担心一次读取单个字符的效率。我也没有包括任何错误检查

Answer 2

您可以逐块读取文件并在每个块中搜索"abc"。有像Boyer-Moore搜索这样的算法来减少你必须显式检查的字符数量。

在linux中，您可以使用posix_fadvise来告诉它您将使用该文件。

Answer 3

对于字符串搜索有许多有趣的算法。例如，在Boyer-Moore中，如果你要匹配'abc'，你可以利用第三个位置必须是'c'的事实，如果它是不是 'c'，那么表格会告诉你前进的距离(例如，如果它是'd'，你可以跳过3，因为前3个字母对你来说根本不感兴趣)。

然而，与读取文件所花费的时间相比，有趣的字符串搜索方法根本无关紧要。如果您想处理任意文件，则应该避免全部读入，因为额外的内存使用是浪费的，并且会减慢您的速度。但是你不能避免读取整个文件，直到你找到你的字符串。

Answer 4

你用的是什么操作系统?如果是Linux，您可以使用内存映射自动将内存的某一部分直接映射到文件。它被认为更快。

编辑

mmap不会一次将整个文件加载到内存中。这样更有效率。