대용량 텍스트 파일(1.5G)이 있습니다.
Linux에서 가장 빠르고 안정적인 도구가 무엇인지 알고 싶습니다.
나는 보통 다음을 사용합니다:
awk '!x[$0]++' file.txt
하지만 명령을 사용하면 htop메모리 사용량이 증가하는 것을 볼 수 있습니다.
대용량 파일의 경우 가장 빠르고 안정적인 것이 무엇인지 알고 싶습니다.
uniq?
sort?
sed?
awk?
왜?
답변1
각 솔루션의 작동 방식을 고려해 보겠습니다.
uniq이를 위해서는 파일이 이미 정렬되어 있어야 합니다. 그렇지 않은 경우 먼저 파이프를 통해 연결해야 합니다sort. 즉,sort전체 파일을 메모리로 읽고 순서를 변경한 다음(O(n log n)) 파이프에 써야 합니다. 의 작업은uniq입력의 인접한 라인만 비교하면 되므로 매우 저렴합니다.sort -u이것은 의 작업을 결합합니다sort | uniq. 이는 스크립트처럼 모든 고유한 입력을 메모리에 수집해야awk하지만 출력을 생성하기 전에 이를 정렬하는 데 시간도 낭비합니다. 이는 입니다O(n log n). 단, 이 경우에는n모든 입력이 아니라 고유 항목의 개수입니다. 그래서 파이프보다 낫습니다.sedsed나는 이것을 수행하는 좋은 방법을 전혀 생각할 수 없기 때문에 왜 이것을 나열했는지 잘 모르겠습니다 . 아마도 먼저 정렬하고 스크립트로 파이프하면sed인접한 줄을 비교할 수 있는 방법이 있을 것입니다. 따라서 가능한 한 효율적으로 수행하는 작업sed을 수행할 것입니다 .uniquniqawk이는 필요한 최소한의 작업만 수행하기 때문에 가장 좋습니다. 각 줄을 읽을 때 효율적인 해시 조회를 수행하여 해당 줄이 이미 메모리에 있는지 확인하고 고유한 줄만 해시 키로 저장하고 카운터를 값으로 저장합니다. (이전에 해당 줄이 없었다면 조건이 true이므로 해당 줄이 인쇄됩니다. 그렇지 않으면 그렇지 않습니다.) 이는O(n)시간과O(uniq n)메모리를 사용합니다.
모든 방법은 입력을 정렬하거나 중복 항목을 제거할 수 있도록 어떤 입력이 표시되었는지 추적하기 위해 상당한 양의 메모리를 사용합니다.
답변2
uniq나는 정렬된 목록에서도 gnu가 매우 느리게 보인다는 점을 지적하고 싶었습니다 .
방금 정렬된 파일 이름 목록에서 디렉터리 접두사 목록을 가져오려고 했습니다.
$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes
36.7GiB 0:07:41 [81.4MiB/s]
$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2
36.7GiB 0:03:14 [ 193MiB/s]
$ pv all_files | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3
36.7GiB 0:02:18 [ 270MiB/s]
sort -u는 uniq보다 두 배 빠른 것 같습니다. 이는 stdin에서 읽고 stdout에 쓰는 정렬이므로 아직 병렬화가 수행되는 것을 볼 수 없습니다. uniq가 목록을 정렬할 필요가 없기 때문에 정렬보다 훨씬 느린 이유를 모르겠습니다...
이 명령의 출력은 매우 작으며(중복 항목이 많음) 264kb에 불과하며 pv가 완료된 후 정렬이 즉시 종료됩니다.
명령의 순서를 바꿔도 동일한 속도가 유지됩니다. 여기에서는 디스크 액세스 및 캐시가 아닌 CPU 시간에 따라 흐름이 제한됩니다(RAM은 8GB만 있고 스왑은 사용되지 않습니다).
나는 이것을 gnu coreutils sort, uniq 및 gnu awk가 있는 fedora 31 시스템에서 실행하고 있습니다. 로케일이 en_US.UTF-8로 설정되었습니다.
업데이트, 이것이 꽤 흥미로웠기 때문에 몇 가지 테스트를 더 수행했습니다. 잘린 부분을 제거하고 파일이 잘 정렬되었는지 확인하겠습니다.
cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test
8.4분이 소요됩니다. 테스트 용량은 이제 7.9GB입니다.
파이프 대신 파일에서 이러한 도구를 실행해 보겠습니다. 이렇게 하면 이러한 도구가 다중 스레드 정렬과 같은 더 많은 최적화를 수행할 수 있습니다. 그리고 더 빠른 SSD에서도요.
sort가 메모리를 많이 차지한다는 사실을 눈치 채지 못할 수도 있습니다. 왜냐하면 tmpfs일 수 있고 RAM에 있을 /tmp의 임시 파일을 사용하여 영리한 트릭을 수행하기 때문입니다(/tmp보다 큰 파일을 정렬하면 공간이 부족해집니다). 문제가 있으므로 위 명령에 -T 플래그가 필요합니다.
$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps
$ time awk '!x[$0]++' test > /dev/null
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps
$ time uniq test > /dev/null
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps
그렇게 보인다귀하의 awk 솔루션은 이 3가지 중 가장 빠릅니다., 실제로 가장 적은 메모리를 사용합니다.
업데이트2 이제 더 간단한 로케일로
$ export LC_ALL=c
$ time sort -u test > /dev/null 1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k
$ time awk '!x[$0]++' test > /dev/null 1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps
$ time uniq test > /dev/null
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps
이 시간유니크가 경주에서 승리했습니다... Stéphane Chazelas가 주석에서 암시했듯이 로케일을 C로 설정하면 정렬 및 유니크가 훨씬 더 빨라집니다!
답변3
여기에 표시된 것처럼 sort가 가장 빠른 uniq 도구인 것 같습니다 -->큰 단어 목록에서 중복 항목을 삭제하는 가장 빠른 방법은 무엇입니까?