Performance difference between append and insert in Python

h1ros

Jul 27, 2019, 7:55:14 AM

Goal¶

This post aims to compare the performance between append and insert in Python. The performance comparison is simply done by the piece of code that counts a number, append it to a list, and then reverse it.

We will see the significant difference between two codes: one using append is linear and another using insert is quadratic run time growth as below.

Reference

Python Algorithms: Mastering Basic Algorithms in the Python Language

Libraries¶

In [26]:

from timeit import Timer
import pandas as pd
%matplotlib inline

Append¶

In [6]:

count = 10**5

In [9]:

def count_by_append(count):
    nums = []
    for i in range(count):
        nums.append(i)
    nums.reverse()
count_by_append(count)

The execution time is 22ms

Insert¶

In [10]:

def count_by_insert(count):
    nums = []
    for i in range(count):
        nums.insert(0, i)
count_by_insert(count)

The execution time is 3.53s

Comparison¶

In [24]:

counts = [10 ** i for i in range(5)]
time_by_append = []
time_by_insert = []

for count in counts:
    print(f'Processing {count}')
    t = Timer(lambda: count_by_append(count))
    time_by_append.append(t.timeit(number=10))
    t = Timer(lambda: count_by_insert(count))
    time_by_insert.append(t.timeit(number=10))

df_performance = pd.DataFrame({'count': counts,
                               'count_by_append': time_by_append,
                               'count_by_insert': time_by_insert})
df_performance

Processing 1
Processing 10
Processing 100
Processing 1000
Processing 10000

Out[24]:

	count	count_by_append	count_by_insert
0	1	0.000013	0.000011
1	10	0.000019	0.000027
2	100	0.000107	0.000227
3	1000	0.000927	0.005318
4	10000	0.009438	0.379457

In [34]:

# Plot the performance difference
df_performance.set_index('count').plot(title='Performance Comparison beteen Append and Insert');