Measure time and space requirements of different Python containers

Question

I was actually kind of bored and since I'm studying some Python data structures I decided to make some size(MB) and time(secs) comparisons between different containers when conducting the operation of adding n items to each container type. I included:

• List appending
• List initialization
• List comprehensions
• Array
• Set comprehensions
• Generator comprehensions
• Dictionary comprehensions
• Tuple
• Set add
• Dictionary assignment

I hope you enjoy using it, since it's mainly for fun purposes and might give you some insight on efficiency.

from time import time
from array import array
import sys
import operator


class MakeContainers:
    """Produce containers of different types."""

    def __init__(self, n):
        self.size = n

    def get_appends(self):
        """Return time and size for appending a list."""
        start_time = time()
        sequence = []
        for i in range(self.size):
            sequence.append(i)
        return time() - start_time, sys.getsizeof(sequence)

    def get_initialization(self):
        """Return time and size for list initialization."""
        start_time = time()
        sequence = [None] * self.size
        for i in range(self.size - 1):
            sequence[i] = i
        return time() - start_time, sys.getsizeof(sequence)

    def get_list_comprehensions(self):
        """Return time and size for list comprehensions."""
        start_time = time()
        sequence = [x for x in range(self.size)]
        return time() - start_time, sys.getsizeof(sequence)

    def get_array(self):
        """Return array time and size."""
        start_time = time()
        sequence = array('i', [x for x in range(self.size)])
        return time() - start_time, sys.getsizeof(sequence)

    def get_generator_comprehensions(self):
        """Return generator comprehensions time and size."""
        start_time = time()
        sequence = (x for x in range(self.size))
        return time() - start_time, sys.getsizeof(sequence)

    def get_set_comprehensions(self):
        """Return set comprehensions time and size."""
        start_time = time()
        sequence = {x for x in range(self.size)}
        return time() - start_time, sys.getsizeof(sequence)

    def get_dictionary_comprehensions(self):
        """Return dictionary comprehensions time and size."""
        start_time = time()
        sequence = {x: x for x in range(self.size)}
        return time() - start_time, sys.getsizeof(sequence)

    def get_tuple(self):
        """Return time and size of making a tuple."""
        start_time = time()
        sequence = tuple(x for x in range(self.size))
        return time() - start_time, sys.getsizeof(sequence)

    def get_set_add(self):
        """Return time and size of adding items to a set."""
        start_time = time()
        sequence = set()
        for i in range(self.size):
            sequence.add(i)
        return time() - start_time, sys.getsizeof(sequence)

    def get_dictionary_assignment(self):
        """Return time and size of assigning values to a dictionary."""
        start_time = time()
        sequence = {}
        for i in range(self.size):
            sequence[i] = i
        return time() - start_time, sys.getsizeof(sequence)


def test_containers(n):
    """Test containers of different types and print results for size n."""
    test = MakeContainers(n)
    size_rank = time_rank = 1
    operation_index = 0
    sizes = {}
    times = {}
    operations = [
        'List appends', 'List initializations', 'List comprehensions', 'Array', 'Generator comprehensions',
        'Set comprehensions', 'Dictionary comprehensions', 'Tuple', 'Set add', 'Dictionary assignment'
    ]
    values = [
        test.get_appends(), test.get_initialization(), test.get_list_comprehensions(), test.get_array(),
        test.get_generator_comprehensions(), test.get_set_comprehensions(), test.get_dictionary_comprehensions(),
        test.get_tuple(), test.get_set_add(), test.get_dictionary_assignment()
    ]
    for value in values:
        times[operations[operation_index]] = value[0]
        sizes[operations[operation_index]] = value[1]
        operation_index += 1
    print('Size ranks:')
    print(35 * '=')
    for operation, size in sorted(sizes.items(), key=operator.itemgetter(1)):
        print(f'Rank: {size_rank}')
        print(f'Operation: {operation}\nSize: {size / 10 ** 6} MB.')
        print(f'Number of items: {n}')
        size_rank += 1
        print(35 * '=')
    print()
    print('Time ranks:')
    print(35 * '=')
    for operation, timing in sorted(times.items(), key=operator.itemgetter(1)):
        print(f'Rank: {time_rank}')
        print(f'Operation: {operation}\nTime: {timing} seconds.')
        print(f'Number of items: {n}')
        time_rank += 1
        print(35 * '=')


if __name__ == '__main__':
    st_time = time()
    test_containers(10 ** 7)
    print(f'Total time: {time() - st_time} seconds.')

Answer 1

There is a lot of repetition in your methods and the only reason you have a class at all is so you can pass the size. Instead I would make this into standalone functions to which you can add a decorator. The functions themselves, together with the decorator, I would put into another module.

I would also use time.perf_counter as it makes sure to use the best time resolution available on the system the code is running.

from array import array
from functools import wraps
from time import perf_counter
from sys import getsizeof

