대용량 텍스트 파일 처리

StackOverflow https://stackoverflow.com/questions/1625299

  •  06-07-2019
  •  | 
  •  

문제

문제:나는 거대한 원시 텍스트 파일 (3GIG라고 가정)을 가지고 있는데 파일의 각 단어를 거쳐서 파일에 몇 번이나 단어가 나타납니다.

내가 제안한 솔루션:대용량 파일을 여러 파일로 분할하면 분할된 각 파일에 정렬된 단어가 포함됩니다.예를 들어, "로 시작하는 모든 단어"ㅏ"는 "에 저장됩니다._a.dic" 파일.따라서 언제든지 26개 이상의 파일을 초과하지 않습니다.

이 접근방식의 문제점은,

스트림을 사용하여 파일을 읽을 수 있지만 스레드를 사용하여 파일의 특정 부분을 읽고 싶었습니다.예를 들어 별도의 스레드로 0-1024바이트를 읽습니다(번호를 기준으로 최소한 4-8개의 스레드가 있어야 함).의 프로세서가 상자에 존재합니다).이게 가능한 걸까, 아니면 내가 꿈을 꾸고 있는 걸까?

더 나은 접근 방식이 있나요?

메모:이는 순수한 C++ 또는 C 기반 솔루션이어야 합니다.데이터베이스 등은 허용되지 않습니다.

도움이 되었습니까?

해결책

당신은 봐야합니다 '프로그래밍 연습'Kernighan과 Pike, 특히 3 장.

C ++에서 문자열과 카운트를 기준으로 맵을 사용합니다 (std::map<string,size_t>, IIRC). 파일을 읽고 (한 번 - 두 번 이상 읽기에는 너무 큽니다), 가면서 단어로 나누고 ( 'Word'의 정의를 위해), 찾은 각 단어에 대한지도 항목의 카운트를 증가시킵니다.

