대용량 텍스트 파일 처리
-
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가 증가하고 답을 병렬화하는 방법이 다를 수 있습니다.
- 단일 레드 레드 - 스트레이트 포워드와 구현이 쉽습니다.
- 다중 리더 스레드와 하나의 데이터 인프라가있는 다중 스레드. 그런 다음 Datafrsucture에 대한 액세스를 동기화해야합니다. 트리에서는 실제로있는 노드를 잠그면됩니다. 따라서 여러 독자가 많은 간섭없이 데이터 스트럭처에 액세스 할 수 있습니다. 자체 밸런싱 트리는 특히 재조정 할 때 다를 수 있습니다.
- 다중 리더 스레드로 다중 스레드, 각각 고유 한 데이터 구조가 있습니다. 각 스레드는 파일의 일부를 읽는 동안 자체 데이터 구조를 구축합니다. 각각을 완료 한 후에는 결과를 결합해야합니다 (쉬워야합니다).
생각해야 할 한 가지 - 각 스레드에 대한 단어 경계를 찾아야하지만 큰 문제가 발생하지 않아야합니다 (예 : 각 스레드는 첫 번째 단어 경계까지 시작하여 각 스레드가 시작됩니다. 작동중인 단어를 완성합니다).
두 번째 스레드를 사용하여 데이터를 읽은 후 데이터를 분석할 수 있지만 그렇게 해도 큰 이득을 얻지는 못할 것입니다.데이터를 읽기 위해 둘 이상의 스레드를 사용하려고 하면 속도가 향상되기보다는 속도가 저하될 것이 거의 확실합니다.여러 스레드를 사용하여 데이터를 처리하는 것은 의미가 없습니다. 처리는 읽는 것보다 몇 배 더 빠르므로 추가 스레드가 하나만 있어도 한계는 디스크 속도가 됩니다.
상당한 속도를 얻는 한 가지 (가능한) 방법은 일반적인 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/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