9 Analyzing Program Runtime

We can use

from timeit import timeit

time = timeit('function(input)', number=1000, globals=globals())
print(f'time {time}')

Runtime Test Example

def push_and_pop(s: Stack) -> None:
    """Push and pop a single item onto <stack>.

    This is simply a helper for the main timing experiment.

    s.push(1)
    s.pop()
    """

if __name__ == '__main__':
    # Import the main timing function.
    from timeit import timeit

    # The stack sizes we want to try.
    STACK_SIZES = [1000, 10000, 100000, 1000000, 10000000]
    for stack_size in STACK_SIZES:

        # Uncomment the stack implementation that we want to time.
        stack = Stack()
        # stack = Stack2()

        # Bypass the Stack interface to create a stack of size <stack_size>.
        # This speeds up the experiment, but we know this violates encapsulation!
        stack._items = list(range(stack_size))

        # Call push_and_pop(stack) 1000 times, and store the time taken in <time>.
        # The globals=globals() is used for a technical reason that you can ignore.

        time = timeit('push_and_pop(stack)', number=1000, globals=globals())

        # Finally, report the result. The :>8 is used to right-align the stack size
        # when it's printed, leading to a more visually-pleasing report.

        print(f'Stack size {stack_size:>8}, time {time}')

Memory Allocation for Lists

A Python list contains an ordered sequence of references stored in consecutive blocks of memory. Can jump to items just based on the address of the first item. A list is contiguous - has no gaps. This makes insertion and deletion less efficient since all items must be moved. Usually allocates free space at the end, so adding and removing an object to the end is faster.

Big-Oh

Runtime normally depends on the size of the input.