C에서는지도를 직접 만들어야합니다. (또는 David Hanson을 찾으십시오.C 인터페이스 및 구현".)

또는 Perl, Python 또는 AWK (모두 맵에 해당하는 연관 배열이 있음)를 사용할 수 있습니다.

다른 팁

파일의 일부를 동시에 읽는 여러 스레드를 사용하는 것이 많은 도움이 될 것이라고 생각하지 않습니다. 이 응용 프로그램은 실제 단어 계산이 아니라 하드 디스크의 대역폭 및 대기 시간에 묶여있을 것으로 기대합니다. "준 랜덤"파일 액세스가 일반적으로 "선형 파일"액세스보다 느리기 때문에 이러한 멀티 스레드 버전은 실제로 악화 될 수 있습니다.

CPU가 단일 스레드 버전에서 실제로 바쁘면 잠재적 인 속도가있을 수 있습니다. 하나의 스레드는 큰 청크로 데이터를 읽고 제한된 용량의 대기열에 넣을 수 있습니다. 다른 많은 작업자 실이 각각 자체 청크로 작동하고 단어를 계산할 수 있습니다. 카운팅 작업자 스레드가 완성 된 후에는 카운터를 병합해야합니다.

먼저 - 단어를 저장하기위한 데이터 스트럭처를 결정하십시오.

명백한 선택은지도입니다. 그러나 아마도 a 트리 더 나은 서비스를 제공 할 것입니다. 각 노드에서 단어 카운트를 저장합니다. 0은 단어의 일부일 뿐이라는 것을 의미합니다. 스트림을 사용하여 트리에 삽입하고 파일 문자 기반을 읽을 수 있습니다.

두 번째 - 멀티 스레딩 예 또는 아니오? 이것은 대답하기 쉽지 않습니다. 크기에 따라 Datafrsucture가 증가하고 답을 병렬화하는 방법이 다를 수 있습니다.

  1. 단일 레드 레드 - 스트레이트 포워드와 구현이 쉽습니다.
  2. 다중 리더 스레드와 하나의 데이터 인프라가있는 다중 스레드. 그런 다음 Datafrsucture에 대한 액세스를 동기화해야합니다. 트리에서는 실제로있는 노드를 잠그면됩니다. 따라서 여러 독자가 많은 간섭없이 데이터 스트럭처에 액세스 할 수 있습니다. 자체 밸런싱 트리는 특히 재조정 할 때 다를 수 있습니다.
  3. 다중 리더 스레드로 다중 스레드, 각각 고유 한 데이터 구조가 있습니다. 각 스레드는 파일의 일부를 읽는 동안 자체 데이터 구조를 구축합니다. 각각을 완료 한 후에는 결과를 결합해야합니다 (쉬워야합니다).

생각해야 할 한 가지 - 각 스레드에 대한 단어 경계를 찾아야하지만 큰 문제가 발생하지 않아야합니다 (예 : 각 스레드는 첫 번째 단어 경계까지 시작하여 각 스레드가 시작됩니다. 작동중인 단어를 완성합니다).

두 번째 스레드를 사용하여 데이터를 읽은 후 데이터를 분석할 수 있지만 그렇게 해도 큰 이득을 얻지는 못할 것입니다.데이터를 읽기 위해 둘 이상의 스레드를 사용하려고 하면 속도가 향상되기보다는 속도가 저하될 것이 거의 확실합니다.여러 스레드를 사용하여 데이터를 처리하는 것은 의미가 없습니다. 처리는 읽는 것보다 몇 배 더 빠르므로 추가 스레드가 하나만 있어도 한계는 디스크 속도가 됩니다.

상당한 속도를 얻는 한 가지 (가능한) 방법은 일반적인 iostream을 우회하는 것입니다. 일부는 C FILE*을 사용하는 것만큼 빠르지만 실제로 더 빠른 것은 없으며 일부는 상당히 느립니다.이것을 시스템에서 실행하는 경우(예:Windows) C와 눈에 띄게 다른 I/O 모델을 사용하는 경우 조금만 주의하면 훨씬 더 많은 것을 얻을 수 있습니다.

문제는 매우 간단합니다.읽고 있는 파일이 사용 가능한 캐시 공간보다 (잠재적으로) 더 큽니다. 하지만 파일 덩어리를 다시 읽지 않을 것이기 때문에 캐싱을 통해 아무 것도 얻을 수 없습니다(적어도 작업을 수행하는 경우). 현명하게).따라서 시스템에 캐싱을 우회하고 디스크 드라이브에서 처리할 수 있는 메모리로 데이터를 가능한 한 직접 전송하도록 지시할 수 있습니다.유닉스 계열 시스템에서는 아마도 open() 그리고 read() (그리고 당신에게 많은 것을 얻지 못할 것입니다).Windows에서는 CreateFile 그리고 ReadFile, 전달 FILE_FLAG_NO_BUFFERING 플래그를 지정하다 CreateFile -- 올바르게 수행하면 속도가 대략 두 배로 빨라질 것입니다.

또한 다양한 병렬 구조를 사용한 처리를 옹호하는 몇 가지 답변도 얻었습니다.나는 이것이 근본적으로 잘못된 것이라고 생각합니다.엄청나게 어리석은 일을 하지 않는 한, 파일의 단어 수를 세는 데 걸리는 시간은 단순히 파일을 읽는 데 걸리는 시간보다 몇 밀리초 정도 더 길어질 뿐입니다.

내가 사용할 구조는 각각 1MB의 버퍼 두 개를 갖는 것입니다.데이터를 하나의 버퍼로 읽습니다.해당 버퍼를 계산 스레드로 넘겨 해당 버퍼에 있는 단어를 계산합니다.그런 일이 일어나는 동안 두 번째 버퍼로 데이터를 읽어보세요.완료되면 기본적으로 버퍼를 교체하고 계속하십시오.한 버퍼에서 다음 버퍼로 경계를 넘을 수 있는 단어를 처리하기 위해 버퍼를 교환할 때 수행해야 할 약간의 추가 처리가 있지만 이는 매우 사소한 일입니다(기본적으로 버퍼가 흰색으로 끝나지 않는 경우). 공간이 없으면 다음 데이터 버퍼에서 작업을 시작할 때 여전히 단어에 있습니다.

다중 프로세서(다중 코어) 시스템에서만 사용된다는 확신이 있는 한 실제 스레드를 사용하는 것은 괜찮습니다.단일 코어 시스템에서 이 작업이 수행될 가능성이 있다면 중첩된 I/O가 있는 단일 스레드를 대신 사용하는 것이 다소 더 나을 것입니다.

