GNU textutil의 sort 소스를 보니
Symmetric Multi Processing (SMP)에 대해서
잇점은 없습니다.
하드웨어적으로 해결을 본다면,
듀얼 CPU보다는 단일의 빠른 클럭의 CPU와 큰 램, 그리고 빠른 하드(RAID-0 mode의 하드array면 더 낳을 듯.)가 더 효과적일 것 같습니다.
만약 SMP에서 이득을 볼려면,
별도록 작성하셔야 할 것 같습니다.
윈도우쪽은 소스를 볼수가 없어서 모르겠습니다.
jinyedge wrote:
그리고 어쩌면 단순히 하드웨어의 사양을 높이는 것만으로도 가능할 것도
같은데 40G 정도의 텍스트 파일을 1시간 내에 정렬을 하려면 어느 정도
의 시스템이 필요할까요? 예를 들자면 제온 2.4 듀얼에 스카시 320 정도를
쓴다면 그냥 운영체제에 포함된 sort 프로그램으로도 가능할까요?
대용량의 소팅에 cpu 성능의 영향은 아주 미미합니다.
램에 담아서 소팅할 수 없는 자료들을 소팅할때는 소팅시간의
95% 이상이 디스크 IO 시간이기때문에 디스크 IO를 줄이는게
소팅시간을 줄이는 거라고 생각하면 정답이죠.
그리고 이런건 이미 많은 사람들이 고민 했기 때문에 우리가 고민할 필요 없습니다. 좋은 알고리즘들이 이미 있다는거져.
정렬은 내부정렬과 외부정렬로 나뉘는데 qsort 같은 함수야 당연히 퀵소팅으로
구현된거니 내부정렬이라서 40G 자료의 소팅에는 맞지 않는 함수이지요.
주메모리를 넘는 소팅은 외부정렬이므로 거기에 걸맞는 알고리즘을 사용하시면
보다 좋은 포퍼먼스를 얻으실 수 있을 듯 하네요.
배보다 배꼽이 더 큰 방법이 될지도 모른다는 생각이 들지만... 혹시 가용한 기계가 몇대 있다면, NFS 로 잘 뜯어맞춰서, 로그를 기계별로 적당히 분배한 다음 머지하는 방법도 괜찮지 않을까요. 머지소트 따위.... 테입에서 쓰던 방법이지만 기계 n 대로 나누어서 하지 말라는 법은 없겠지요.
CPU보다는 disk IO가 더 중요한 요소가 되니 다른 기계에서 돌리는 것이 좀 더 빠른 결과를 줄 수도 있겠다는 생각이 들지만...
아무튼 앞으로는 데이타의 양이 더 많아져서 파일의 크기가 40G 이상
100G 까지도 가능할 것 같은데 3박 4일동안 정렬만 할 수도 없고 해서
정렬 프로그램을 하나 만들던가 아님 어디서 구하던가 해야 될 것 같은데
다른 분들은 이런 상황이라면 어떻게 처리를 하실 건가요?
알고리듬도 좋지만 시스템 업그레드가 필요할 것 같네요.
jinyedge wrote:
그리고 어쩌면 단순히 하드웨어의 사양을 높이는 것만으로도 가능할 것도
같은데 40G 정도의 텍스트 파일을 1시간 내에 정렬을 하려면 어느 정도
의 시스템이 필요할까요? 예를 들자면 제온 2.4 듀얼에 스카시 320 정도를
쓴다면 그냥 운영체제에 포함된 sort 프로그램으로도 가능할까요?
테스트가 필요하겠죠. 테스트 해 보고 결과를 알려 주시면 참 도움이 되겠네요.
sort 프로그램을 쓴다면 파일이 크면 임시 디렉토리에 파일을 만들 것입니다.
그러니 임시 디렉토리를 성능이 좋은 하드로 설정하면 아주 간단히 성능을
올릴 수 있지 않을까 합니다. 결국 업그레이드가 가장 편한 방법이겠네요.
(Disk I/O를 개선하는 방향으로)
프로그램을 고친다면 mmap 을 쓰면 도움이 되지 않을까 생각합니다.
메모리가 아무리 커도 파일을 따라 갈 수는 없을 테니 결국 paging이 일어나
니까 swap 디바이스도 성능 좋은 하드에 잡아 주는 것이 좋겠네요.
그럼 건투를.
sort로 처리할 수 있다면 한 줄에 한 단어씩인가 보네요. 기존 방법으로 빠르게 처리하려면... 글자 구성에 따라 다르겠지만, 가령 맨 앞자가 0-9까지만 있다면
for i in 0 1 2 3 4 5 6 7 8 9
do
grep "^$i" orig.txt | sort > tmp.$i
done
cat tmp.[0-9] > sorted.txt
와 같이 가장 앞 1-2바이트 단위로 나누어서 정렬하고
다시 합치면 됩니다. radix sort같은 external sort가
이런 식으로 됩니다. 더 복잡하게 만들수도 있지만
일정 환경 이내라면... 앞문자가 임의의 글자가 나온다면
분류해 주는 간단한 프로그램을 작성해 주셔도 되겠네요. 특정 문자로 시작하는 것만 많다면 그 다음 글자로
분류하셔도 될 겁니다.
텍스트 파일의 구성에 대해서 간략하게 설명하신다면 좀 더 나은 아이디어가
텍스트 파일의 구성에 대해서 간략하게 설명하신다면 좀 더 나은 아이디어가 나오지 않을까 합니다.
Re: 대용량 텍스트 파일의 정렬 방법?
GNU textutil의 sort 소스를 보니
Symmetric Multi Processing (SMP)에 대해서
잇점은 없습니다.
하드웨어적으로 해결을 본다면,
듀얼 CPU보다는 단일의 빠른 클럭의 CPU와 큰 램, 그리고 빠른 하드(RAID-0 mode의 하드array면 더 낳을 듯.)가 더 효과적일 것 같습니다.
만약 SMP에서 이득을 볼려면,
별도록 작성하셔야 할 것 같습니다.
윈도우쪽은 소스를 볼수가 없어서 모르겠습니다.
There is no spoon. Neo from the Matrix 1999.
일단 text파일이 일종의 log로 보이는데..갱신되는 부분을 대상으
일단 text파일이 일종의 log로 보이는데..
갱신되는 부분을 대상으로만 sort하여..
기존의 sort 결과물과 병합할 수 있는
방법을 모색하던가,
아니면, Berkeley DB 등과 같이
가볍고 속도빠른 db를 이용해서 관리하는 것도
방법을 일것 같습니다.(이경우는 smp의 이득을 볼수 있습니다.)
There is no spoon. Neo from the Matrix 1999.
대용량의 소팅에 cpu 성능의 영향은 아주 미미합니다.램에 담아서 소
대용량의 소팅에 cpu 성능의 영향은 아주 미미합니다.
램에 담아서 소팅할 수 없는 자료들을 소팅할때는 소팅시간의
95% 이상이 디스크 IO 시간이기때문에 디스크 IO를 줄이는게
소팅시간을 줄이는 거라고 생각하면 정답이죠.
그리고 이런건 이미 많은 사람들이 고민 했기 때문에 우리가 고민할 필요 없습니다. 좋은 알고리즘들이 이미 있다는거져.
정렬은 내부정렬과 외부정렬로 나뉘는데 qsort 같은 함수야 당연히 퀵소팅으로
구현된거니 내부정렬이라서 40G 자료의 소팅에는 맞지 않는 함수이지요.
주메모리를 넘는 소팅은 외부정렬이므로 거기에 걸맞는 알고리즘을 사용하시면
보다 좋은 포퍼먼스를 얻으실 수 있을 듯 하네요.
http://hjunki.hihome.com/programming/algorithm/sort.html
여기에 소팅 알고리즘에 대한 리스트가 있으니 가셔서 외부정렬쪽을 보시고
맘에 드시는거 하나 골라 잡으시면 되겠네요.
배보다 배꼽이 더 큰 방법이 될지도 모른다는 생각이 들지만... 혹시 가
배보다 배꼽이 더 큰 방법이 될지도 모른다는 생각이 들지만... 혹시 가용한 기계가 몇대 있다면, NFS 로 잘 뜯어맞춰서, 로그를 기계별로 적당히 분배한 다음 머지하는 방법도 괜찮지 않을까요. 머지소트 따위.... 테입에서 쓰던 방법이지만 기계 n 대로 나누어서 하지 말라는 법은 없겠지요.
CPU보다는 disk IO가 더 중요한 요소가 되니 다른 기계에서 돌리는 것이 좀 더 빠른 결과를 줄 수도 있겠다는 생각이 들지만...
저도 궁금해지네요. 혹시 나중에 성공하시면 리포팅을 한번 해주시면 어떨까요.
분산 처리라면 bitonic sort도 괜찮지 않을까 싶네요.그냥
분산 처리라면 bitonic sort도 괜찮지 않을까 싶네요.
그냥 제 생각 .. -_-a ( complexity가 기억이 잘 .. )
잡담:)
DB의 KEY로 잡고 SORT를 하면 어떨까 생각해봤는데
그냥 sort 보다 훨씬 느리겠군요 -_-;
Re: 대용량 텍스트 파일의 정렬 방법?
http://www.nist.gov/dads/HTML/distributionSort.html
이런 알고리듬을 말하는 것 같네요.
알고리듬도 좋지만 시스템 업그레드가 필요할 것 같네요.
테스트가 필요하겠죠. 테스트 해 보고 결과를 알려 주시면 참 도움이 되겠네요.
sort 프로그램을 쓴다면 파일이 크면 임시 디렉토리에 파일을 만들 것입니다.
그러니 임시 디렉토리를 성능이 좋은 하드로 설정하면 아주 간단히 성능을
올릴 수 있지 않을까 합니다. 결국 업그레이드가 가장 편한 방법이겠네요.
(Disk I/O를 개선하는 방향으로)
프로그램을 고친다면 mmap 을 쓰면 도움이 되지 않을까 생각합니다.
메모리가 아무리 커도 파일을 따라 갈 수는 없을 테니 결국 paging이 일어나
니까 swap 디바이스도 성능 좋은 하드에 잡아 주는 것이 좋겠네요.
그럼 건투를.
sort로 처리할 수 있다면 한 줄에 한 단어씩인가 보네요. 기존 방법으
sort로 처리할 수 있다면 한 줄에 한 단어씩인가 보네요. 기존 방법으로 빠르게 처리하려면... 글자 구성에 따라 다르겠지만, 가령 맨 앞자가 0-9까지만 있다면
와 같이 가장 앞 1-2바이트 단위로 나누어서 정렬하고
다시 합치면 됩니다. radix sort같은 external sort가
이런 식으로 됩니다. 더 복잡하게 만들수도 있지만
일정 환경 이내라면... 앞문자가 임의의 글자가 나온다면
분류해 주는 간단한 프로그램을 작성해 주셔도 되겠네요. 특정 문자로 시작하는 것만 많다면 그 다음 글자로
분류하셔도 될 겁니다.
--
익스펙토 페트로눔
^^;;
저는 예전에 정보검색시스템 만들면서;;;
했던건데... Cosequential Processing
일단 부분적으로 소팅을 합니다.
물론 메모리에 한번에 올라갈 만큼씩 잘라서했습니다.
그렇게 해서 저장했구요.
물론 메모리는 계속 재활용합니다. (저는 시스템 중간에 동적할당 하는것을 좋아하지 않거든요;)
그리고 나중에 합치는거죠.. 머지 소트처럼
근데 이걸 자료구조를 잘 만드신다면^^ 무쟈게 빠릅니다.
합칠때 약간만 생각해 주면 빠른 머지를 할수있죠.
파일처리 관련 책을 보면 Cosequential Processing 에 대해 나와있습니다^^
제가 잘못 짚은게 아닌가 싶네요~^^;;
-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com
1
1
댓글 달기