Время выполнения рекурсивной функции с использованием библиотеки datetime в python - PullRequest
Новая
       17

Время выполнения рекурсивной функции с использованием библиотеки datetime в python

0 голосов
/ 26 марта 2019

У меня в Python есть 2 функции для сортировки списка, используя quicksort

import datetime
def partition(arr, low, high):
    i = (low - 1)  # index of smaller element
    pivot = arr[high]  # pivot

    for j in range(low, high):

        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            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(arr, low, high):
    dt_started = datetime.datetime.utcnow()

    if low < high:
        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr, low, high)

        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    dt_ended = datetime.datetime.utcnow()

    total_time = (dt_ended - dt_started).total_seconds()

    return total_time

, где dt_started - время начала функции, а dt_ended - время окончания.Из моего main я вызываю функцию следующим образом: 

total_time=quickSort(arr,0,n-1)

, где arr - список, который я хочу отсортировать, а n - его размер.

Мой вопрос , вернет ли функция quickSort() правильное время выполнения, так как в функции также будет несколько рекурсивных вызовов.

1 Ответ

0 голосов
/ 26 марта 2019

Да, будет. Переменные являются локальными для функции (при каждом вызове), поэтому даже если вы вызываете функцию рекурсивно, они не перезаписываются.

Вы можете проверить это, вставив некоторую трассировку в код. Например, вы можете напечатать значения dt_started и dt_ended в своем коде (я не буду вдаваться в то, что делает сам код): 

def quickSort(arr, low, high):
    print '>> called quickSort'
    print '  low:', low
    print ' high:', high
    dt_started = datetime.datetime.utcnow()
    print 'dt_started:', dt_started
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    print '> other calls finished'
    print '  low:', low
    print ' high:', high
    print 'dt_started:', dt_started        
    dt_ended = datetime.datetime.utcnow()
    print '  dt_ended:', dt_ended
    total_time = (dt_ended - dt_started).total_seconds()
    return total_time

Запуск этой функции с небольшим массивом: 

In [4]: a = range(1,100)

In [5]: quickSort(a,0,1)
>> called quickSort
  low: 0
 high: 1
dt_started: 2019-03-26 14:59:41.840875
>> called quickSort
  low: 0
 high: 0
dt_started: 2019-03-26 14:59:41.840914
> other calls finished
  low: 0
 high: 0
dt_started: 2019-03-26 14:59:41.840914
  dt_ended: 2019-03-26 14:59:41.841138
>> called quickSort
  low: 2
 high: 1
dt_started: 2019-03-26 14:59:41.841253
> other calls finished
  low: 2
 high: 1
dt_started: 2019-03-26 14:59:41.841253
  dt_ended: 2019-03-26 14:59:41.841327
> other calls finished
  low: 0
 high: 1
dt_started: 2019-03-26 14:59:41.840875
  dt_ended: 2019-03-26 14:59:41.841370
Out[5]: 0.000495

Как видите, dt_started в конце звонков совпадает с первым. Он сохраняет значение, которое он имел при первом вызове, и общее вычисленное время будет правильным.

...