funmark를 사용하여 Python 함수 벤치마크 및 결과 플롯

블로그를 시작하기 전에 저는 이것이 제 첫 번째 PyPI 패키지이고 아직 개발 단계에 있다고 말하고 싶었습니다. 누군가 흥미를 느낀다면 GitHub에서 funmark를 확인하십시오.

Funmark는 함수 벤치마킹에 사용할 수 있고 그래프 플롯을 사용하여 런타임 및 메모리 소비를 분석/비교하는 데 사용할 수 있는 Python 패키지입니다.

이 블로그에서는 내 funmark 패키지를 사용하여 주로 정렬 기능을 벤치마킹할 것입니다.

퀵소트

병합정렬

팀소트

랜덤 배열을 만들기 위해 먼저 funmark와 random.randint()를 가져오는 것으로 시작하겠습니다.

import funmark
from random import randint

각 정렬 방법에 대한 함수를 만들어 봅시다

퀵소트

def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 
    for j in range(low , high): 
        if   arr[j] < pivot: 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

def quickSort(argv): 
    arr = argv[0]
    low = argv[1]
    high = argv[2]
    if low < high: 
        pi = partition(arr,low,high) 
        quickSort([arr, low, pi-1]) 
        quickSort([arr, pi+1, high]) 

병합 정렬

def mergeList(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
    L = [0] * (n1) 
    R = [0] * (n2) 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 
    i = 0     
    j = 0 
    k = l     
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1

def mergeSort(argv):
    arr = argv[0]
    l = argv[1]
    r = argv[2]
    if l < r: 
        m = (l+(r-1))//2 
        mergeSort([arr, l, m]) 
        mergeSort([arr, m+1, r]) 
        mergeList(arr, l, m, r) 

팀 정렬

def timSort(argv):
    ar = argv[0]
    ar.sort()
    return ar

위 기능 벤치마킹

funmark.Benchmark() 각 함수에 대한 개체를 만들 수 있습니다.

merge = funmark.Benchmark()
quick = funmark.Benchmark()
tim = funmark.Benchmark()

이제 크기의 임의 배열을 만들 수 있습니다.

listSize = 10
maxSize = 10**6
while listSize < maxSize:
    ar = [randint(1,10**5) for listSize in range(listSize)]

    time, memory = merge.run(quickSort, ar, 0, len(ar)-1)
    merge.add(len(ar), time, memory)

    time, memory= quick.run(mergeSort, ar, 0, len(ar)-1)
    quick.add(len(ar), time, memory)

    time, memory = tim.run(timSort, ar)
    tim.add(len(ar), time, memory)

    listSize = int(2*listSize)

각 함수에 대해 .run(function Name, parameter)을 실행하여 런타임 및 메모리 사용량을 가져온 다음 .add(size, time, memory)를 사용하여 각 개체에 저장합니다.
while 루프의 마지막 줄에서 listSize의 크기를 늘려 다양한 크기의 목록에 대해 이러한 값을 얻을 수 있도록 합니다.

비교 그래프 플로팅

merge.compareTime("Length", "Time", "Compression between Sorting Algorithms", quick, tim)

여기에 병합을 사용하여 시간 그래프를 플로팅하고 있으며, 모두 함께 플로팅하기 위해 quick 및 tim을 전달합니다. 여기 이 라인의 결과가 있습니다.



보시다시피 QuickSort는 MergeSort보다 최악의 경우 시간 복잡성이 더 크지만 평균적인 경우는 다음과 같은 이유로 훨씬 낫습니다.

보조 공간: Quicksort는 내부 정렬 알고리즘입니다. 반면 병합 정렬은 정렬된 배열을 병합하기 위해 임시 배열이 필요하므로 제자리에 있지 않습니다.

최악의 경우: 무작위 퀵 정렬을 사용하면 퀵 정렬 O(n^2)의 최악의 경우를 피할 수 있습니다. 올바른 피벗을 선택하면 높은 확률로 쉽게 피할 수 있습니다.

참조 지역성: 특히 Quicksort는 캐시 지역성이 우수하여 가상 메모리 환경과 같은 많은 경우 병합 정렬보다 빠릅니다.

꼬리 재귀: QuickSort는 꼬리 재귀이지만 병합 정렬은 그렇지 않습니다. 꼬리 재귀 함수는 재귀 호출이 함수에 의해 마지막으로 실행되는 함수입니다. 실행 전에 컴파일러에 의해 최적화될 수 있으므로 꼬리가 아닌 재귀 함수보다 나은 것으로 간주됩니다.

그리고 Tim Sort는 예상한 것보다 훨씬 더 나은 성능을 발휘하므로 일반 정렬이 필요한 한 Python의 빌드 내 .sort() 메서드를 사용하는 것이 좋습니다.

merge.compareMemory("Length", "Time", "Compression between Sorting Algorithms", quick, tim)

여기에서는 mergeSort를 사용하여 메모리 그래프를 플로팅하고 quickSort 및 timSort를 전달하여 모두 함께 플로팅합니다. 다음은 이 라인의 결과입니다.



QuickSort에 대한 플롯은 TimSort 플롯 바로 아래에 있으므로 이 플롯에서 명확하게 볼 수 없지만 여기에서 MergeSort에는 추가 공간이 필요하지만 QuickSort 및 TimSort에는 필요하지 않다는 것을 이해할 수 있습니다!

이것은 정렬 알고리즘에 대한 단순한 분석일 뿐이지만 funmark는 함수로 작성될 수 있는 모든 파이썬 코드에 대한 벤치마크 및 분석을 수행하는 데 사용할 수 있습니다.

이 라이브러리가 할 수 있는 일이 마음에 들면 github에서 확인하고 기여하고 싶다면 별표를 표시하고 이슈 탭을 살펴보십시오!