“wc -l”보다 빠른 것이 필요합니다 파일의 줄 바꿈 수를 계산하는 더 빠른

1GB와 같은 큰 파일의 wc -l경우 속도가 느려집니다. 특정 파일의 줄 바꿈 수를 계산하는 더 빠른 방법이 있습니까?



답변

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;
}

에 저장, 예를 들어 wcl.c컴파일 gcc wcl.c -O2 -o wcl및 실행

<yourFile ./wcl

이것은 약 370ms (반복 실행)로 시스템의 1GB 파일에 줄 바꿈을 발견 합니다. (버퍼 크기를 늘리면 시간이 약간 증가합니다. BUFSIZ가 최적에 가까워 야합니다). 이것은 내가 얻는 ~ 380ms 와 매우 비슷합니다 wc -l.

Mmaping은 약 280ms 의 더 나은 시간을 제공 하지만 물론 실제 파일 (FIFOS 없음, 터미널 입력 없음)로 제한되는 한계가 있습니다.

#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

그리고 16 진 편집기.


답변

에 대한 호출 수를 줄임으로써 @pskocik에서 제안한 솔루션을 개선 할 수 있습니다 read. 있습니다 많이 읽을 수있는 통화의 BUFSIZ1GB의 파일에서 청크. 이를 수행하는 일반적인 방법은 버퍼 크기를 늘리는 것입니다.

  • 재미를 위해서 버퍼 크기를 10 배로 늘리십시오. 또는 100. 내 데비안 7에서는 BUFSIZ8192입니다. 원래 프로그램에서는 12 만 건의 읽기 작업이 있습니다. 아마도 1Mb 입력 버퍼를 감당하여 100 배로 줄일 수 있습니다.
  • 보다 최적의 접근 방식을 위해 응용 프로그램은 파일만큼 큰 버퍼를 할당하여 단일 읽기 작업이 필요할 수 있습니다. “작은”파일에는 충분합니다 (일부 독자는 컴퓨터에 1Gb 이상을 가지고 있지만).
  • 마지막으로, 할당을 처리하는 메모리 매핑 I / O를 실험 할 수 있습니다.

다양한 접근 방식을 벤치마킹 할 때 Linux와 같은 일부 시스템은 대부분의 시스템에서 사용하지 않는 메모리를 디스크 캐시로 사용한다는 것을 명심하십시오. 얼마 전 (거의 20 년 전, 사악한 FAQ 에서 언급 ), 텍스트 편집기에서 메모리 부족 조건을 처리하기 위해 개발 한 (아주 좋지 않은) 페이징 알고리즘의 예기치 않은 좋은 결과에 의아해했습니다. 프로그램이 파일을 읽는 데 사용 된 메모리 버퍼에서 작동하기 때문에 빠르게 실행되었다고 설명했으며 파일을 다시 읽거나 쓰는 경우에만 속도 차이가 있다고 설명했습니다.

동일하게 적용됩니다 mmap(또 다른 경우에도 FAQ에 포함시키기 위해 할 일 목록에 있음). 개발자는 디스크 캐시가 실제 개선의 이유 인 시나리오에서 매우 좋은 결과를보고했습니다. 벤치 마크를 개발하려면 성능이 우수한 이유를 분석하는 데 시간과주의가 필요합니다.

더 읽을 거리 :