Linux에서 가장 빠른 "uniq" 도구

각 솔루션의 작동 방식을 고려해 보겠습니다.

• uniq이를 위해서는 파일이 이미 정렬되어 있어야 합니다. 그렇지 않은 경우 먼저 파이프를 통해 연결해야 합니다 sort. 즉, sort전체 파일을 메모리로 읽어 들여 재정렬( O(n log n))한 다음 파이프에 써야 합니다. uniq입력의 인접한 행만 비교하면 되므로 매우 저렴하게 작동합니다 .

• sort -u이것은 작업을 결합합니다 sort | uniq. 이는 스크립트처럼 모든 고유한 입력을 메모리에 수집해야 awk하지만 출력을 생성하기 전에 이를 정렬하는 데 시간도 낭비합니다. O(n log n)이 경우에는 n전체 입력 수가 아니라 고유 항목 수입니다. 그래서 파이프보다 낫습니다.

• sed나는 이것을 수행하는 좋은 방법을 생각할 수 없기 때문에 왜 이것을 나열했는지 모르겠습니다 sed. 아마도 먼저 정렬하고 sed스크립트에 파이프하면 인접한 행을 비교할 수 있는 방법이 있을 것입니다. 그래서 우리는 해야 할 일을 sed하고 , 가능한 한 효율적으로 일을 합니다.uniquniq

• awk이는 필요한 최소한의 작업만 수행하기 때문에 아마도 가장 좋습니다. 각 행을 읽을 때 효율적인 해시 조회를 수행하여 행이 이미 메모리에 있는지 확인하고 고유한 행만 해시 키로 저장하고 카운터를 값으로 저장합니다. (행이 이전에 존재하지 않았다면 조건이 true이므로 행이 인쇄됩니다. 그렇지 않으면 인쇄되지 않습니다.) 이는 O(n)시간과 O(uniq n)메모리를 차지합니다.

각 방법은 입력을 정렬하거나 중복 항목을 제거할 수 있도록 표시된 입력을 추적하기 위해 많은 메모리를 사용합니다.

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는 stdin에서 읽고 stdout에 쓰는 작업을 정렬하는 uniq보다 두 배나 많은 작업을 수행하는 것으로 보이므로 병렬화를 수행하는 것을 본 적이 없습니다. uniq가 목록을 정렬할 필요가 없기 때문에 왜 정렬보다 훨씬 느려야 하는지 모르겠습니다...

이 명령의 출력은 매우 작으며(중복 항목이 많음) 264kb에 불과하며 pv가 완료되자마자 정렬이 종료됩니다.

명령 순서를 변경해도 속도는 여전히 동일합니다. 여기서 프로세스는 디스크 액세스 및 캐시가 아닌 CPU 시간에 의해 제한됩니다(8GB RAM만 있고 스왑 영역은 사용되지 않습니다).

저는 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로 설정하면 정렬 및 유니크가 더 빨라집니다!

아래와 같이 sort가 가장 빠른 uniq 도구인 것 같습니다 -->큰 단어 목록에서 중복 항목을 제거하는 가장 빠른 방법은 무엇입니까?