많은 단어 목록에서 중복된 단어를 제거해야 합니다. 몇 가지 명령을 시도하고 조사를 했습니다.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(아마도 추가 스위치가 있을 것입니다!). 다른 대안은 고려하지 않을 것입니다. 내가 필요할 때까지.