Day2/IntroductionToDataOrganizationSolutions.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": "9e64ba9d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In our introduction to this session we will start with data storage, and discuss fast algorithms as a challenge problem. "
   ]
  },
  {
   "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": "7a214369",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The `movies` sheet contains 4 columns: id, name, year, and rank. `id` appears to be a running index counting the movies, `name` is the title of the movie (and the file appears to be organized alphabetically by name), `year` is the release date for the film, and `rank` is the user score (10 = really good) for the film on IMDb. \n",
    "\n",
    "There are 388,269 movies in the file. This can (with an investment of time) be determined by scrolling all the way to the end of the file and seeing the top index. We can be more efficient and use the built-in count function to determine the number of movies `=COUNTA(B2:B)`."
   ]
  },
  {
   "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": "323075e7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The `directors` sheet includes 3 columns: id, First Name, Last Name. `id` is a running index, and the name columns are self-explanatory. \n",
    "\n",
    "There are 86,880 directors total in this sheet. "
   ]
  },
  {
   "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": "071f0b2a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The `movies_directors` sheet includes 2 columns: `movie_id` and `director_id`. `movie_id` corresponds to the `id` column in the `movies` sheet, while `director_id` correspondss to the `id` in the directors sheet.\n",
    "\n",
    "There are 371,180 total rows in this sheet. This answer does not really make sense – we know there are 388,269 movies in total, so I would expect just as many entries here. Perhaps there are a bunch of movies without directors? "
   ]
  },
  {
   "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": "b76300ed",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "My favorite movie is \"Wayne's World\" (at least it's top 5), and that has movie id = 360290. The director was Penelope Sphereis, who has director id = 75368. In the `movies_directors` sheet, this `movie_id` and `director_id` match up confirming my answer from **1c**. "
   ]
  },
  {
   "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": "75b691c9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The `movies_genres` sheet includes 2 columns: `movie_id` and `genre`. `movie_id` corresponds to the `id` column in the `movies` sheet, while `genre` is one of several potential genres for the movie.\n",
    "\n",
    "There are 395119 total rows in this sheet. A quick glance at the sheet reveals two things: (i) there are several movies that do not have an identified genre (e.g., movie_id = 3), and (ii) there are movies that have multiple genres (e.g., movie_id = 8). \n",
    "\n",
    "It is hard to know how many rows to expect given these two facts, but given that many films fall into multiple genres it makes sense this sheet has more rows than there are total movies."
   ]
  },
  {
   "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": "84dbe588",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "There are only 88,680 directors, so we could make a file that only has 88,680 rows and store all the information in the 4 sheets. "
   ]
  },
  {
   "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": "923e6492",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Below you will determine the numbers necessary to calculate the true answers to these problems, but we can get a sense of the order of magnitude in a relatively straightforward fashion. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b6d7da9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We need two columns for first and last name. We need $3N_\\mathrm{movie}$ columns where $N_\\mathrm{movie}$ is the most movies directed by *any* director. In a single sheet this would be `movie1`, `movie2`, ..., `movieN`, plus the associated `year` and `rank`. From `movies_directors` we see that director 8 has 35 movie credits, so this is *at least* 105 additional columns."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab28f876",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "At maximum another $21N_\\mathrm{movie}$ columns are required to account for the different genres for each movie. This is likely overly conservative, no film belongs to every genre – let's say 5 is a reasonable number per movie (e.g., Action, Sci-Fi, Fantasy, Comedy, Short). Then this is another 175 columns."
   ]
  },
  {
   "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": "8e63965f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "For the four sheets there are: $4 \\times 388{,}269 + 3 \\times 88{,}680 + 2 \\times 371{,}180 + 2 \\times 395{,}119 = 3{,}351{,}714$ entries\n",
    "\n",
    "For a single sheet there are: $282 \\times 88{,}680 = 25{,}007{,}760$ entries"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "322aa0da",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "What we see here is that it is very inefficient/expensive to record \"nothing\". "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7877f0e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Suppose there is a director that only has one film credit. In the single sheet solution, we need to record that `movie2` = `NULL`, and `movie3` and so on. This information has a cost (storage), AND, there is essentially nothing learned from said information. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31d0723f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The reason the data have been organized into several sheets (or shall we call them \"data tables\"; yeah! let's call them \"tables\") is that it allows us to store far less information. There are some columns that we otherwise would not need (in a single table there is no need for an `id`, whereas the multi-table solution has at least one id in every table). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e14824a8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The `id` however is very powerful, as it is what allows the connection between the different tables."
   ]
  },
  {
   "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": "8fa41f7b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Scorsese has director `id` = 71645. \n",
    "\n",
    "If you are scrolling or use built in functions, you can find that the 40 films that Scorsese has directed are: [7842, 8183, 10702, 13395, 13804, 25192, 27108, 37304, 42328, 45312, 47130, 54209, 56304, 67388, 82967, 123849, 131780, 163603, 163730, 177369, 181766, 183593, 185704, 185751, 193231, 199510, 209158, 212717, 214872, 230947, 230963, 253470, 270971, 316709, 326155, 352863, 362473, 364368, 379931, 382309]\n",
    "\n",
    "If we copy that list of movie numbers to the `movies` sheet, we can then use a `FILTER` to find the years:  \n",
    "`=FILTER(C2:C1000000, A2:A1000000 = G10)`  where G10 is 7842. This filter can then be copied to all rows below the first to result in the following years (this is sorted by title alphabetically):\n",
    "\n",
    "[1985, 1993, 1974, 1992, 1978, 2004, 1987, 1967, 2005, 1972, 1999, 1991, 1995, 1986, 2006, 2002, 1990, 1964, 1974, 1983, 1997, 2004, 1988, 1978, 1988, 1990, 1973, 1995, 1999, 1989, 1977, 1995, 1980, 1970, 1976, 1959, 1963, 1967, 1985, 2003]"
   ]
  },
  {
   "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": "1aadc6df",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We can again use `group by` to solve this problem in the `movies` table:\n",
    "\n",
    "`=QUERY(A1:C500000, \"select C, count(C) group by C order by count(C) desc limit 25\", 1)`\n",
    "\n",
    "From this we find that 2002 had the most movies, with 12056."
   ]
  },
  {
   "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",
    "        sort_list.append(unsort[1])\n",
    "    else:\n",
    "        sort_list.insert(0,unsort[1])\n",
    "    for u in unsort[2:]:\n",
    "        for idx, sl in enumerate(sort_list):\n",
    "            n = len(sort_list)\n",
    "            if u <= sl:\n",
    "                sort_list.insert(idx, u)\n",
    "                break\n",
    "            elif idx + 1 == n:\n",
    "                sort_list.insert(idx+1, u)\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",
    "            arr[i], arr[ptr] = arr[ptr], arr[i]\n",
    "            ptr += 1\n",
    "    arr[ptr], arr[r] = arr[r], arr[ptr]\n",
    "    return ptr\n",
    "\n",
    "def quicksort(l, r, arr):\n",
    "    if len(arr) == 1:\n",
    "        return arr\n",
    "    if l < r:\n",
    "        pi = sort_pivot(l, r, arr)\n",
    "        quicksort(l, pi-1, arr)\n",
    "        quicksort(pi+1, r, arr)\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..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52c1d37c",
   "metadata": {},
   "source": []
  }
 ],
 "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
}