오늘의 Perl - 리스트 비교

입개발 챗방에서 떠들다가

"파일이 수백만개 있고, 파일리스트가 하나 있는데 이 파일리스트에 없는 파일을 지워야 한다" 라는 애환(?)을 듣고 재빨리 방법을 생각해 봤습니다.

우선 find 로 존재하는 파일리스트를 만들고 최종적으로 삭제할 파일리스트를 만들면 파일이고 뭐고 그냥 두개의 리스트를 비교하는 문제가 됩니다.

정리하자면

• list1.txt : 전체 파일 리스트
• list2.txt : 지우지 말아야할 파일 리스트

따라서 list1.txt 에는 있고 list2.txt 에는 없는 파일들을들 list3.txt 에 쓰면 됩니다.

• list3.txt 삭제할 파일 리스트

예전엔 이런 걸 밥먹듯이 했었는데

• 리스트가 100줄 근처 라면 그냥 grep 으로 해결합니다.

grep -vf list2.txt list1.txt > list3.txt

• 리스트가 10000줄 이하라면 정렬을 한 후 comm 이나 diff 를 이용합니다.

sort list1.txt > s_list1.txt
sort list2.txt > s_list2.txt
comm -23 s_list1.txt s_list2.txt

리스트가 수 만줄을 넘어가면 이 방법도 문제가 생기는데 , 그럴때 해시테이블을 사용합니다. 전 주로 perl 을 사용하죠

 perl -ne'BEGIN{$h{$_}++for`cat list2.txt`}print unless $h{$_}' list1.txt > list3.txt

1000 만줄 정도 테스트했더니 10초 걸립니다.

그런데 문제가 하나 있습니다.
헤시 테이블은 메모리를 사용하는데 1000만줄 list1.txt 에 700만줄 list2.txt 를 사용했더니 메모리를 무려 1.5GiB 나 먹습니다.
전 각 줄에 숫자를 사용했는데 파일 경로처럼 더 긴 문자열이면 심각한 문제가 생길 수 있습니다.

몇가지 해결책을 찾을 수 있을 것 같은데 제가 생각한 가장 간단한 방법은 이렇습니다.
list1.txt 에 있고 list2.txt 에 없는 파일을 찾는 것이니까, list2.txt 를 여러 파일로 나눈 후 여러번 필터링을 해도 같은 효과가 납니다. 디스크 IO 가 늘어나고 좀 더 느려지겠지만요.
코드는 간단합니다.

# 먼저 list2.txt 를 백만줄 단위로 나눕니다.
split -l 1000000 list2.txt
# list 1 의 임시파일을 만듭니다.
cp list1.txt tmp.txt
# 나누어진 list2.txt 에 대해 각각 시행합니다.
ls x* | while read x;do
  perl -ne'BEGIN{$h{$_}++for`cat '$x'`}print unless $h{$_}' tmp.txt > ${x}.txt
  mv ${x}.txt tmp.txt
done
mv tmp.txt list3.txt
rm x*

타다~

이제 메모리는 250MiB 정도이고 시간은 25초 가량 걸리네요.