使用 timeit 对算法进行计时,而没有对计时进行排序或设置
Using timeit to time algorithms without timing already sorted or setup
我正在尝试使用 timeit 为我已经实现的两个算法计时,但我需要构建一个图形对象并且不想对已经排序的图形进行排序(为了时间准确性)。
这是迄今为止我将设置与实际时间分开的最佳尝试。后来我想不带参数调用 ShortestPathAlgorithm()
并将 table 中的结果打印到 txt 文件中,所以我相信格式必须是这样的.一切都在 shortestPathAlgorithm
函数内完成。
任何人都可以给出任何关于如何在嵌套函数中完成所有这些的指示吗?
def shortestPathAlgorithms():
def MultipleRuns(numberOfRuns):
graph1 = ()
graph2 = ()
graph3 = ()
graph4 = ()
graph5 = ()
graph6 = ()
def setup():
# not timed global or nonlocal
nonlocal graph1
nonlocal graph2
nonlocal graph3
nonlocal graph4
nonlocal graph5
nonlocal graph6
graph1 = WeightedGraph(123, 2314, 2, 50)
graph2 = WeightedGraph(22, 1231, 2, 50)
graph3 = WeightedGraph(123, 12442, 2, 50)
graph4 = WeightedGraph(234, 2344, 2, 50)
graph5 = WeightedGraph(33, 123, 1, 50)
graph6 = WeightedGraph(1245, 53456, 1, 50)
def thingToTime():
# variables either global or nonlocal
# whether this is nested inside another function.
# nonlocal if inside another function
nonlocal graph1
nonlocal graph2
nonlocal graph3
nonlocal graph4
nonlocal graph5
nonlocal graph6
graph1.bellmanFord(0)
graph1.dijkstra(0)
graph2.bellmanFord(0)
graph2.dijkstra(0)
graph3.bellmanFord(0)
graph3.dijkstra(0)
graph4.bellmanFord(0)
graph4.dijkstra(0)
graph5.bellmanFord(0)
graph5.dijkstra(0)
graph6.bellmanFord(0)
graph6.dijkstra(0)
t = timeit(thingToTime, setup=setup, number=numberOfRuns)
print("sort " + str(numberofRuns) + " times (in seconds):", t)
print("average:{0:.5f}".format(t / numberofRuns))
你的理解是正确的。但是,有一些问题可以改进。
首先,您通常希望一次只测量一种算法。如果您分别测量每个算法,您可以比较两者并获得更准确的数据。此外,我会坚持在同一张图表上多次测量它,然后平均时间以获得更准确的时间(您可以使用 copy.deepcopy()
来复制图表)。然后对您拥有的每个图表执行此操作。由于每种算法在不同类型的图上可能更有效(如果按照您的建议进行测量,您将完全丢失此信息)。
其次,由于 timeit
可以多次重复测量操作,但设置仅在任何测量开始前完成一次 (see the docs),您将测量已经遍历的算法(或 sorted 如你所说)图表。您正确地指出了这一点。
作为解决方案,我建议使用 time.perf_counter_ns()
手动计时运行。用于测量 bellmanFord 算法的代码可能如下所示:
import time
import copy
"""
Measures bellman ford algorithm ran on a *graph* *repetitions* number of times.
Returns time measured
"""
def measure_bellman_ford(repetitions, graph):
graphs = [copy.deepcopy(graph) for x in range(repetitions)]
# make measurements
start = time.perf_counter_ns()
for idx in range(repetitions):
graphs[idx].bellmanFord(0)
end = time.perf_counter_ns()
return (end - start) / repetitions
我正在尝试使用 timeit 为我已经实现的两个算法计时,但我需要构建一个图形对象并且不想对已经排序的图形进行排序(为了时间准确性)。
这是迄今为止我将设置与实际时间分开的最佳尝试。后来我想不带参数调用 ShortestPathAlgorithm()
并将 table 中的结果打印到 txt 文件中,所以我相信格式必须是这样的.一切都在 shortestPathAlgorithm
函数内完成。
任何人都可以给出任何关于如何在嵌套函数中完成所有这些的指示吗?
def shortestPathAlgorithms():
def MultipleRuns(numberOfRuns):
graph1 = ()
graph2 = ()
graph3 = ()
graph4 = ()
graph5 = ()
graph6 = ()
def setup():
# not timed global or nonlocal
nonlocal graph1
nonlocal graph2
nonlocal graph3
nonlocal graph4
nonlocal graph5
nonlocal graph6
graph1 = WeightedGraph(123, 2314, 2, 50)
graph2 = WeightedGraph(22, 1231, 2, 50)
graph3 = WeightedGraph(123, 12442, 2, 50)
graph4 = WeightedGraph(234, 2344, 2, 50)
graph5 = WeightedGraph(33, 123, 1, 50)
graph6 = WeightedGraph(1245, 53456, 1, 50)
def thingToTime():
# variables either global or nonlocal
# whether this is nested inside another function.
# nonlocal if inside another function
nonlocal graph1
nonlocal graph2
nonlocal graph3
nonlocal graph4
nonlocal graph5
nonlocal graph6
graph1.bellmanFord(0)
graph1.dijkstra(0)
graph2.bellmanFord(0)
graph2.dijkstra(0)
graph3.bellmanFord(0)
graph3.dijkstra(0)
graph4.bellmanFord(0)
graph4.dijkstra(0)
graph5.bellmanFord(0)
graph5.dijkstra(0)
graph6.bellmanFord(0)
graph6.dijkstra(0)
t = timeit(thingToTime, setup=setup, number=numberOfRuns)
print("sort " + str(numberofRuns) + " times (in seconds):", t)
print("average:{0:.5f}".format(t / numberofRuns))
你的理解是正确的。但是,有一些问题可以改进。
首先,您通常希望一次只测量一种算法。如果您分别测量每个算法,您可以比较两者并获得更准确的数据。此外,我会坚持在同一张图表上多次测量它,然后平均时间以获得更准确的时间(您可以使用 copy.deepcopy()
来复制图表)。然后对您拥有的每个图表执行此操作。由于每种算法在不同类型的图上可能更有效(如果按照您的建议进行测量,您将完全丢失此信息)。
其次,由于 timeit
可以多次重复测量操作,但设置仅在任何测量开始前完成一次 (see the docs),您将测量已经遍历的算法(或 sorted 如你所说)图表。您正确地指出了这一点。
作为解决方案,我建议使用 time.perf_counter_ns()
手动计时运行。用于测量 bellmanFord 算法的代码可能如下所示:
import time
import copy
"""
Measures bellman ford algorithm ran on a *graph* *repetitions* number of times.
Returns time measured
"""
def measure_bellman_ford(repetitions, graph):
graphs = [copy.deepcopy(graph) for x in range(repetitions)]
# make measurements
start = time.perf_counter_ns()
for idx in range(repetitions):
graphs[idx].bellmanFord(0)
end = time.perf_counter_ns()
return (end - start) / repetitions