使用 timeit 对算法进行计时，而没有对计时进行排序或设置

Question

我正在尝试使用 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))

Answer 1

你的理解是正确的。但是，有一些问题可以改进。

首先，您通常希望一次只测量一种算法。如果您分别测量每个算法，您可以比较两者并获得更准确的数据。此外，我会坚持在同一张图表上多次测量它，然后平均时间以获得更准确的时间（您可以使用 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 对算法进行计时，而没有对计时进行排序或设置

Using timeit to time algorithms without timing already sorted or setup

python

python-3.x

timeit