Day2/IntroductionToDataOrganization.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d3197b78",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41cd95a9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introduction to Data Organization\n",
    "\n",
    "##### Version 0.11\n",
    "\n",
    "***\n",
    "\n",
    "By B Scott (Northwestern/CIERA) \n",
    "Modified from Version 0.1 by A Miller  \n",
    "May 2024"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6da5aecb",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "[Session 21](https://github.com/LSSTC-DSFP/LSSTC-DSFP-Sessions/tree/main/Sessions/Session15) is primarily concerned with handling our data with efficiency.\n",
    "\n",
    "Ideally, for any and every task we want to devire solutions that operate *faster*. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "365aba81",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This can be accomplished many different ways:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff847fa4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* build algorithms that execute faster"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "463c7bde",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* spread calculations over many different computers simultaneously"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9acb12a2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* find a compact storage solution for the data so it can be accessed more quickly"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82fdb8d7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problem 1) IMDb Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04689f26",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Throughout the session we will use information from the [Internet Movie Database (IMDb)](https://www.imdb.com/) to illustrate various principles regarding data storage."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccc1f7da",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "For this notebook, we will use a [google sheets](https://docs.google.com/spreadsheets/d/1B-C7uJFrVNGpAXsGE6_xymfFVSKhwnIsI_RewkkmGa0/edit?usp=sharing) spreadsheet to examine this data (later in the week we will explore the same data stored in a database). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d0e4d76",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A quick note on the provenance of this data. The files we have used to populate this data set are from [this website](https://relational.fit.cvut.cz/dataset/IMDb) and it may not be a list of every single movie on IMDb (there are no movies after 2004)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3eb22b82",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 1a**\n",
    "\n",
    "Open the google sheet.$^\\dagger$ What information is stored in the `movies` sheet of this file? \n",
    "\n",
    "How many movies are listed? "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57b0075a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "$^\\dagger$Note – the link points to a \"view\" of the data, you may find it useful to copy the file so that you have write access. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a6737ba",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b998ad2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 1b**\n",
    "\n",
    "What information is stored in the `directors` sheet? \n",
    "\n",
    "How many directors are there? "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afdecb03",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d6fa250",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 1c**\n",
    "\n",
    "What information is stored in the `movies_directors` sheet?\n",
    "\n",
    "How many rows are there? Does this make sense? Why?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "001d78e9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea5e8ce8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 1d**\n",
    "\n",
    "Confirm your column identifications in **1c** by finding your favorite movie and making sure `movies_directors` correctly matches it with the proper director."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f5760b2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dfbf89f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 1e**\n",
    "\n",
    "What information is stored in the `movies_genres` sheet?\n",
    "\n",
    "How many rows are there? Does this make sense? Why?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a225e9a5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "373aafb4",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problem 2) Connections"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bbaf49d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We started this exercise with a goal of being efficient. And yet, the data have been organized across 4 different files (each sheet is effectively a unique csv file).  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d56e699",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 2a**\n",
    "\n",
    "If we wanted to store all the data in a single sheet, how many rows would we need?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41c182fd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d577b40",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 2b**\n",
    "\n",
    "Supposing we did convert everything to a single sheet – how many columns would you need to store all the information in a single sheet? "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87fb762a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Think about this for at least 30 sec, but you do not have to write down a full answer*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de5dc057",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 2c**\n",
    "\n",
    "Which has fewer total entries (the combination of a column and a row makes 1 entry) – all the data in one sheet, or the data spread across 4 sheets? "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "713aa396",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d06e4a3e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 2d**\n",
    "\n",
    "What is the release year for every movie directed by Martin Scorcese? \n",
    "\n",
    "*Hint* – do not spend more than 10 min working on this problem (you probably should not even spend a full 10 min). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ae014e3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "895a7e0f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problem 3) Leverage"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "514a9758",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Now that we know why the data has been organized in this way, we can leverage this unique structure in order to learn interesting properties of the data. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10f62233",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 3a**\n",
    "\n",
    "As a follow-up to a previous problem, according the the IMDb data, which director has directed the most movies?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52a16bb0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Hint* – there are probably several ways to figure this out, but I'll note that google sheets provides the ability to calculate aggregated statistics *after* the data have been grouped in a single category. This type of operation exists on many different platforms, and is typically called a `group by`. \n",
    "\n",
    "For google sheets, a `group by` is performed inside the built in `QUERY` function. For example, if you were to type the following into a cell:\n",
    "\n",
    "`=QUERY(A1:D25, \"select B, AVG(D) group by B\", 1)`\n",
    "\n",
    "this would look at all the data in columns A--D, and between rows 1--25, it would then select values in B and \"group the data\" (i.e., suppose this column listed city names and column D listed temperatures, then every entry for the same city would be \"grouped\"), then aggregate statistics are caluclated on D (in this example, the average temperature for the city would be calculated). The `1` at the end indicates a single header row to those being searched.\n",
    "\n",
    "The results would be a column saying city and a column saying temperature, and then the average temp in each city would be recorded. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e6ca2ca",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Hint 2* – run your query on only a few rows first to make sure it works in the expected fashion."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b4852d5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "To determine who has directed the most movies, we can run the following command on the `movies_directors` table.\n",
    "\n",
    "`=QUERY(A1:B400000, \"select A, count(B) group by A order by count(B) desc limit 5\", 1)`\n",
    "\n",
    "*Note* – I have added an `order by count(B) desc` so that the results show the largest numbers first. I have also added a `limit 5` so that only the top results are shown (we don't care about all the people that have only directed one film at this time). \n",
    "\n",
    "From this we see that director `25116` has directed 616 movies (!!!)\n",
    "\n",
    "|  director_id  |  count movie_id  |\n",
    "| :---:    | :---:       |\n",
    "|  25116        |  616  |\n",
    "|56530\t|554|\n",
    "|30570\t|530|\n",
    "|1958\t|360|\n",
    "|24576\t|345|\n",
    "\n",
    "We can now scroll in the directors table to see that `director_id = 25116` corresponds to [Dave Fleischer](https://www.imdb.com/name/nm0281487/?ref_=fn_al_nm_1#director)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c65526f",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "P.S. How in the world did Dave Fleischer have enough time to direct 616 movies in a single life time? \n",
    "\n",
    "P.P.S. If we need 616 columns for the single table/sheet solution, that is another factor of $\\sim$20 more storage. Hopefully it's clear this would be a bad idea."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce380d67",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We now know who (according to IMDb) has directed the most movies ever.\n",
    "\n",
    "You should feel a little unsatisfied with this solution, however. While we had a clever way to count the movies by director, we still had to click over to another sheet and scroll (or `cntl+f`) to find the name of the director."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9662933",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "It would be far more satisfying to use a single command that returns director name *and* number of movies. \n",
    "\n",
    "To do this in a single command requires a `JOIN` (i.e., data from two different tables/sheets must be combined). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f528b9f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Sadly, joins are not possible in google sheets$^\\dagger$ (or at least I've spent a lot of time trying, and I have not found anything close to a useful solution even for the moderate amount of data included in this project).\n",
    "\n",
    "$^\\dagger$If you know how to do this let me know."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b2ddec9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "To understand why the join operation is so powerful, consider the following question:\n",
    "\n",
    "Which drama directed by Martin Scorsese has the highest IMDb rating? "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a45b7aba",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This question is not that complex, but, we need to do the following to solve it with our spreadsheet: \n",
    "  1. look up the Scorsese `director_id`\n",
    "  2. use `movies_directors` to look up the movies Scorsese has directed\n",
    "  3. use `movies_genres` to figure out which of those movies are dramas\n",
    "  4. select and sort the subset of Scorsese drama `movies` based on score"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f541393",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "That's a lot of clicking around and running multiple operations. \n",
    "\n",
    "We will see several other methods later this week that are capable of `JOIN`ing tables so that this can be accomplished quickly."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48868d33",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Problem 3b**\n",
    "\n",
    "In which year were the most movies made according to IMDb?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71d8aafa",
   "metadata": {},
   "source": [
    "*write your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56a386a8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Challenge Problem) Algorithmic Speed"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d94a06c7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "For the challenge problem we will consider a different type of efficiency – algorithms.\n",
    "\n",
    "We will demonstrate the types of improvements that are possible even for simple algorithms, like \"sorting\"."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96ac4280",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Both `python` and `numpy` have build-in functions that can sort a list or array with a great deal of efficiency. In practice, I would never recommend writing your own function to this end, but we will demonstrate how much time can be saved via \"clever\" implementations of straightforward ideas. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf1e95ab",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge a**\n",
    "\n",
    "Write a \"pure\" python function to sort the numbers in a list. Restrict yourself to simple list operations (i.e., do not use `np.sort()`. \n",
    "\n",
    "*Hint* – we can sort a list by creating a new list, `sort_list`, and looping over all elements in the original list and inserting each element in the position where it is greater than the previous value and less than or equal to the next value in `sorted`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "c075c4bc",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def sortlist(unsort):\n",
    "    '''Sort the unsorted list unsort\n",
    "    \n",
    "    Inputs\n",
    "    ------\n",
    "    unsort : list of numbers\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    sort_list : values of unsort after being sorted\n",
    "    '''\n",
    "    \n",
    "    sort_list = []\n",
    "    sort_list.append(unsort[0])\n",
    "    if unsort[1] > unsort[0]:\n",
    "        # complete\n",
    "    else:\n",
    "        # complete\n",
    "    for u in unsort[2:]:\n",
    "        for idx, sl in enumerate(sort_list):\n",
    "            n = len(sort_list)\n",
    "            if u <= sl:\n",
    "                # complete\n",
    "                break\n",
    "            elif idx + 1 == n:\n",
    "                # complete\n",
    "                break\n",
    "    return sort_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21eaca07",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge b**\n",
    "\n",
    "Confirm your algorithm works by running it on the following list: [4, 1, 6, 2, 4, 7, 9, 3, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "03c5b5ca",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 4, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortlist([4, 1, 6, 2, 4, 7, 9, 3, 8])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51e60eca",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge c**\n",
    "\n",
    "Create a list with 10000 random numbers. Time how long it takes to sort that list with your algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "384b213a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "It takes 3.4232 s to sort this list\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "np.random.seed(1662)\n",
    "\n",
    "haha = list(np.random.randn(10000))\n",
    "\n",
    "tstart = time.time()\n",
    "sl = sortlist(haha)\n",
    "tend = time.time()\n",
    "\n",
    "print('It takes {:.4f} s to sort this list'.format(tend-tstart))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdc8665f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "10000 elements is not that many, and 3 s is a lot of time. In this case the speed of the algorithm is quite slow because we have a nested for loop. As the sorted array becomes larger, we have to again and again consider all the same numbers while looking for the \"right\" place to insert our value. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48021ae3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We can achieve dramatic improvements with a \"divide and conquer\" strategy. In particular, we will use the [`quicksort`](https://en.wikipedia.org/wiki/Quicksort) algorithm to avoid looking at the same numbers again and again. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90742739",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In brief, `quicksort` does the following: pick a single element of an array/list (called the \"pivot\"), move all values less than the pivot to its right, move all values greater than the pivot to its left.\n",
    "\n",
    "The pivot is now in its correct position within the array. We can now perform the same operation on the left and on the right to recursively move everything into the correct order. Unlike the \"simple\" method, we do not need to \"look at\" the same values again and again and again."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3f3bd96",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge d**\n",
    "\n",
    "Write a recursive `quicksort` algorithm to sort values in a list/array. \n",
    "\n",
    "*Hint* – use the last element of the array as the \"pivot\" each time you separate the data into high and low values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "1235cfd1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def sort_pivot(l, r, arr):\n",
    "    pivot, ptr = arr[r], l\n",
    "    for i in range(l, r):\n",
    "        if arr[i] <= pivot:\n",
    "            # complete\n",
    "            # complete\n",
    "    # complete \n",
    "    return ptr\n",
    "\n",
    "def quicksort(l, r, arr):\n",
    "    if len(arr) == 1:\n",
    "        return arr\n",
    "    if l < r:\n",
    "        # complete\n",
    "        # complete\n",
    "        # complete \n",
    "    return arr"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0b9745c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge e**\n",
    "\n",
    "Confirm your algorithm works by sorting the short list [4, 1, 6, 2, 4, 7, 9, 3, 8]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "0dd28622",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 4, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "short_list = [4, 1, 6, 2, 4, 7, 9, 3, 8]\n",
    "quicksort(0, len(short_list)-1, short_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d2788f6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge f**\n",
    "\n",
    "Time how long it take to sort the random number array using `quicksort`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "e7d6b749",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "It takes 0.0388 s to sort this list\n"
     ]
    }
   ],
   "source": [
    "meh = haha.copy()\n",
    "tstart = time.time()\n",
    "sl = quicksort(0, len(haha)-1, meh)\n",
    "tend = time.time()\n",
    "\n",
    "print('It takes {:.4f} s to sort this list'.format(tend-tstart))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1006d8cd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A factor of 100 improvement! "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6040cfaa",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Challenge g**\n",
    "\n",
    "Time how long it takes to sort the random number array using `np.sort()`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "991da431",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "It takes 0.0068 s to sort this list\n"
     ]
    }
   ],
   "source": [
    "meh = haha.copy()\n",
    "\n",
    "tstart = time.time()\n",
    "sl = np.sort(meh)\n",
    "tend = time.time()\n",
    "\n",
    "print('It takes {:.4f} s to sort this list'.format(tend-tstart))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca55a730",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "While your solution was quite clever, under the hood `numpy` is still another factor of 5 faster! \n",
    "\n",
    "The upside from this exercise – every time you find yourself creating a for loop, ask the question do I really need a for loop. For the most part you will always be working with software that is already optimized but the for loops that you write may not be..."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.8.13"
  },
  "livereveal": {
   "height": 768,
   "scroll": true,
   "start_slideshow_at": "selected",
   "theme": "solarized",
   "width": 1024
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}