다른 사람들이 지적했듯이 병목 현상은 디스크 I/O가됩니다. 따라서 겹친 I/O를 사용하는 것이 좋습니다. 이것은 기본적으로 프로그램 논리를 뒤집습니다. I/O를 수행 할시기를 결정하기 위해 코드를 기울이는 대신 운영 체제에 약간의 I/O가 완료 될 때마다 코드를 호출하도록 지시합니다. 사용하는 경우 I/O 완료 포트, 파일 청크를 처리하기 위해 여러 스레드를 사용하도록 OS에도 알릴 수도 있습니다.

C 기반 솔루션?

나는 Perl 이이 정확한 목적으로 태어 났다고 생각합니다.

스트림에는 커서가 하나만 있습니다.한 번에 두 개 이상의 스레드로 스트림에 액세스하면 원하는 위치를 읽을 수 없을 것입니다.커서 위치부터 읽기가 수행됩니다.

내가 할 일은 스트림을 읽고 읽은 바이트를 다른 스레드에 전달하는 스레드(아마도 메인 스레드) 하나만 갖는 것입니다.

예를 들어:

  • 스레드 #i가 준비되었으며 메인 스레드에 다음 부분을 제공하도록 요청합니다.
  • 메인 스레드는 다음 1Mb를 읽고 이를 스레드 1에 제공합니다.
  • 스레드 #i는 1Mb를 읽고 원하는 대로 단어 수를 세고,
  • 스레드 #i는 작업을 마치고 다음 1Mb를 다시 요청합니다.

이런 방식으로 스트림 읽기와 스트림 분석을 분리할 수 있습니다.

당신이 찾고있는 것은 Regex입니다. C ++ Regex 엔진 의이 stackoverflow 스레드는 다음과 같습니다.

C ++ : 어떤 Regex 라이브러리를 사용해야합니까?

첫째, C/C ++가 이것을 처리하는 가장 좋은 방법이 아니라고 확신합니다. 이상적으로는 병렬 처리에도 맵/축소도 사용합니다.

그러나 당신의 제약을 가정하면 여기에 내가하는 일이 있습니다.

1) 텍스트 파일을 작은 청크로 나눕니다. 당신은 단어의 첫 글자로 이것을 할 필요가 없습니다. 5000 단어 덩어리로 나누십시오. 의사 코드에서는 다음과 같은 일을 할 것입니다.

색인 = 0

numwords = 0

mysplitfile = OpenFile (index-split.txt)

while (bigfile >> Word)

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

2) 공유 맵 데이터 구조와 pthreads를 사용하여 새 스레드를 생성하여 각 하위 파일을 읽습니다. 다시, 의사 코드 :

maplock = create_pthread_lock ()

SharedMap = std :: map ()

모든 index-split.txt 파일에 대해 :

spawn-new-thread(myfunction, filename, sharedmap, lock)

dump_map (sharedmap)

void myfunction (filename, sharedMap) {

localmap = std::map<string, size_t>();

file = openfile(filename)

while (file >> word)

    if !localmap.contains(word)
         localmap[word] = 0

    localmap[word]++

acquire(lock)
for key,value in localmap
    if !sharedmap.contains(key)
         sharedmap[key] = 0

    sharedmap[key] += value
release(lock)

}

구문에 대해 죄송합니다. 나는 최근에 많은 파이썬을 쓰고 있습니다.

C는 아니고 약간 보기 흉하지만, 실행하는 데 2분 밖에 걸리지 않았습니다.

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

다음을 사용하여 각 줄을 반복합니다. -n
각 줄을 다음과 같이 나눕니다. @F 와 단어 -a
각 $_ 단어가 해시를 증가시킵니다. %h
일단 END ~의 file 도달했습니다,
sort 빈도별 해시 $h{$b}<=>$h{$a}
두 빈도가 동일하면 알파벳순으로 정렬 $a cmp $b
주파수를 인쇄하세요 $h{$w} 그리고 그 단어 $w
결과를 'freq' 파일로 리디렉션

저는 이 코드를 580,000,000 단어로 구성된 3.3GB 텍스트 파일에서 실행했습니다.
Perl 5.22는 173초 만에 완료되었습니다.

내 입력 파일에는 이미 다음 코드를 사용하여 구두점을 제거하고 대문자를 소문자로 변환했습니다.
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(런타임 144초)

단어 계산 스크립트는 awk로 작성할 수도 있습니다.
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top