{
"cells": [
{
"cell_type": "markdown",
"id": "d62ead64-2b6b-4447-9d70-60774c5e1050",
"metadata": {},
"source": [
"# Welcome to Data Structures\n",
"\n",
"Let's do a simple demonstration of why we're here with a simple Python task.\n",
"\n",
"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."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "0240ee0f-273e-4203-b6b6-ca144d86844a",
"metadata": {},
"outputs": [],
"source": [
"def list_alg1(N):\n",
" my_list = []\n",
" for i in range(N):\n",
" my_list.insert(0,i)\n",
" return my_list"
]
},
{
"cell_type": "markdown",
"id": "31b34898-fa9c-4ed4-98e4-283f421e20bd",
"metadata": {},
"source": [
"We can run this a couple times, and see that it works:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "c7030a06-79cf-4b89-a287-33ff3673b57a",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0]\n",
"[1, 0]\n",
"[2, 1, 0]\n"
]
}
],
"source": [
"print( list_alg1(1) )\n",
"print( list_alg1(2) )\n",
"print( list_alg1(3) )"
]
},
{
"cell_type": "markdown",
"id": "0972dce2-edff-4d45-bf64-b298f6b95e96",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "8685685b-8186-4648-b60c-d620cf1fab2e",
"metadata": {},
"outputs": [],
"source": [
"def list_alg2(N):\n",
" my_list = []\n",
" for i in range(N):\n",
" my_list.append(i)\n",
" my_list.reverse()\n",
" return my_list"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "99547156-e105-416e-82ef-2323b1c97724",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0]\n",
"[1, 0]\n",
"[2, 1, 0]\n"
]
}
],
"source": [
"print( list_alg2(1) )\n",
"print( list_alg2(2) )\n",
"print( list_alg2(3) )"
]
},
{
"cell_type": "markdown",
"id": "09ed0421-667c-44f7-bb94-ed689911cbe2",
"metadata": {},
"source": [
"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?\n",
"\n",
"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."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "1374531a-dd20-4102-9115-febd328d7a7c",
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"\n",
"def time_alg1(N):\n",
" times=[]\n",
" for i in range(N):\n",
" start_time = time.perf_counter()\n",
" list_alg1(i)\n",
" end_time = time.perf_counter()\n",
" times.append(end_time - start_time)\n",
" return times\n",
" \n",
"def time_alg2(N):\n",
" times=[]\n",
" for i in range(N):\n",
" start_time = time.perf_counter()\n",
" list_alg2(i)\n",
" end_time = time.perf_counter()\n",
" times.append(end_time - start_time)\n",
" return times"
]
},
{
"cell_type": "markdown",
"id": "4299631a-a67a-4655-9c3d-c1a286e2ccd9",
"metadata": {},
"source": [
"We can run these for increasingly large values of `N`, and see how long each takes."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "daaaf494-14ca-4b9f-bf56-726b812e0f13",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
" \n",
" \n",
" "
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import plotly.graph_objects as go\n",
"import plotly.io as pio\n",
"pio.renderers.default = 'notebook'\n",
"\n",
"N = 10000\n",
"times1 = time_alg1(N)\n",
"times2 = time_alg2(N)\n",
"fig = go.Figure()\n",
"fig.add_trace(go.Scatter(\n",
" y=times1,\n",
" name='Alg1'))\n",
"fig.add_trace(go.Scatter(\n",
" y=times2,\n",
" name='Alg2'))\n",
"fig.show()"
]
},
{
"cell_type": "markdown",
"id": "189b19e7-c3bc-4ff4-a596-f4c2c8df558d",
"metadata": {},
"source": [
"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.\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"id": "7f623d31-f21a-4aa9-a6fd-ceec86818e88",
"metadata": {
"editable": true,
"slideshow": {
"slide_type": ""
},
"tags": []
},
"source": [
"### Things you should know after this unit\n",
"\n",
"- You should appreciate why we care about the time and space used by a computer program.\n",
"- You should understand why we don't talk about time in terms of seconds, but instead in terms of number of operations."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "598b1bee-4a20-4ebf-b2f6-cbec63805876",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.13.5"
}
},
"nbformat": 4,
"nbformat_minor": 5
}