Arrays and Lists

I often get questions about the difference between the Python list and the NumPy ndarray, and we talk about this a lot in Python Foundations for Scientists & Engineers. But recently I had a question about the array object that is part of the Python language, and why don’t we use it for computations? Why is NumPy necessary if Python has an array data type? Well, this is a great question!

First of all, let’s take a quick look at the Python array. It’s found in the array standard library and usually imported as arr:

>>> import array as arr

Like a NumPy ndarray, it has a data type, and every element of the array has to conform to that type. Set the data type in in the first argument when creating the array. 'l' in this case specifies a 4-byte signed integer:

>>> a = arr.array('l', range(5))
>>> a
array('l', [0, 1, 2, 3, 4])

It has the same indexing and slicing behavior as a Python list, and we even see that it has the same “multiplication” behavior as lists: i.e. “multiplying” means repetition, not element-wise, arithmetic multiplication as with the NumPy ndarray.

With that in mind, computations look the same for arrays as for lists:

>>> b = arr.array(a.typecode, (v + 1 for v in a))
>>> b
array('l', [1, 2, 3, 4, 5])

Let’s use IPython’s %timeit magic to see how array computations fare in comparison with Python lists and NumPy ndarrays. For the list and array, we’ve specified a list comprehensions as the most efficient way to do the computations and a simple vector computation for the NumPy ndarray, and our test is to increment sequence of 10 integers:

In [1]: import array as arr
   ...: import numpy as np
   ...:
   ...: %timeit [val + 1 for val in list(range(10))]
   ...: %timeit arr.array('q', [val + 1 for val in arr.array('q', range(10))])
   ...: %timeit np.arange(10) + 1
279 ns ± 45.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
825 ns ± 5.22 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.03 μs ± 98.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

It’s surprising to note that list comprehension is fastest, beating array computation by a factor of 3 or so, and beating ndarray computation by a factor of 3.7! Suspecting that a 10-integer sequence may not be representative, let’s bump it up to 1000:

In [2]: %timeit [val + 1 for val in list(range(1000))]
   ...: %timeit arr.array('q', [val + 1 for val in arr.array('q', range(1000))])
   ...: %timeit np.arange(1000) + 1
28.4 μs ± 3.47 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
82.4 μs ± 9.05 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
1.82 μs ± 175 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

With more numbers to chew on, NumPy clearly pulls ahead, suggesting the overhead of creating an ndarray may dominate computation time for small arrays, but the actual computation time is relatively small. The Python array is still relatively inefficient compared to the Python list. Let’s make some helper functions to compare how long it takes to increment each value in lists, arrays, and NumPy ndarrays accross a broad range of different sizes. Each function will accept a list, array, or ndarray and return the time (in ms) required to increment each value by 1.

In [3]: from datetime import datetime
   ...:
   ...: def inc_list_by_one(l):
   ...:     start = datetime.now()
   ...:     res = [val + 1 for val in l]
   ...:     return (datetime.now() - start).total_seconds() * 1000
   ...:
   ...: def inc_array_by_one(a):
   ...:     start = datetime.now()
   ...:     res = arr.array(a.typecode, [val + 1 for val in a])
   ...:     return (datetime.now() - start).total_seconds() * 1000
   ...:
   ...: def inc_numpy_array_by_one(arr):
   ...:     start = datetime.now()
   ...:     res = arr + 1
   ...:     return (datetime.now() - start).total_seconds() * 1000

Now let’s record the computation times for a range of array sizes and plot them using matplotlib and seaborn:

In [14]: import matplotlib.pyplot as plt
    ...: import seaborn as sns
    ...:
    ...: times = []
    ...: for size in range(1, 10_000_001, 200_000):
    ...:     times.append((
    ...:         size,
    ...:         inc_list_by_one(list(range(size))),
    ...:         inc_array_by_one(arr.array('q', range(size))),
    ...:         inc_numpy_array_by_one(np.arange(size)),
    ...:     ))
    ...: times_arr = np.array(times)
    ...:
    ...: sns.regplot(x=times_arr[:, 0], y=times_arr[:, 1], label='Python list')
    ...: sns.regplot(x=times_arr[:, 0], y=times_arr[:, 2], label='Python array')
    ...: sns.regplot(x=times_arr[:, 0], y=times_arr[:, -1], label='Numpy array')
    ...: plt.xlabel('Array Size (num elements)')
    ...: plt.ylabel('Time to Increment by 1 (ms)')
    ...: plt.legend()
    ...: plt.show()

Computation time v array size

…and now it’s clear that computation times for Python lists and arrays scale with the size of the object much faster than NumPy ndarrays do. And it’s also clear that the Python array is no improvement for computations, static typing notwithstanding. Let’s quantify:

In [26]: print(f'Python list {np.polyfit(times_arr[:, 0], times_arr[:, 1], 1)[0]:.2e} (ms/element)')
    ...: print(f'Python array {np.polyfit(times_arr[:, 0], times_arr[:, 2], 1)[0]:.2e} (ms/element)')
    ...: print(f'NumPy ndarray {np.polyfit(times_arr[:, 0], times_arr[:, -1], 1)[0]:.2e} (ms/element)')
Python list 4.02e-05 (ms/element)
Python array 6.50e-05 (ms/element)
NumPy ndarray 2.01e-06 (ms/element)

So if we take the slope of those curves as a gauge of performance, Python arrays are roughly 40% slower in computation than lists, and the NumPy ndarray computations run in about 95% less time, on average for arrays that are not trivially small. This is because NumPy takes advantage of knowing the data type of each element and setting up efficient strides in memory for computations, which can be optimized at the operating system and hardware levels.

What, then, is the advantage of the Python array over a Python list? With helper functions similar to the ones above, we can return sys.getsizeof() sample list and array objects over the same range of sizes. Plotting the results, we see something interesting:

Memory consumption v array size

Memory consumption for both Python arrays and NumPy ndarrays scale exactly linearly with the number of elements (the q typcode specifies a signed integer with a minimum 8 bytes, which corresponds to the default int64 dytpe for integer NumPy ndarrays.) But notice how the Python list memory consumption increases stepwise. This is an implementation detail of the Python list type that allows it to quickly add elements without shifting memory after each append operation. And this is likely the explanation for why lists can be faster and more efficient than arrays. When a new value is written to an array, it likely often occurs that the some or all of the object needs to be shuffled in memory to find contiguous locations, but a list is optimized for appending, so a certain number of additions can be made before any reshuffling happens.

To test this, we can compare the computation times for an array computed with a list comprehension against an array that is copied and overwritten:

def inc_array_by_one_with_copy(a):
    start = datetime.now()
    res = copy(a)
    for i, val in enumerate(a):
        res[i] = val + 1
    return (datetime.now() - start).total_seconds() * 1000

Plotted, we see that the copy-fill approach is marginally faster, and there is less variation, likely due to fewer memory relocations.

Computation time v array size for arrays created with list comprehension and copy-fill strategies

In conclusion, it helps to understand that the array type is really intended as a Python wrapper around a C array, and there are some functions and codes that use it to efficiently return a Python object. But as for computations, I hope I’ve conviced you that the NumPy ndarray is the right type for computations in terms of both memory and computation efficiency. As for Python arrays, now you know what they are, and you can safely ignore them in favor of the ndarray for your scientific computations.

Back to blog

Leave a comment

Please note, comments need to be approved before they are published.