Как можно засечь время выполнения каждой из функций и суммарное время выполнения программы

#python #python_3x #сортировка #производительность

Есть код с тремя сотрировками, есть отчет о времени выполнения программы.
Как можно засечь время выполнения каждой из функций и суммарное время выполнения
программы.
Еще, если не сложно, посоветуйте как сократить программу.

import numpy
import time
start_time = time.clock()
def selection(arrayToSort):
    a = arrayToSort
    for i in range(len(a)):
        idxMin = i
        for j in range(i+1, len(a)):
            if a[j] < a[idxMin]:
                idxMin = j
        tmp = a[idxMin]
        a[idxMin] = a[i]
        a[i] = tmp
    return a

def insertion(arrayToSort):
    a = arrayToSort
    for i in range(len(a)):
        v = a[i]
        j = i
        while (a[j-1] > v) and (j > 0):
            a[j] = a[j-1]
            j = j - 1
        a[j] = v
    return a

def bubble(arrayToSort):
    a = arrayToSort
    for i in range(len(a),0,-1):
        for j in range(1, i):
            if a[j-1] > a[j]:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp
    return a

ary = numpy.random.choice(100000, 100000, replace=False)
print (len(ary), ary[:5])
print (len(selection(ary)), selection(ary)[:5])
print (len(insertion(ary)), insertion(ary)[:5])
print (len(bubble(ary)), bubble(ary)[:5])
print ("{:g} s".format(time.clock() - start_time))

    

Ответы

Ответ 1

При желании можно слегка автоматизировать и визуализировать процесы замера времени:

import timeit
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
matplotlib.style.use('ggplot')

def selection(arrayToSort):
    a = arrayToSort.copy()
    for i in range(len(a)):
        idxMin = i
        for j in range(i+1, len(a)):
            if a[j] < a[idxMin]:
                idxMin = j
        tmp = a[idxMin]
        a[idxMin] = a[i]
        a[i] = tmp
    return a

def insertion(arrayToSort):
    a = arrayToSort.copy()
    for i in range(len(a)):
        v = a[i]
        j = i
        while (a[j-1] > v) and (j > 0):
            a[j] = a[j-1]
            j = j - 1
        a[j] = v
    return a

def bubble(arrayToSort):
    a = arrayToSort.copy()
    for i in range(len(a),0,-1):
        for j in range(1, i):
            if a[j-1] > a[j]:
                tmp = a[j-1]
                a[j-1] = a[j]
                a[j] = tmp
    return a

def np_sort(arrayToSort):
    a = arrayToSort.copy()
    return np.sort(a)

def py_sorted(arrayToSort):
    a = arrayToSort.copy()
    return sorted(a)

res = pd.DataFrame(
    index=['selection', 'insertion', 'bubble', 'py_sorted', 'np_sort'],
    columns=np.logspace(2, 5, 4).astype(int),
    dtype=float
)

for j in res.columns:
    a = np.random.choice(j, j, replace=False)
    for i in res.index:
        stmt = '{}(a)'.format(i)
        setp = 'from __main__ import a, {}'.format(i)
        print('processing [{}]\tarray size: {}'.format(i,j), end='')
        res.at[i, j] = timeit.timeit(stmt, setp, number=50)
        print('\t\ttiming:\t{}'.format(res.at[i, j]))
print(res)

plt.figure()
ax = res.T.plot(loglog=True, style='-o', figsize=(10,8))
ax.set_xlabel('array size')
ax.set_ylabel('time (sec)')
plt.savefig('c:/temp/result.png')


Результаты:

             100       1000       10000        100000
selection  0.002741  0.271356  26.972909  2717.141041
insertion  0.002278  0.258578  26.933399  2644.332910
bubble     0.005418  0.566870  62.634945  5881.305021
py_sorted  0.000066  0.000689   0.008864     0.112469
np_sort    0.000298  0.000313   0.001023     0.012551


result.png:


Ответ 2

Чтобы измерить время выполнения программы, можно time команду использовать (часто
встроена в shell):

