Welcome to Data Structures

Let’s do a simple demonstration of why we’re here with a simple Python task.

Suppose we would like to make a Python list, and continually add an element to the beginning of the list. I can think of two ideas off the top of my head as to how we might do this. The first is to use Python’s .insert(index, element) function, which shoehorns element into index index, and pushes everything over to make room. The following code demonstrates this algorithm.

def list_alg1(N):
    my_list = []
    for i in range(N):
        my_list.insert(0,i)
    return my_list

We can run this a couple times, and see that it works:

print( list_alg1(1) )
print( list_alg1(2) )
print( list_alg1(3) )

[0]
[1, 0]
[2, 1, 0]

Another possible algorithm we might try, for some reason, is to continually add elements to the back of the python list using append(element), and then reverse it at the end. The following demonstrates this algorithm, and demonstrates that it works.

def list_alg2(N):
    my_list = []
    for i in range(N):
        my_list.append(i)
    my_list.reverse()
    return my_list

print( list_alg2(1) )
print( list_alg2(2) )
print( list_alg2(3) )

[0]
[1, 0]
[2, 1, 0]

So both work, and give us identical answers, but which is better? We might prefer alg1 because it requires less code, and is simpler for the programmer and a maintainer. This is a good reason to like an approach! We might also ask some deeper questions. For example: Is one faster?

Well, in our tests, both seem to be nearly instantaneous. But what if we try to run these with large numbers? The below code times how long these algorithms take when adding N values to the front of the list.

import time

def time_alg1(N):
    times=[]
    for i in range(N):
        start_time = time.perf_counter()
        list_alg1(i)
        end_time = time.perf_counter()
        times.append(end_time - start_time)
    return times
    
def time_alg2(N):
    times=[]
    for i in range(N):
        start_time = time.perf_counter()
        list_alg2(i)
        end_time = time.perf_counter()
        times.append(end_time - start_time)
    return times

We can run these for increasingly large values of N, and see how long each takes.

import plotly.graph_objects as go
import plotly.io as pio
pio.renderers.default = 'notebook'

N = 10000
times1 = time_alg1(N)
times2 = time_alg2(N)
fig = go.Figure()
fig.add_trace(go.Scatter(
    y=times1,
    name='Alg1'))
fig.add_trace(go.Scatter(
    y=times2,
    name='Alg2'))
fig.show()

Wow! alg1 becomes much slower than alg2, especially when applied to larger numbers. In fact, it seems like as the number of values increases, alg1 is getting slower at an increasing rate, meaning that for very large values of N, alg1 might well be an obstacle to getting work done, while alg2 would be nearly instantaneous.

Clearly, something very different happens when we call insert() vs append(). It seems unlikely that Python developers would do something very smart with one function, and something dumb on the other, and in fact we’ll learn both are implemented as best they can be. This course is about understanding these details so that we can write code that is fast, memory efficient, and accurate, even when applied to very large amounts of data. Code that runs slowly, inefficiently, or otherwise poorly when confronted with large amounts of data is not scalable, and is a frequent roadblock when less-educated-than-you-will-be programmers do data science.

Things you should know after this unit

• You should appreciate why we care about the time and space used by a computer program.

• You should understand why we don’t talk about time in terms of seconds, but instead in terms of number of operations.