Python

Subcategory: None · Core

List Comprehension

Subcategory: Core

List comprehension (e.g. [expression for item in iterable if condition == True]) is faster than constructing a list with a loop. it can’t be used for all list construction, such as where items depend on one another, but it should be used whenever possible.

Example Code

Rather than constructing a list with append() inside a loop

squares = []
for x in range(100):
    squares.append(x**2)

Use a list comprehension

squares = [x**2 for x in range(10)]

Whilst being more concise and readable, it is also typically faster. The speed-up will depend on the length of the list, and complexity of it’s construction but is likely to be twice as fast.

List comprehension syntax can be nested to create two-dimensional lists, however using map() and zip() may create more readable code in these scenarios.

Example Benchmark

The below code provides a simple benchmark of creating a list of 100,000 consecutive integers using a three approaches.

from timeit import timeit

# Construct the list appending each item individually
def list_append():
    li = []
    for i in range(100000):
        li.append(i)

# Construct the list by preallocating it, before setting each item to the correct value
def list_preallocate():
    li = [0]*100000
    for i in range(100000):
        li[i] = i

# Construct the list using list comprehension
def list_comprehension():
    li = [i for i in range(100000)]

repeats = 1000
print(f"Append: {timeit(list_append, number=repeats):.2f}ms")
print(f"Preallocate: {timeit(list_preallocate, number=repeats):.2f}ms")
print(f"Comprehension: {timeit(list_comprehension, number=repeats):.2f}ms")

In testing this produced the following results

list_append: 3.50ms
list_preallocate: 2.48ms
list_comprehension: 1.69ms

Using list comprehension was over 2x faster than using a loop and append().

The Technical Detail

List comprehension is likely faster than using loops and append, because the syntax is more constrained allowing greater optimisation within the Python back-end.

How Lists Are Implemented

Lists are implemented as a form of dynamic array found within many programming languages by different names (C++: std::vector, Java: ArrayList, R: vector, Julia: Vector).

They allow direct and sequential element access, with the convenience to append items.

This is achieved by internally storing items in a static array. This array however can be longer than the list, so the current length of the list is stored alongside the array. When an item is appended, the list checks whether it has enough spare space to add the item to the end. If it doesn’t, it will re-allocate a larger array, copy across the elements, and deallocate the old array. The item to be appended is then copied to the end and the counter which tracks the list’s length is incremented.

The amount the internal array grows by is dependent on the particular list implementation’s growth factor. CPython for example uses newsize + (newsize >> 3) + 6, which works out to an over allocation of roughly ~12.5%.

A graph demonstrating the number of resizes required based on the number of appends to a list within CPython. The plot is almost vertical for x < 100,000, before tapering off.
The relationship between the number of appends to an empty list, and the number of internal resizes in CPython.

This has two implications:

If you are creating large static lists, they will use upto 12.5% excess memory.
If you are growing a list with append(), there will be large amounts of redundant allocations and copies as the list grows.

Set

Subcategory: Core

Similar to the mathematical concept of a set, Python (and most other languages) provides a data structure set which is an unordered collection of unique values. Using a set is the fastest way to detect unique items (e.g. if a in my_set) or remove duplicates (e.g. [x for x in set(my_list)]).

Example Code

Rather than using a list to build a unique collection of items

import random
# Create a list of 1000 random numbers in the range [0, 2000)
list_out = []
while len(list_out) < 1000:
    t = random.randint(0, 2000)
    if not t in list_out:
        list_out.append(t)

Use a set

import random
# Create a set of 1000 random numbers in the range [0, 2000)
set_out = []
while len(set_out) < 1000:
    t = random.randint(0, 2000)
    set_out.add(t)

Depending on the size of the collection, the order of items, and the proportion of duplicates, using a set could be thousands of times faster than using a list.

Example Benchmark

The below code provides a simple benchmark of removing duplicates from a list of 25000 random integers using a list or set.

import random
from timeit import timeit

# A simple method to generate us a consistent input list
def generateInputs(N = 25000):
    random.seed(12)  # Ensure every list is the same 
    return [random.randint(0,int(N/2)) for i in range(N)]

# Pass the list directly to the set constructor
def uniqueSet():
    ls_in = generateInputs()
    set_out = set(ls_in)

# Iterate the list, adding each item to the set individually
def uniqueSetAdd():
    ls_in = generateInputs()
    set_out = set()
    for i in ls_in:
        set_out.add(i)

# Iterate the list, adding each unique item to the new list individually
def uniqueList():
    ls_in = generateInputs()
    ls_out = []
    for i in ls_in:
        if not i in ls_out:
            ls_out.append(i)

# Sort the input list, add each item if it does not match the last item of the new list
def uniqueListSort():
    ls_in = generateInputs()
    ls_in.sort()
    ls_out = [ls_in[0]]
    for i in ls_in:
        if ls_out[-1] != i:
            ls_out.append(i)
            
repeats = 1000
gen_time = timeit(generateInputs, number=repeats)
print(f"uniqueSet: {timeit(uniqueSet, number=repeats)-gen_time:.2f}ms")
print(f"uniqueSetAdd: {timeit(uniqueSetAdd, number=repeats)-gen_time:.2f}ms")
print(f"uniqueList: {timeit(uniqueList, number=repeats)-gen_time:.2f}ms")
print(f"uniqueListSort: {timeit(uniqueListSort, number=repeats)-gen_time:.2f}ms"

In testing this produced the following results

uniqueSet: 0.30ms
uniqueSetAdd: 0.81ms
uniqueList: 660.71ms
uniqueListSort: 2.67ms

Using the constructor for set was over 2000x times faster than iterating the unsorted list.

The Technical Detail

Set data structures are similar to dictionaries, but without the values. Internally they are typically implemented with hashing or tree data-structures. These are highly optimal for direct access to items, requiring less items to be checked to test for existence.

In contrast, performing a search through an unsorted list will require all items to be checked in the worst case whereby the item is not found. Approaches such as sorting the list and using a binary search can greatly improve performance, however in most cases using a set will be preferable.