$ time python -c 'import time; time.sleep(1)'
python -c 'import time; time.sleep(1)'  0.01s user 0.00s system 1% cpu 1.021 total


Если команда недоступна, её можно реализовать в Питоне.

Чтобы посмотреть сколько времени индивидуальные функции занимают, можно cProfile
модуль использовать:

$ python -m cProfile -s time your_module.py


В графическом виде результаты удобно в KCachegrind просматривать. Пример команд.
Больше вариантов: How can you profile a script?

line_profiler позволяет построчно сравнение производить.

Содержание:


timeit
reporttime.py
make-figures.py
reporttime + pandas




timeit

Чтобы измерить производительность отдельной функции, можно timeit модуль использовать:

$ python -m timeit -s 'from insertion_sort import sorted; L = list(range(10**5))'
'sorted(L)'


Тот же интерфейс предоставляет perf модуль (помимо прочего):

$ python -m perf timeit -s '...' 'sorted(L)'


Документация утверждает, что perf более надёжные результаты выдаёт.

Для интерактивной работы можно %timeit magic в ipython/jupyter notebook  использовать.



reporttime.py

Оптимизируя выполнение функции, стоит убедиться что она работает корректно (тесты),
что изменения действительно ускорили её работу (сравнение производительности). Для
этого можно pytest-benchmarkиспользовать.

Для удобства сравнения производительности нескольких алгоритмов, можно автоматически
соответствующие функции собрать по общему префиксу в имени (get_functions_with_prefix()).
К примеру, если функции в вопросе можно назвать: sorted_selection, sorted_insertion,
sorted_bubble и поместить в daedra.py файл:

#!/usr/bin/env python
import random
from reporttime import get_functions_with_prefix, measure
import daedra

funcs = get_functions_with_prefix('sorted_', module=daedra)
for comment, L in [
        ("all same", [1] * 10**3),
        ("range", list(range(10**3))),
        ("random", list(range(10**3)))]:
    if comment == "random":
        random.shuffle(L)
    measure(funcs, args=[L], comment=comment)


где reporttime.py. measure() функция измеряет производительность функций похожим
на python -mtimeit команду способом.

Результаты

name                  time  ratio comment
sorted_insertion  184 usec   1.00 all same
sorted_selection 55.9 msec 303.86 all same
sorted_bubble    59.4 msec 322.92 all same
name                  time  ratio comment
sorted_insertion  186 usec   1.00 range
sorted_selection 57.7 msec 309.44 range
sorted_bubble    60.8 msec 326.40 range
name                  time ratio comment
sorted_selection   58 msec  1.00 random
sorted_insertion 66.2 msec  1.14 random
sorted_bubble     119 msec  2.05 random


Таблица показывает, что на уже отсортированном вводе sorted_insertion() функция заметно
выигрывает (в этом случае линейное время для этой функции требуется по сравнению с
квадратичным для sorted_selection() и sorted_bubble()). Для случайного ввода, производительность
примерно одинаковая. sorted_bubble() хуже во всех вариантах.



make-figures.py

В качестве альтернативы можно декоратор использовать такой как @to_compare, чтобы
собрать функции для сравнения и адаптировать их для make-figures.py скрипта, который
измеряет производительность и строит графики. Пример.

Чтобы нарисовать время выполнения функций для разных вводов:

#!/usr/bin/env python
#file: plot_daedra.py
import random

def seq_range(n):
    return list(range(n))

def seq_random(n):
    L = seq_range(n)
    random.shuffle(L)
    return L

if __name__ == '__main__':
    import sys
    from subprocess import check_call

    import daedra
    from reporttime import get_functions_with_prefix

    # measure performance and plot it
    check_call(["make-figures.py"] + [
        "--sort-function=daedra." + f.__name__
        for f in get_functions_with_prefix('sorted_', module=daedra)
    ] + [
        "--sequence-creator=plot_daedra." + f.__name__
        for f in get_functions_with_prefix('seq_')
    ] + sys.argv[1:])


seq_range(), seq_random() задают два типа ввода (уже отсортированный и случайный
соответственно). Можно определить дополнительные типы, определив seq_*(n) функцию.
Пример запуска:

