8
\$\begingroup\$

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.')
\$\endgroup\$
  • \$\begingroup\$ And the winners are ... \$\endgroup\$ – dfhwze Aug 6 at 20:00
  • 1
    \$\begingroup\$ Generators on top of course, followed by list comprehensions and intializations and tupling in terms of speed... sets and dictionaries are worst in terms of size. and btw there is a window of like 4 seconds between list comprehensions and list appending (n = 10 ** 8) \$\endgroup\$ – Emad Boctor Aug 6 at 20:14
  • \$\begingroup\$ test run on macbook pro 2015 2.7 GHz Intel Core i5 8 GB 1867 MHz DDR3 \$\endgroup\$ – Emad Boctor Aug 6 at 20:28
  • \$\begingroup\$ Two problems. #1) get_generator_comprehensions() creates a generator that is never iterated over. It is like saying "get ready to count to 10 million. You ready? Great! How much time has that taken you?" You haven't done any counting yet. #2) sys.getsizeof() returns the size of the container, but not (necessarily) the contents, because the contents are (usually) references to other objects, so may not be "owned" by the container. array.array() is an exception. It directly contains the values it stores. Memory wise, it looks 2x better than a list, but is actually 9x better! \$\endgroup\$ – AJNeufeld Aug 7 at 22:54
  • \$\begingroup\$ @AJNeufeld yeah, I know I just included the generator for fun purposes, I know it does not use any memory or anything and as I'm not the hardcore programmer type yet, I still do not see any significant importance to arrays in Python because Python lists in my narrow perspective, do most of the work, so can you point a few things/applications to arrays where they are better than lists or must be applied? \$\endgroup\$ – Emad Boctor Aug 7 at 23:34
3
\$\begingroup\$

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.

enter image description here

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You can make a decorator for a class which applies a decorator to all methods of that class. You don't need to necessarily split them up. \$\endgroup\$ – QuantumChris Aug 7 at 8:45
  • 1
    \$\begingroup\$ @Graipher thanks a lot for the very thorough review, I'll check the link and btw I'm reading a technical O'Reilly book about Python as well sooner or later I'll come across the decorators and whatever other features. \$\endgroup\$ – Emad Boctor Aug 7 at 12:37
  • 2
    \$\begingroup\$ Two problems. #1) generator_expression() creates a generator that is never iterated over. It is like saying "get ready to count to 10 million. You ready? Great! How much time has that taken you?" You haven't done any counting yet. #2) sys.getsizeof() returns the size of the container, but not (necessarily) the contents, because the contents are (usually) references to other objects, so may not be "owned" by the container. array.array() is an exception. It directly contains the values it stores. Memory wise, it looks 2x better than a list, but is actually 9x better! \$\endgroup\$ – AJNeufeld Aug 7 at 22:57
  • 2
    \$\begingroup\$ @AJNeufeld 1) I am aware. However, that is how it is in the OP, and I took that to be on purpose. 2) True. I have not looked into it, but would something like getsizeof(sequence) + sum(map(getsizeof, sequence)) work (disregarding for now that this would iterate over the generator). \$\endgroup\$ – Graipher Aug 7 at 23:01
  • 1
    \$\begingroup\$ With, x = [i for i in range(1_000_000)], then getsizeof(x) + sum(getsizeof(e) for e in x) return 36697460. With y = array('i', (x for x in range(1_000_000))), then getsizeof(y) return 4091932. Advantage of array.array() is 36697460 / 4091932 which is 8.968247761693009. \$\endgroup\$ – AJNeufeld Aug 7 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.