파이썬에서 목록 정렬하기

Python에서 목록을 정렬하는 일반적인 방법은 최소한 두 가지가 있습니다.

새 목록을 반환하는 sorted 함수 포함

목록을 제자리에서 수정하는 list.sort 메서드 사용

어느 것이 더 빠릅니까? 알아 보자!

sorted() 대 list.sort()

무작위로 섞인 1,000,000개의 정수 목록으로 시작하겠습니다. 나중에 순서가 중요한지 저도 확인하겠습니다.

# sorting.py
from random import sample

# List of 1 000 000 integers randomly shuffled
MILLION_RANDOM_NUMBERS = sample(range(1_000_000), 1_000_000)

def test_sort():
    random_list = MILLION_RANDOM_NUMBERS[:]
    return random_list.sort()

def test_sorted():
    random_list = MILLION_RANDOM_NUMBERS[:]
    return sorted(random_list)

$ python -m timeit -s "from sorting import test_sort" "test_sort()"
1 loop, best of 5: 352 msec per loop

$ python -m timeit -s "from sorting import test_sorted" "test_sorted()"
1 loop, best of 5: 385 msec per loop

sorted는 10% 미만입니다(385/352≈1.094). 하나의 루프만 실행하기 때문에 정확한 숫자는 신뢰할 수 없습니다. 나는 같은 테스트를 몇 번 더 반복했고 결과는 매번 약간씩 달랐다. sort는 약 345-355msec가 소요되었고 sorted는 약 379-394msec가 소요되었습니다(그러나 항상 sort보다 느림). 이 차이는 대부분 sorted가 새 목록을 생성한다는 사실에서 비롯됩니다.

각 테스트에서 원본 목록의 복사본을 만드는 이유는 무엇입니까? 글쎄, 이 기사의 원본 버전에서 나는 이것을 하는 것을 잊었고 완전히 잘못된 벤치마크로 끝났습니다. sort는 정렬된 목록에서 실행되고 있었고(timeit의 첫 번째 반복이 정렬했기 때문에) sorted는 임의의 목록에서 실행되었습니다. 전체 설명은 original post 에서 볼 수 있습니다.

초기 주문 문제

초기 목록이 이미 정렬되어 있으면 어떻게 됩니까?

MILLION_NUMBERS = list(range(1_000_000))

$ python -m timeit -s "from sorting import test_sort" "test_sort()"
20 loops, best of 5: 12.1 msec per loop

$ python -m timeit -s "from sorting import test_sorted" "test_sorted()"
20 loops, best of 5: 16.6 msec per loop

이제 정렬 시간이 훨씬 줄어들고 sort와 sorted의 차이가 37%(16.6/12.1≈1.372)로 늘어납니다. 이번에는 sorted가 37% 느린 이유는 무엇입니까? 음, 새 목록을 만드는 데는 이전과 같은 시간이 걸립니다. 그리고 정렬에 소요되는 시간이 줄어들었기 때문에 새 목록을 만드는 데 따른 영향이 더 커졌습니다.

그리고 내림차순으로 정렬된 1,000,000개의 숫자 목록을 정렬하려고 하면:

DESCENDING_MILLION_NUMBERS = list(range(1_000_000, 0, -1))

$ python -m timeit -s "from sorting import test_sort" "test_sort()"
20 loops, best of 5: 11.7 msec per loop

$ python -m timeit -s "from sorting import test_sorted" "test_sorted()"
20 loops, best of 5: 18.1 msec per loop

결과는 이전과 거의 동일합니다. 정렬 알고리즘은 내림차순 목록에 대한 정렬 프로세스를 최적화하기에 충분히 영리합니다.

마지막 테스트를 위해 100,000개의 요소가 섞이고 나머지는 순서가 지정된 1,000,000개의 숫자를 정렬해 보겠습니다.

# 10% of numbers are random
MILLION_SLIGHTLY_RANDOM_NUMBERS = [*range(900_000), *sample(range(1_000_000), 100_000)]

$ python -m timeit -s "from sorting import test_sort" "test_sort()"
5 loops, best of 5: 61.2 msec per loop

$ python -m timeit -s "from sorting import test_sorted" "test_sorted()"
5 loops, best of 5: 71 msec per loop

입력 목록이 더 복잡해지면 두 기능 모두 느려집니다.
list.sort()를 사용하는 것이 내가 선호하는 목록 정렬 방법입니다. 새 목록을 생성하지 않아 시간과 메모리가 절약됩니다. 하지만 그건 양날의 검! 때때로 당신은 깨닫지 못한 채 실수로 초기 목록을 덮어쓸 수 있습니다(제가 초기 벤치마크에서 했던 것처럼 😅). 따라서 초기 목록의 순서를 유지하려면 대신 sorted를 사용해야 합니다. sorted는 모든 iterable과 함께 사용할 수 있지만 sort는 목록에서만 작동합니다. 세트를 정렬하려면 sorted가 유일한 솔루션입니다.

결론

sort 는 sorted 보다 약간 빠릅니다. 새 목록을 생성하지 않기 때문입니다. 그러나 다음과 같은 경우 여전히 sorted를 고수할 수 있습니다.

원본 목록을 수정하고 싶지 않습니다. sort는 제자리에서 정렬을 수행하므로 여기서는 사용할 수 없습니다.

목록이 아닌 다른 것을 정렬해야 합니다. sort는 목록에만 정의되어 있으므로 세트 또는 다른 항목 컬렉션을 정렬하려면 대신 sorted를 사용해야 합니다.

더 자세히 알아보려면 Python 설명서의 Sorting HOW TO 가이드에 유용한 정보가 많이 포함되어 있습니다.