$ PYTHONPATH=. python plot_daedra.py --maxn 1024


PYTHONPATH=. используется, чтобы make-figures.py смог найти plot_daedra модуль (с
seq_range, seq_random функциями) в текущей директории. --maxn определяет наибольшее
n, которое в seq_(n) функции передаётся.

Результаты




Рисунки подтверждают, что sorted_insertion() показывает линейное поведение на отсортированном
вводе (seq_range=0,1,2,3,4,...,n-1). И квадратичное на случайном вводе (seq_random).
Коэффициент перед log2(N) показывает приближённо соответствующую степень в функции
роста алгоритма в зависимости от размера ввода:

|------------------------------+-------------------|
| Fitting polynom              | Function          |
|------------------------------+-------------------|
| 1.00  log2(N)   +  1.25e-015 | N                 |
| 2.00  log2(N)   +  5.31e-018 | N*N               |
| 1.19  log2(N)   +      1.116 | N*log2(N)         |
| 1.37  log2(N)   +      2.232 | N*log2(N)*log2(N) |




reporttime + pandas

Собрав результаты измерений времени выполнения функций сортировки из daedra.py (sorted_*())
для разных типов (уже отсортированный/случайный) и размеров ввода (длины от 1 до 100000):

import random
import daedra
from reporttime import get_functions_with_prefix, measure_func

times = {}  # (function name, input type, exp size) -> time it takes
for f in get_functions_with_prefix('sorted_', module=daedra):
    for N in range(6):
        for case, L in [
            ("range", list(range(10**N))),
            ("random", list(range(10**N)))]:
            if case == "random":
               random.shuffle(L)
            times[(f.__name__, case, N)] = measure_func(f, [L])


Удобно исследовать результаты интерактивно, используя pandas.DataFrame:

import pandas as pd

df = pd.DataFrame([dict(function=f, input=i, size=10**n, time=t)
                   for (f,i,n), t in times.items()])


К примеру, чтобы сравнить поведение функций на уже отсортированном вводе:



def plot_input(input):
    p = df[df.input==input].pivot(index='function', columns='size', values='time')
    p.T.plot(loglog=True, style='-o', title=input)  # same style as in @MaxU's answer
    return p

plot_input('range')




Поведение на случайном вводе:

plot_input('random')




Или сравнить поведение одной функции для разных типов ввода на одном графике:

p = df[df.function=='sorted_insertion'].pivot(index='input', columns='size', values='time')
p.T.plot(loglog=True, style='-o', title='sorted_insertion')




соответствующий jupyter notebook.


Ответ 3

import numpy
from timeit import default_timer as timer


start_time = timer()

#
# <Описание функций selection, insertion и bubble>
#

def python_sort(array_to_sort):
    array_to_sort.sort()


number = 10000
ary = numpy.random.choice(number, number, replace=False)
print(len(ary), ary[:5])
print()


def my_time_this(function):
    items = numpy.copy(ary)

    t = timer()
    function(items)
    elapsed = timer() - t

    print_format = "{:<15} {:.10f} secs. number: {}, first 5: {}"
    print(print_format.format(function.__name__, elapsed, len(items), items[:5]))


my_time_this(python_sort)
my_time_this(selection)
my_time_this(insertion)
my_time_this(bubble)

print()
print("Total elapsed: {:g} secs".format(timer() - start_time))


Консоль:

10000 [2961 2787 7118  974 7860]

python_sort     0.0004201819 secs. number: 10000, first 5: [0 1 2 3 4]
selection       11.4002999229 secs. number: 10000, first 5: [0 1 2 3 4]
insertion       11.0592371948 secs. number: 10000, first 5: [0 1 2 3 4]
bubble          24.4177592050 secs. number: 10000, first 5: [0 1 2 3 4]

Total elapsed: 46.8791 secs




Перед каждой сортировкой делал копию массива, т.к. после первой сортировки массив
стал бы отсортированным и это помешало бы адекватно оценить следующие алгоритмы сортировки