대용량 데이터 처리에 효율적인 방법..
글쓴이: toughguy / 작성시간: 화, 2007/06/05 - 12:21오후
안녕하세요~
대용량 파일이 2개가 존재 합니다.
FILE 1 = 약 200만개의 ID
FILE 2 = 약 50 만개의 ID
제가 할려는 작업은,
FILE 1 에 있는 ID와 FILE 2 에 있는 ID를 비교하여,
FILE 1 에 존재하는 ID중 FILE 2 에 존재하는 ID를 제외한 나머지 ID를 출력하려 합니다.
즉 FILE 2 에 존재하는 ID 를 FILE 1 에서 삭제하는 것이지요..
가능한한 빠른 방법으로 처리해 결과를 얻고 싶은데 쉽지 않네요..
단순 비교를 하면 약, 200만 * 50만 = 1조번의 연산..
1시간 이내 얻을 수 있는 좋은 방법이 없을까요..
현재 Python의 List를 이용해 돌려보고 있는데, 아무래도 몇시간(혹은 1일이상?) 걸릴듯 하네요 -_-
여러분의 조언을 구하고 싶습니다.
Forums:
꼭 프로그램으로 작성해야 하는 것이 아니라면...
일단 파일내에 ID만 있는 것으로 가정하고 아래와 같이 하시면 됩니다.
200만개면 아이디
200만개면 아이디 한개를 100byte로 가정하고 200MByte정도니까 메모리에 모두 올릴 수 있겠군요.
perl의 hash를 사용하면 NlnN의 시간으로 처리할 수 있습니다.
메모리에 모두 올릴 수 없다면 . 올릴 수 있는 만큼 일을 나누면 되고요.
예전에 100*1000만 정도의 매트릭스를 처리하는 일을 한적이 있었는데, 상황이 복잡해서 직접적인 답은 안되지만 파일 IO를 포함해서 12분 정도 걸렸던 것 같습니다.
파일처리
FILE 1 = 약 200만개의 ID
FILE 2 = 약 50 만개의 ID
file2의 50만개의 id가 모두 메모리에 올라 간다면?
file2를 모두 메모리에 올리고 file1에서 id하나씩 꺼내서 조회를 하면 될거 같습니다.
BUT file2의 50만개 id가 메모리에 모두 올라가지 않는다면?
올라가는 만큼씩 올려서 앞에 방법으로 처리하고 결과를 하나로 모으면 될거 같습니다.
연산 회수?
50만 id로 hash를 빌드 + 200만번 조회
아... 200만개는
아... 200만개는 메모리에 올릴 필요가 없군요..
다만 파일에서 하나씩 읽는것 보다는 메모리에 한꺼번에 올려놓고 읽는게 더 빠를겁니다.
200만개는 리스트에, 50만개는 해쉬에 넣으면 되겠군요.
갑자기 궁금해지는게 있는데. perl에서 for(){}로 큰 파일을 읽으면
파일이 아주 클경우 당연히 자동으로 나눠서 읽겠죠? 아마도.. 막연히 그럴 것 같습니다.
그냥 스왑을
그냥 스왑을 써버리는 군요 이런..
너무 오래 지닌거긴 하지만...
200만개의 파일을 메모리에 올린다 하더라도 결국 파일을 열고 마지막까지 읽어야 합니다.
그러한 부분은 os의 버퍼를 이용해서 효과적으로 읽겟지만 여전히 파일을 끝까지 다 읽어야 함은 변함이 없습니다.
따라서 파일을 끝까지 읽어 가는 도중에 모든 연산을 마치면 됩니다.
fd를 한번 열고 닫기 전까지 모든 엔트리는 다 읽혀 질것이기에 이것을 따로 메모리에 모두 담아야 할 필요는 없습니다.
이런경우
두 파일 모두 정렬 후
merge로 처리하세요.
我不知道
댓글을 남겨주신 모든분들께 감사드립니다.^^
윗글에 남겨주신 모든 방법으로 해보았는데요,
처음 남겨주신 fgrep 을 사용하지 상당히 빠른시간(수초) 내에 결과가 나오네요..
관심을 가져주신 모든분께 감사드립니다(__)
아..참고로.
python으로 돌려보았는데,
중간에 멈추어 버리네요..ㅡ.ㅡ;;
참고하세요.
--소스--
import os
import sys
if len(sys.argv) != 3:
print "usage: make_data_python.py < original Data > < delete Data >"
sys.exit()
os.system('date')
f = file(sys.argv[1])
f_1 = file(sys.argv[2])
f_write = open('result_total_python','w')
original_ID_list = f.readlines()
delete_ID_list = f_1.readlines()
flag=0
length_first = len(original_ID_list)
length_sec = len(delete_ID_list)
for i in range(length_first):
print "in"
for j in range(length_sec):
if original_ID_list[i] == delete_ID_list[j]:
print original_ID_list[i],"PASS!"
flag=1
break
if flag == 0:
f_write.writelines(original_ID_list[i])
print "write"
flag=0
f.close()
f_1.close()
os.system('date')
이렇게 만드려고
이렇게 만드려고 하신건가요?
import sys, os if len(sys.argv) != 3: print "usage: make_data_python.py < original Data > < delete Data >" sys.exit() os.system('date') f_write = open('result_total_python','w') for i in open(sys.argv[1]): print "in" for j in open(sys.argv[2]): if i == j: print i,"PASS!" break else: f_write.writelines(i) print "write" os.system('date')----
데스크탑 프로그래머를 꿈꾸는 임베디드 삽질러
DB 를
DB 를 이용해도되죠..
두파일 DB 에 로드하고..
not in 조건이나.. 마이너스 이용하는방법도..
----------------------------------------------------------------------------
C Library Development Project
----------------------------------------------------------------------------
트랜잭션이 필요하지 않는다면 굳이...
DB까지 쓸 필요는 없을듯 합니다.
ACID중 2가지만 필요해도 DBMS를 쓰면 될듯 싶네요. ^^
Hello World.
제가....
생각하기에는....
인덱싱을 만들면 좋을 것이라 생각하지만...
노력이 더 많이 들어가려나 -_-;;
일단 대용량 자료는 아니지만 매번 이런일을 하고 관리를 해야한다면...
Binary search tree 같은 걸 만들어 놓으면 편리하겠죠.
뭐 시간복잡도도 이정도 양이라면 그다지 고민하지 않아도 되구요.
DBMS 를
DBMS 를 이용한다는것이 굳이 프로그램을 짠다는 것은 아니기 때문에
강력 추천합니다.
위와 같은 상황에서 MySQL 을 쓴다면
create table a (seq int primary key not null, id varchar(200) not null, index (id));
create table b (seq int primary key not null, id varchar(200) not null, index (id));
load data infile 'a.txt' into a (id);
load data infile 'b.txt' into b (id);
(문법은 잘 기억이 안나서 틀릴수도 있습니다.)
여기까지 하는데 fgrep 보다는 조금 많은 노력이 들었지만,
이 이후로는 fgrep 보다 많은 일을 처리할 수 있겠지요.
놀면서 해도 수분내에 원하는 결과가 나올 것이라는것도 믿어 의심치 않습니다.
emerge money
http://wiki.kldp.org/wiki.php/GentooInstallSimple - 명령어도 몇개 안되요~
https://xenosi.de/
댓글 달기