☰

需要比“wc -l”更快的东西

tag-icon • tag-icon command-line wc
需要比“wc -l”更快的东西

对于像 1GB 这样的大文件来说，wc -l速度会很慢。我们是否有更快的方法来计算特定文件的换行数？

答案1

你可以尝试用C写：

#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(){
  char buf[BUFSIZ];
  int nread;
  size_t nfound=0;
  while((nread=read(0, buf, BUFSIZ))>0){
    char const* p;
    for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
  }
  if(nread<0) { perror("Error"); return 1; }
  printf("%lu\n", nfound);
  return 0;
}

保存在eg, 中wcl.c，编译eg, withgcc wcl.c -O2 -o wcl并运行

<yourFile ./wcl

这会发现我的系统上的 1GB 文件中散布着换行符，时间约为370毫秒（重复运行）。 （增加缓冲区大小会稍微增加时间，这是可以预料的——BUFSIZ 应该接近最佳值）。这个很有可比性了~380毫秒我从wc -l.

Mmaping 让我度过了一段更好的时光280毫秒，但它当然有仅限于真实文件的限制（没有 FIFO、没有终端输入等）：

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
int main(){
  struct stat sbuf;
  if(fstat(0, &sbuf)<0){ perror("Can't stat stdin"); return 1; }

  char* buf = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, 0/*stdin*/, 0/*offset*/);
  if(buf == MAP_FAILED){ perror("Mmap error"); return 1; } 

  size_t nread = sbuf.st_size, nfound=0;
  char const* p;
  for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}

  printf("%lu\n", nfound);
  return 0;
}

我使用以下命令创建了测试文件：

 $ dd if=/dev/zero of=file bs=1M count=1042

并添加了一些测试换行符：

 $ echo >> 1GB

和一个十六进制编辑器。

答案2

您可以通过减少对 的调用次数来改进 @pskocik 建议的解决方案read。有一个很多BUFSIZ从 1Gb 文件中读取块的调用次数。通常的方法是增加缓冲区大小：

  • 只是为了好玩，尝试将缓冲区大小增加 10 倍或 100 倍。在我的 Debian 7 上，BUFSIZ是 8192。使用原始程序，这是 12 万次读取操作。您可能可以负担得起 1Mb 输入缓冲区，将其减少 100 倍。
  • 为了更优化的方法，应用程序可以分配与文件一样大的缓冲区，需要单个读取操作。这对于“小”文件来说已经足够了（尽管有些读者的机器上有超过 1GB 的空间）。
  • 最后，您可以尝试使用内存映射 I/O，它会自行处理分配。

在对各种方法进行基准测试时，您可能会记住，某些系统（例如 Linux）将计算机的大部分未使用内存用作磁盘缓存。不久前（大约 20 年前，在卑鄙的常见问题解答），我对（不是很好）分页算法出乎意料的好结果感到困惑，我开发了该算法来处理文本编辑器中的低内存情况。有人向我解释说它运行得很快，因为程序是从用于读取文件的内存缓冲区工作的，并且只有重新读取或写入文件时才会有速度差异。

这同样适用于mmap（在另一种情况下，仍在我的待办事项列表中纳入常见问题解答，开发人员在磁盘缓存是改进的实际原因的情况下报告了非常好的结果）。开发基准需要花费时间和精力来分析良好（或不良）性能的原因。

进一步阅读：

相关内容