用Python装饰器正确计时递归函数

Question

我正在编写一段代码进行学习，我想比较使用不同算法排序列表所需的时间。我尝试使用装饰器，但由于mergeSort函数是递归的，因此它会给出每个递归的结果。如果可能的话，我希望找到一种方法来总结结果。由于我对装饰器非常陌生，所以我不确定在这种情况下可以做什么。是否有一种方法可以使用装饰器实现这个目标？

import random
import functools
import time


def timeIt(func):
    @functools.wraps(func)
    def newfunc(*args, **kwargs):
        startTime = time.time()
        func(*args, **kwargs)
        elapsedTime = time.time() - startTime
        print('function [{}] finished in {} ms'.format(
            func.__name__, int(elapsedTime * 1000)))
    return newfunc


@timeIt
def mergeSort(L):
    if len(L) > 1:
        mid = len(L) // 2
        left = L[:mid] 
        right = L[mid:]
        mergeSort(left)
        mergeSort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                L[k] = left[i]
                i += 1
            else:
                L[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            L[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            L[k] = right[j]
            j += 1
            k += 1


@timeIt
def selectionSort(L):
    for fillslot in range(len(L) - 1, 0, -1):
        maxpos = 0
        for location in range(1, fillslot + 1):
            if L[location] > L[maxpos]:
                maxpos = location
        temp = L[fillslot]
        L[fillslot] = L[maxpos]
        L[maxpos] = temp


randomList = random.sample(range(10000), 10000)
mergeSort(randomList.copy())
selectionSort(randomList.copy())

输出：

[...] truncated
function [mergeSort] finished in 7 ms
function [mergeSort] finished in 15 ms
function [mergeSort] finished in 33 ms
function [mergeSort] finished in 68 ms
function [selectionSort] finished in 2049 ms

- Fabio Lopes

---

你可以编写一个专门调用mergeSort的函数，比如mergeSortObserver，并使用你的装饰器进行修饰。由于这个特殊函数只会被调用一次，所以你将得到期望的行为。 - Mickaël Bucas

Answer 1

你可以在包装函数上设置一个属性（例如示例中的_entered）作为标志，以便它能够判断自己是否在递归调用中，如果该属性被设置：

def timeIt(func):
    @functools.wraps(func)
    def newfunc(*args, **kwargs):
        if not hasattr(newfunc, '_entered'): # enter only if _entered is not set
            newfunc._entered = True # set _entered
            startTime = time.time()
            func(*args, **kwargs)
            elapsedTime = time.time() - startTime
            print('function [{}] finished in {} ms'.format(
                func.__name__, int(elapsedTime * 1000)))
            del newfunc._entered # remove _entered
    return newfunc

- blhsing

Answer 2

你可以简单地在它周围包裹另一个函数...

import random
import functools
import time


def timeIt(func):
    @functools.wraps(func)
    def newfunc(*args, **kwargs):
        startTime = time.time()
        func(*args, **kwargs)
        elapsedTime = time.time() - startTime
        print('function [{}] finished in {} ms'.format(
            func.__name__, int(elapsedTime * 1000)))
    return newfunc



def mergeSort(L):
    if len(L) > 1:
        mid = len(L) // 2
        left = L[:mid]
        right = L[mid:]
        mergeSort(left)
        mergeSort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                L[k] = left[i]
                i += 1
            else:
                L[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            L[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            L[k] = right[j]
            j += 1
            k += 1



def selectionSort(L):
    for fillslot in range(len(L) - 1, 0, -1):
        maxpos = 0
        for location in range(1, fillslot + 1):
            if L[location] > L[maxpos]:
                maxpos = location
        temp = L[fillslot]
        L[fillslot] = L[maxpos]
        L[maxpos] = temp


@timeIt
def timedSelectionSort(L):
    selectionSort(L)

@timeIt
def timedMergeSort(L):
    mergeSort(L)


randomList = random.sample(range(10000), 10000)
timedSelectionSort(randomList.copy())
timedMergeSort(randomList.copy())

- Boomer