Как можно засечь время выполнения каждой из функций и суммарное время выполнения программы
1,00
р.
Есть код с тремя сотрировками, есть отчет о времени выполнения программы. Как можно засечь время выполнения каждой из функций и суммарное время выполнения программы. Еще, если не сложно, посоветуйте как сократить программу.
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))
Ответ
Чтобы измерить время выполнения программы, можно 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 позволяет построчно сравнение производить.
Есть множество других профайлеров, например, py-spy, scalene. С Python 3.12 есть специальная поддержка для Linux perf.
Содержание:
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)'
Тот же интерфейс предоставляет pyperf модуль (помимо прочего):
$ python -m pyperf timeit -s '...' 'sorted(L)'
Документация утверждает, что pyperf более надёжные результаты выдаёт.
Для интерактивной работы можно %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.
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))
Ответ
Чтобы измерить время выполнения программы, можно 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 позволяет построчно сравнение производить.
Есть множество других профайлеров, например, py-spy, scalene. С Python 3.12 есть специальная поддержка для Linux perf.
Содержание:
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)'
Тот же интерфейс предоставляет pyperf модуль (помимо прочего):
$ python -m pyperf timeit -s '...' 'sorted(L)'
Документация утверждает, что pyperf более надёжные результаты выдаёт.
Для интерактивной работы можно %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.
