텍스트를 구문 분석하는 가장 빠른 방법은 무엇입니까?

Question

어떤 텍스트 파일에서 발견 된 주어진 문자열 다음에 오는 첫 번째 단어 (또는 부동 소수점 숫자)를 추출하려고합니다 (How to extract the first word that follows a string? 참조). 나는 당신이 perl이나 sed, 그리고 아마도 다른 많은 방법으로 그것을 할 수 있다는 것을 압니다. 나는 성과를 찾고있다. 파싱하는 가장 빠른 방법은 무엇입니까?

Answer 1

비슷한 질문을 할 때마다 특정 사례를 구현하고 적용 가능한 도구를 선택하여 측정합니다.

너 다른 요인이 그림에 왜곡되어 있음을 알 수 있습니다. 파일 열기/읽기 등의 속도 때문에 기술 권장 사항은 쓸모가 없습니다.

Answer 2

정말 단순한 경우 (실제 정규 표현식이 없다면) C가 (memchr() 및 friends)를 얻게 될 것입니다. 그렇지 않으면 TCL이 강력한 경쟁자가 될 것이고 Perl이 뒤따를 것입니다 정규 표현식 설계 기술).

추가 설명 : 설명을 다시 읽고 (관련 링크) 몇 가지 도구를 테스트하고 결과를 비교해야한다고 말하고 싶습니다. 우리에게 (어딘가에) 입력 파일을 제공하고 해당 파일을 기반으로 정확한 문제를 지정할 수 있습니까?

부록 2 (파인만에 대한) : (당신이 제안한 "사이트 디자인 /") 은이 사이트 (~ 44킬로바이트, 'sof.dat')를 저장 및 반복 검색 테스트 을 수행 펄한다. 이것은 사용되는 코드입니다 : 내 설치 (2,4GHz E6600, Win7에, ActivePerl의)와

... 
use Benchmark qw' timeit timestr '; 

{ 
    open my $fh, '<', 'sof.dat' or die $!; 
    undef $/; 
    our $data = <$fh>; 
    close $fh; 

    my $count = 100000; 
    my $t = timeit($count, ' $data =~ m|site design /| ? 1 : 0 ' ); 
    print "$count loops of code took:", timestr($t),"\n"; 
} 
... 

, 다음 타이밍 나왔다 : 코드의

100000 루프에 나섭니다 : 1 wallclock의 초 을 (1.36 usr + 0.00 sys = 1.36 CPU) @ 73746.31/s (n = 100000)

즉,이 페이지에서이 텍스트는 초당 약 74,000 번 찾을 수 있습니다. 나는 전체 파일 처리를 포함하는 경우

:

use Benchmark qw' timeit timestr '; 

{ 
    my $count = 10000; 
    my $t = timeit($count, q{ 
        open my $fh, '<', 'sof.dat' or die $!; 
        undef $/; 
        our $data = <$fh>; 
        close $fh; 
        $data =~ m|site design /| ? 1 : 0 
        }); 
    print "$count loops of code took:", timestr($t),"\n"; 
} 

을 우리는거야 : 코드의

10000 루프에 나섭니다 : 3 wallclock의 초를 (1.70 USR + 1.51 SYS = 3.21 CPU) @ 3110.42/s (n = 10000)

초당 약 3 천 건의 검색/발견 통과.

감사

RBO

Answer 3

하면, 디스크, 또는 더 나쁜에서 문자열을 읽어 네트워크를 읽어됩니다 대부분의 시간, 그것은 이미 어떤 제정신 방법보다 느린 크기 순서입니다 당신이 선택하는 검색. 그런데 문자열이 이미 메모리에 있고 검색 용어가 앞쪽에 있다는 것을 알고 있다면 정규 표현식 (Perl이 아닌 실제 FSM 기반 구문)이 입력 크기에 대해 시간 선형으로 작동하도록 보장됩니다. 단지 일정한 요인에 의해 더 빠를 것입니다. re2라는 빠른 정규식 엔진 라이브러리가 있습니다.

Answer 4

고정 된 문자열을 찾고 있다면 Boyer-Moore 또는 Boyer-Moore-Horspool과 같은 것을 사용하여 검색 할 수 있습니다 (후자의 경우 Ray Gardner의 구현을 권장합니다). B-M과 B-M-H는 모두 sublinear입니다. 대조적으로, 정규 표현식은 최상의 선형은 이며 많은 구현 (역 추적을 사용하는 구현)은 2 차입니다.

다음 단계는 가능한 빨리 데이터를 메모리로 읽는 것입니다. 현실적으로 이것은 일반적으로 병목 현상이 될 것입니다. 불행히도 병목 현상을 해결하려면 일반적으로 일부 이식 가능 코드를 사용해야합니다. 리눅스에서는 mmap이 가장 좋은 선택 인 반면, Windows에서는 인데 보통은 큰 덩어리를 한꺼번에 읽는 편이 더 좋으며 FILE_FLAG_NO_BUFFERING 플래그가있는 CreateFile입니다. 또한 I/O 완료 포트 (IOCP)를 사용하여 읽기 작업을 수행하여 검색과 읽기 작업을 동시에 수행 할 수 있습니다. 이론 상으로는 적절한 종류의 패턴을 서브 라인 방식으로 검색하는 RE 엔진을 작성할 수 있습니다. 그러나 실제로 어떤 것이 있는지는 알지 못합니다.