☰

*********** 갱신********

tag-icon • tag-icon bash awk performance sort
*********** 갱신********

많은 단어 목록에서 중복된 단어를 제거해야 합니다. 몇 가지 명령을 시도하고 조사를 했습니다.Linux에서 가장 빠른 "uniq" 도구그리고대용량 GB 텍스트 파일에서 중복 줄을 제거하는 방법은 무엇입니까?중복된 단어 목록을 제거하는 가장 빠른 방법은 를 사용하는 것 같다고 설명합니다 awk.

awk  --> O(n) ?
sort --> O(n log n) ?

그러나 나는 이것이 사실이 아닌 것 같다는 것을 알았다. 내 테스트 결과는 다음과 같습니다.

time sort -u input.txt -o output.txt 
real    0m12.446s  
user    0m11.347s  
sys 0m0.906s**


time awk '!x[$0]++' input.txt > output.txt
real    0m47.221s  
user    0m45.419s  
sys 0m1.260s

그래서 사용 sort -u속도가 3.7배 빨라졌습니다. 왜 이런거야? 중복 제거를 수행하는 더 빠른 방법이 있습니까?

*********** 갱신********

누군가 댓글에서 지적했듯이 어쩌면 내 단어 목록이 이미 어떤 방식으로 정렬되어 있을 수도 있습니다. 이러한 가능성을 배제하기 위해 다음을 사용하여 두 개의 단어 목록을 생성했습니다.난수 어휘 생성기.py.

List1 = 7 Mb  
List2 = 690 Mb

**Results AWK:**  
***List1***  
real    0m1.643s  
user    0m1.565s  
sys     0m0.062s

***List2***  
real    2m6.918s  
user    2m4.499s  
sys     0m1.345s

**Results SORT:**  
***List1***  
real    0m0.724s  
user    0m0.666s  
sys     0m0.048s

***List2***  
real    1m27.254s  
user    1m25.013s  
sys     0m1.251s

답변1

잘못된 질문을 하거나 잘못된 스택에 있는 경우 사람들이 awk 및 정렬에 사용되는 알고리즘을 기반으로 답변을 제공할 수 있도록 프로그래밍/스택 오버플로에서 질문하는 것이 더 좋습니다.

추신: nawk, mawk 및 gawk를 사용하여 원하는 작업을 수행하여 더 많은 "구역 지정" 세부 정보를 제공하고 최소, 최대, 평균 및 표준 편차를 사용하여 각각 100회 실행할 수도 있습니다.

어쨌든 CompSci 210의 현재 질문으로 돌아가면 사용된 알고리즘과 관련이 있습니다. Sort는 메모리가 부족할 때 병합 정렬을 허용하기 위해 크기 및 메모리 제한에 따라 다양한 방법을 사용하여 파일을 디스크의 임시 파일에 저장하며, 어떤 특정 sort(1) 명령이 작동하는지 확인하려면 소스 코드를 살펴봐야 합니다. 실행 중인 특정 OS에서 사용되지만 경험상 가능한 한 많이 메모리에 로드하고 빠른 정렬을 수행하고 디스크에 쓰고 중복 항목을 플러시한 다음 마지막에 수행됩니다. 작은 정렬 파일에 대한 병합 정렬. 따라서 여기서는 개별 부품에 대해 O(n*log2(N))을 얻은 다음 대략적인 O(n*log(n)) 병합 작업을 수행합니다.

awk:x[$0]++ 메커니즘은 해시 사용을 "가정"합니다. 그러나 해싱(O(1) "조회" 작업으로 가정)의 문제는 충돌과 그 처리입니다. 이로 인해 데이터가 잘 분산되지 않고 버킷이 채워지지 않을 때 문제가 발생할 수 있으며 큰 목록에서 충돌이 올바르게 처리되지 않으면 해싱이 큰 메모리 문제가 될 수 있습니다(예상 대상을 지정해야 할 수도 있음). 데이터 조정 해싱 알고리즘), 실제 해시 함수의 성능을 살펴봐야 합니다. 그러면 O(1)은 아마도 삽입을 위해 O(log(n))에 더 가까울 것입니다(즉, 첫 번째 검색의 경우 O(1)인 경우) 존재하지 않는 경우 O(log(n)))를 추가하면 n*O(1)은 *O(log(n))=> O(n*log(n))이 됩니다. , 당신이 "설명된" 방식으로 일을 하고 있다는 것은 말할 것도 없습니다 :)

답변2

몇 가지 심각한 스크립팅 언어(Python/Perl/Raku, 아마도 그런 종류 이후일 가능성이 높음)를 시작하기 전에 사용 방법을 알아내려고 노력할 것입니다 sort -u(아마도 추가 스위치가 있을 것입니다!). 다른 대안은 고려하지 않을 것입니다. 내가 필요할 때까지.

답변3

속도 차이는 "sort"가 명령이기 때문입니다(협회), "awk"는 프로그래밍 언어(협회).

"sort" 명령은 입력을 받아들이고 출력을 반환합니다. 그리고 "awk"는 코드(터미널 명령)를 먼저 해석한 다음 처리를 시작하는 프로그래밍 언어입니다. 그렇게 간단합니다.

관련 정보