def time_and_memory(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = perf_counter()
        ret = func(*args, **kwargs)
        return perf_counter() - start, getsizeof(ret)
    return wrapper


@time_and_memory
def list_append(n):
    """list append"""
    sequence = []
    for i in range(n):
        sequence.append(i)
    return sequence


@time_and_memory
def list_pre_initialized(n):
    """list pre-initialized"""
    sequence = [None] * n
    for i in range(n - 1):
        sequence[i] = i
    return sequence


@time_and_memory
def list_comprehension(n):
    """list comprehension"""
    return [x for x in range(n)]


@time_and_memory
def array_int(n):
    """array.array with integers"""
    return array('i', [x for x in range(n)])


@time_and_memory
def generator_expression(n):
    """generator expression"""
    return (x for x in range(n))


@time_and_memory
def range_object(n):
    """range"""
    return range(n)


@time_and_memory
def set_comprehension(n):
    """set comprehension"""
    return {x for x in range(n)}


@time_and_memory
def dictionary_comprehension(n):
    """dictionary comprehension"""
    return {x: x for x in range(n)}


@time_and_memory
def tuple_constructor(n):
    """tuple"""
    return tuple(x for x in range(n))


@time_and_memory
def set_add(n):
    """set add"""
    s = set()
    s_add = s.add
    for i in range(n):
        s_add(i)
    return s


@time_and_memory
def dict_assignment(n):
    """dict assign"""
    sequence = {}
    for i in range(n):
        sequence[i] = i
    return sequence


all_funcs = [list_append, list_pre_initialized, list_comprehension, array_int,
             generator_expression, range_object, set_comprehension,
             dictionary_comprehension, tuple_constructor, set_add, dict_assignment]

I also added the range object and interned set.add before the loop to slightly speed it up, just for fun.

As an alternative to the decorator, you could also just have a function that runs a given function with the given arguments and returns the time and memory size:

def get_time_and_memory(func, *args, **kwargs):
    start = perf_counter()
    ret = func(*args, **kwargs)
    return perf_counter() - start, getsizeof(ret)

Then you call this on all inputs:

for n in values:
    for func in all_funcs:
        time, size = get_time_and_memory(func, n)
        ...

---

The analyzing script can then be quite short. I would read all times and sizes into one data structure. I generated logarithmically spaced values using numpy.logspace and saved the results in a pandas.DataFrame. I also added some plotting (using matplotlib). Note that I (ab)used the docstring as the label in the plot.

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

from python_containers_funcs import all_funcs


def test_containers(values):
    df = pd.DataFrame(columns=["func", "n", "time", "size"])
    for n in values:
        for func in all_funcs:
            time, size = func(n)
            df = df.append({"func": func.__doc__, "n": n,
                            "time": time, "size": size / 10**6},
                           ignore_index=True)
    return df


def plot_results(df):
    fig = plt.figure()
    ax1 = plt.subplot(2, 2, 1)
    ax2 = plt.subplot(2, 2, 3)

    for group, gdf in df.groupby("func"):
        # print(group)
        ax1.plot(gdf["n"], gdf["time"], label=group)
        ax2.plot(gdf["n"], gdf["size"], label=group)
    ax1.set_xlabel("n")
    ax1.set_ylabel("Time [s]")
    ax1.set_xscale("log")
    ax1.set_yscale("log")
    ax1.legend(bbox_to_anchor=(1.04, 1), borderaxespad=0)
    ax2.set_xlabel("n")
    ax2.set_ylabel("Memory size [MB]")
    ax2.set_xscale("log")
    ax2.set_yscale("log")
    return fig


if __name__ == "__main__":
    values = np.logspace(1, 6, dtype=int)
    df = test_containers(values)
    print("Sorted by time [s]:")
    print(df.groupby("func").time.max().sort_values())
    print("\nSorted by memory size [MB]:")
    print(df.groupby("func")["size"].max().sort_values())
    fig = plot_results(df)
    plt.show()

This produces the following output in the terminal:

Sorted by time [s]:
func
generator expression         0.000032
range                        0.000036
list comprehension           0.160947
list pre-initialized         0.236695
set comprehension            0.264900
tuple                        0.312254
array.array with integers    0.350580
dictionary comprehension     0.353248
set add                      0.398240
dict assign                  0.412190
list append                  0.418838
Name: time, dtype: float64

Sorted by memory size [MB]:
func
range                         0.000048
generator expression          0.000088
array.array with integers     4.000064
tuple                         8.000048
list pre-initialized          8.000064
list append                   8.697464
list comprehension            8.697464
set add                      33.554656
set comprehension            33.554656
dict assign                  41.943144
dictionary comprehension     41.943144
Name: size, dtype: float64

And the following figure, which is admittedly a bit hard to read with this many lines.

Fun fact: the memory footprint of range is even smaller than that of a generator expression, since it only needs to store start, stop, step, whereas the generator needs to store the entire state (which in this case includes a range object, but also other objects).