coreutils가 Python보다 정렬 속도가 느린 이유는 무엇입니까?

이즈카르타의 리뷰답은 로케일별 비교입니다. 명령 sort은 환경에 표시된 로케일을 사용하고 Python은 기본적으로 바이트 순서 비교를 사용합니다. UTF-8 문자열을 비교하는 것은 바이트 문자열을 비교하는 것보다 어렵습니다.

$ time (LC_ALL=C sort <numbers.txt >s2.txt)
real    0m5.485s
user    0m14.028s
sys     0m0.404s

어떻게에 대한.

두 가지 구현 모두 C로 되어 있으므로 공평한 경쟁의 장입니다. 핵심 도구sort 확실히사용병합 정렬연산. 병합 정렬은 입력 크기에 대해 대수적으로 증가하는 고정된 수의 비교를 수행합니다.빅오(n 로그 n).

Python의 정렬은 고유한 하이브리드 병합/삽입 정렬을 사용합니다.팀 사우터, 이는 O(n)(아마도 이미 정렬된 목록에 있음)의 최상의 시나리오를 사용하여 다양한 수의 비교를 수행하지만 일반적으로 로그 정렬(논리적으로, 일반적인 경우에는 숫자가 더 나을 수 없음) 정렬입니다.

두 가지 서로 다른 로그 순위가 주어지면 일부 특정 데이터 세트에서는 하나가 다른 것보다 더 유리할 수 있습니다. 전통적인 병합 정렬은 변경되지 않으므로 데이터에 관계없이 동일한 작업을 수행하지만 예를 들어 퀵 정렬(로그 정렬)은 변경되어 일부 데이터에서는 더 나은 성능을 발휘하지만 다른 데이터에서는 성능이 좋지 않습니다.

그럼에도 불구하고 3번(또는 병렬화되었기 때문에 3번 이상 sort)은 꽤 크며, 여기에 디스크로 교체하는 것과 같은 몇 가지 우발적인 상황이 없는지 궁금합니다 sort( -T옵션은 그렇게 함을 의미하는 것 같습니다). 그러나 시스템 시간이 사용자 시간에 비해 낮다는 사실은 문제가 아니라는 것을 의미합니다.

실제 답변이라기보다는 추가적인 분석에 가깝지만, 정렬되는 데이터에 따라 달라지는 것 같습니다. 첫째, 기본 읽기:

$ printf "%s\n" {1..1000000} > numbers.txt

$ time python sort.py <numbers.txt >s1.txt
real    0m0.521s
user    0m0.216s
sys     0m0.100s

$ time sort <numbers.txt >s2.txt
real    0m3.708s
user    0m4.908s
sys     0m0.156s

좋아요, 파이썬은요많은서둘러요. 그러나 sortcoreutils에 숫자순으로 정렬하도록 지시하면 속도가 더 빨라질 수 있습니다.

$ time sort <numbers.txt >s2.txt 
real    0m3.743s
user    0m4.964s
sys     0m0.148s

$ time sort -n <numbers.txt >s2.txt 
real    0m0.733s
user    0m0.836s
sys     0m0.100s

그건많은더 빠르지만 Python이 여전히 큰 차이로 승리합니다. 이제 정렬되지 않은 100만 개의 숫자 목록을 사용하여 다시 시도해 보겠습니다.

$ sort -R numbers.txt > randomized.txt

$ time sort -n <randomized.txt >s2.txt 
real    0m1.493s
user    0m1.920s
sys     0m0.116s

$ time python sort.py <randomized.txt >s1.txt
real    0m2.652s
user    0m1.988s
sys     0m0.064s

coreutils는 sort -n정렬되지 않은 숫자 데이터에 대해 더 빠릅니다(비록 cmpPython 정렬 매개변수를 조정하여 더 빠르게 만들 수는 있지만). 이 플래그가 없으면 Coreutils는 sort여전히 훨씬 느려집니다 -n. 그렇다면 순수 숫자 대신 임의의 문자는 어떻습니까?

$ tr -dc 'A-Za-z0-9' </dev/urandom | head -c1000000 | 
    sed 's/./&\n/g' > random.txt

$ time sort  <random.txt >s2.txt 
real    0m2.487s
user    0m3.480s
sys     0m0.128s

$ time python sort.py  <random.txt >s2.txt 
real    0m1.314s
user    0m0.744s
sys     0m0.068s

Python은 여전히 ​​coreutils를 능가하지만 질문에 표시된 것보다 훨씬 작은 마진입니다. 놀랍게도 알파벳순으로만 표시된 데이터를 볼 때 여전히 더 빠릅니다.

$ tr -dc 'A-Za-z' </dev/urandom | head -c1000000 |
    sed 's/./&\n/g' > letters.txt

$ time sort   <letters.txt >s2.txt 
real    0m2.561s
user    0m3.684s
sys     0m0.100s

$ time python sort.py <letters.txt >s1.txt
real    0m1.297s
user    0m0.744s
sys     0m0.064s

또한 두 가지가 동일한 정렬된 출력을 생성하지 않는다는 점에 유의하는 것도 중요합니다.

$ echo -e "A\nB\na\nb\n-" | sort -n
-
a
A
b
B

$ echo -e "A\nB\na\nb\n-" | python sort.py 
-
A
B
a
b

이상하게도 이 --buffer-size옵션은 내 테스트에서 큰 차이를 가져오지 않은 것 같습니다. 어쨌든 아마도 goldilock의 답변에 언급된 다른 알고리즘 때문에 sort대부분의 경우 Python이 더 빠른 것 같지만수치GNU는 정렬되지 않은 숫자에서 ¹sort 만큼 이겼습니다 .

---

OP가있을 수 있습니다근본 원인을 찾았습니다그러나 완전성을 기하기 위해 최종 비교는 다음과 같습니다.

$ time LC_ALL=C sort   <letters.txt >s2.txt 
real    0m0.280s
user    0m0.512s
sys     0m0.084s


$ time LC_ALL=C python sort.py   <letters.txt >s2.txt 
real    0m0.493s
user    0m0.448s
sys     0m0.044s

---

^{1 나보다 Python을 더 잘 아는 사람은} _{정렬 방법을 지정하여 동일한 속도를 얻을 수 있는지 확인하기 위해 비틀기를 테스트해 보아야 합니다 .list.sort()}