Using timeit to time algorithms without timing already sorted or setup

Question

I am trying to use timeit to time two algorithms I have implemented, but I need to construct a graph object and don't want to sort graphs that are already sorted (for time accuracy).

This is the best attempt I have so far at separating the setup from the actual timing. Later I want to call ShortestPathAlgorithm() with no arguments and print the results in a table to a txt file, so I believe the format has to be something like this. With everything being completed inside the shortestPathAlgorithm Function.

Can anyone give any pointers on how to do all of this in the nested functions?

 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))

user_12007200 · Answer

Your understanding is correct. However, there are some issues that could be improved.

Firstly, you usually want to measure only one algorithm at a time. If you measure each algorithm separately you can compare the two and get more accurate data. Also, I would stick to measuring it on the same graph multiple times and then average the time to get one more accurate (you can use copy.deepcopy() to make duplicates of the graph). Then do this on each of the graphs you have. Since each algorithm may be more efficient on different types of graphs (you would lose this information completely if measured as you propose).

Secondly, since timeit can repeat the measured operation multiple times but the setup is done only once before any measurement starts (see the docs) you would measure the algorithm on already traversed (or sorted as you put it) graphs. Which you correctly point out.

As a solution, I suggest manually timing the runs using the time.perf_counter_ns(). The code for measuring the bellmanFord algorithm could look as such:

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

Using timeit to time algorithms without timing already sorted or setup

1 Answers