hw1_Workbook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HW1 - Intro to the Map Reduce Paradigm  \n",
    "__ `MIDS w261: Machine Learning at Scale | UC Berkeley School of Information | Spring 2018`__\n",
    "\n",
    "Welcome to Machine Learning at Scale! This first homework assignment introduces one of the core strategies in distributed processing: divide and conquer. We'll use the simplest of tasks, word counting, to illustrate the difference between a scalable and non-scalable algorithm. You will be working with the text of _Alice in Wonderland_ to put these ideas into practice using Python and Bash scripting. By the end of this week you should be able to:\n",
    "* ... __describe__ the Bias-Variance tradeoff as it applies to Machine Learning.\n",
    "* ... __explain__ why we consider word counting to be an \"Embarrassingly Parallel\" task.\n",
    "* ... __estimate__ the runtime of embarrassingly parallel tasks using \"back of the envelope\" calculations.\n",
    "* ... __implement__ a Map Reduce algorithm using the Command Line.\n",
    "* ... __set-up__ a Docker container and know why we use them for this course.\n",
    "\n",
    "You will also  become familiar (if you aren't already) with `defaultdict`, `re` and `time` in Python, linux piping and sorting, and Jupyter magic commands `%%writefile` and `%%timeit`. __Please refer to the `README` for detailed submission instructions__.\n",
    "\n",
    "__IMPORTANT:__ If you're not familiar with linux, you should read the following tutorial reagrding **piping** and **redirecting**: https://ryanstutorials.net/linuxtutorial/piping.php You will need to understand the differences to answer some of the later questions.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Notebook Set-Up\n",
    "Before starting your homework run the following cells to confirm your setup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sys.version_info(major=3, minor=7, micro=5, releaselevel='final', serial=0)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# confirm you are running Python 3\n",
    "import sys\n",
    "sys.version_info"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# imports\n",
    "import re\n",
    "import sys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a folder for any data you download locally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mkdir: cannot create directory `data': File exists\n"
     ]
    }
   ],
   "source": [
    "!mkdir data\n",
    "# NOTE: the contents of this directory will be ignored by git."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 1: Introductions\n",
    "\n",
    "`The Caterpillar and Alice looked at each other for some time in silence: at last the Caterpillar took the hookah out of its mouth, and addressed her in a languid, sleepy voice. \"Who are you?\" said the Caterpillar.`   \n",
    "<div style=\"text-align: right\"> -- Lewis Carroll, _Alice's Adventures in Wonderland_, Chapter 4 </div>\n",
    "\n",
    "\n",
    "__Tell us about yourself! Briefly describe where you live, how far along you are in MIDS, what other classes you are taking and what you want to get out of w261.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> I am an electrical engineer at Intel Corp. I will be graduating MIDS in Spring 2022. I am only taking W261 this semester. I do not have much experince with data science or machine learning since my background is in hardware design. I plan a career shit to become a machine learning engineer and I would like to learn as much as I can about distributed processin in machine learning so that I am ready to take on a full-time posistion in this field.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 2: Bias - Variance\n",
    "__In 1-2 sentences explain the bias-variance trade off. Describe what it means to \"decompose\" sources of error. How is this used in machine learning?__ Please use mathematical equation(s) to support your explanation. (Use `$` signs to take advantage of $\\LaTeX$ formatting, eg. `$f(x)$` will look like: $f(x)$). Please also cite any sources that informed your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The tradeoff of verience and bias can be explained as such that a learning algorithm with low bias must be “flexible” so that it can fit the data well. But if the learning algorithm is too flexible (for instance, too linear), it will fit each training data set differently, which will translate to a high variance. So when we build supervied machine learnting models, we want to make sure that we are controlling the bais-variance tradeoff.   \n",
    "By decomposing the source of error, we mean that the reducible error can be broken into “error due to squared bias” and “error due to variance.\n",
    "sited: https://insidebigdata.com/2014/10/22/ask-data-scientist-bias-vs-variance-tradeoff/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 3: Tokenizing\n",
    "A number of our assignments this term will involve extracting information from text. A common preprocessing step when working with raw files is to 'tokenize' (i.e. extract words from) the text. Within the field of Natural Language Processing a lot of thought goes into what specific tokenizing makes most sense for a given task. For example, you might choose to remove punctuation or to consider punctuation symbols  'tokens' in their own right. __In this question you'll use the Python `re` module to create a tokenizer to use when you perform WordCount on the _Alice In Wonderland_ text.__\n",
    "\n",
    "### Q3 Tasks:\n",
    "\n",
    "* __a) short response:__ In the Naive Bayes algorithm (which we'll implement next week), we'll estimate the _likelihood_ of a word by counting the number of times it appears and dividing by the size of the vocabulary (total number of unique words). Using the text: *\"Alice had an adventure that took alice to wonderland\"*, give a concrete example of how two different tokenizers could cause us to get two different results on this calculation. [`HINT`: _you should not need to read up on Naive Bayes to answer this question_]  \n",
    "  \n",
    "\n",
    "* __b) short response:__ When tokenizing in this assignment we'll remove punctuation and discard numerical digits by making everything lowercase and then capturing only consecutive letters a to z. Suppose __`tokenize(x)`__ is a Python function that performs the desired tokenization. What would __`tokenize(\"By-the-bye, what became of Alice's 12 hats?!\")`__ output? Type the answer in the space provided below.\n",
    "\n",
    "\n",
    "* __c) code:__  Fill in the regular expression pattern in the cell labeled `part c` so that the subsequent call to `re.findall(RE_PATTERN, ...)` returns the tokenization described above. [`HINT`: _we've taken care of the lowercase part for you. If regex is new to you, check out the [`re`  documentation](https://docs.python.org/3/library/re.html) or [this PyMOTW tutorial](https://pymotw.com/2/re/)._]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3 Student Answers:\n",
    "> __a)__\n",
    "There is a total of 3006 unique For example whem taking the tokenizers with which appeared 228 times and the tokenizer walk which appeared 5 times in the text file. \n",
    "The calculation for estimating the NB algorithim is (228/3006 for \"with\") and (5/3006 for walk). So the likelihood for \"with\" = 0.0758 and 0.00166 for \"walk\"\n",
    "> __b)__ by the bye what became of alice s 12 hats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Part C - Fill in the regular expression\n",
    "RE_PATTERN = re.compile(\"[a-z]{1,}\")          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['by', 'the', 'bye', 'what', 'became', 'of', 'alice', 's', 'hats']\n"
     ]
    }
   ],
   "source": [
    "# Tokenize - DO NOT MODIFY THIS CELL, just run it as is to check your pattern\n",
    "words = re.findall(RE_PATTERN, \"By-the-bye, what became of Alice's 12 hats?!\".lower())\n",
    "print(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Load the Data\n",
    "` \"Please would you tell me\", said Alice, a little timidly, for she was not quite sure whether it was good manners for her to speak first, \"why your cat grins like that?\"`  \n",
    "<div style=\"text-align: right\">  -- Lewis Carroll, _Alice's Adventures in Wonderland_, Chapter 4  </div>\n",
    "\n",
    "For the main part of this assignment we'll be working with the free plain text version of _Alice's Adventures in Wonderland_ available from Project Gutenberg. __Use the first two cells below to download this text and preview the first few lines.__ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100  170k  100  170k    0     0   533k      0 --:--:-- --:--:-- --:--:--  533k\n"
     ]
    }
   ],
   "source": [
    "# Download Full text \n",
    "# NOTE: feel free to replace 'curl' with 'wget' or equivalent command of your choice.\n",
    "!curl \"https://www.gutenberg.org/files/11/11-0.txt\" -o data/alice.txt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "﻿The Project Gutenberg eBook of Alice’s Adventures in Wonderland, by Lewis Carroll\n",
      "\n",
      "This eBook is for the use of anyone anywhere in the United States and\n",
      "most other parts of the world at no cost and with almost no restrictions\n",
      "whatsoever. You may copy it, give it away or re-use it under the terms\n",
      "of the Project Gutenberg License included with this eBook or online at\n"
     ]
    }
   ],
   "source": [
    "# Take a peak at the first few lines\n",
    "!head -n 6 data/alice.txt\n",
    "# NOTE: If you are working in JupyterLab on Docker you may not see the output \n",
    "# below due to an encoding issue... in that case, use a terminal on Docker to \n",
    "# execute this head command and confirm that the file has downloaded properly, \n",
    "# this encoding issue should not affect your work on subsequent HW items."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'd also like you to develop a habit of creating small files with simulated data for use in developing, debugging and testing your code. The jupyter magic command `%%writefile` is a convenient way to do this. __Run the following cells to create a test data file for use in our word counting task.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting data/alice_test.txt\n"
     ]
    }
   ],
   "source": [
    "%%writefile data/alice_test.txt\n",
    "This is a small test file. This file is for a test.\n",
    "This small test file has two small lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alice_test.txt\n"
     ]
    }
   ],
   "source": [
    "# confirm the file was created in the data directory using a grep command:\n",
    "!ls data | grep test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 4: Word Count in Python\n",
    "\n",
    "Over the course of this term you will also become very familiar writing Python programs that read from standard input and using Linux piping commands to run these programs and save their output to file. __In this question you will write a short python script to perform the Word Count task and then run your script on the _Alice in Wonderland_ text__. You can think of this like a 'baseline implementation' that we'll later compare to the parallelized version of the same task.\n",
    "\n",
    "### Q4 Tasks:\n",
    "\n",
    "* __a) code:__ Complete the Python script in the file __`wordCount.py`__. Read the docstrings carefully to be sure you understand the expected behavior of this function. Please do not code outside of the marked location.\n",
    "\n",
    "\n",
    "* __b) testing:__ Run the cell marked `part b` to call your script on the test file we created above. Confirm that your script returns the correct counts for each word by visually comparing the output to the test file. \n",
    "\n",
    "\n",
    "* __c) results:__ When you are confident in your implementation, run the cell marked `part c` to count the number of occurrences of each word in _Alice's Adventures in Wonderland_. In the same cell we'll pipe the output to file. Then use the provided `grep` commands to check your answers.\n",
    "\n",
    "\n",
    "* __d) short response:__ Suppose you decide that you'd really like  a word and its plural (e.g. 'hatter' and 'hatters' or 'person' and 'people') to be counted as the same word. After we have run the wordcount would it be more efficient to post-process your output file or discard your output file and start the analysis over with a new tokenizer? Explain your reasoning briefly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4 Student Answers:\n",
    "> __a-c)__ _Complete the coding portions of this question before answering 'e'._\n",
    "\n",
    "> __d)__ I would discard the output file and start the analysis again beacuse doing it into steps is not effecient in terms of processing space "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "# part a - DO YOUR WORK IN wordCount.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a 2\n",
      "file 3\n",
      "for 1\n",
      "has 1\n",
      "is 2\n",
      "lines 1\n",
      "small 3\n",
      "test 3\n",
      "this 3\n",
      "two 1\n"
     ]
    }
   ],
   "source": [
    "# part b - DO NOT MODIFY THIS CELL, just run it as is to test your script\n",
    "!python wordCount.py < data/alice_test.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part c - DO NOT MODIFY THIS CELL, just run it as is to perform the word count.\n",
    "!python wordCount.py < data/alice.txt > data/alice_counts.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take a look at the first 10 words & their counts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a 695\n",
      "abide 2\n",
      "able 1\n",
      "about 102\n",
      "above 3\n",
      "absence 1\n",
      "absurd 2\n",
      "accept 1\n",
      "acceptance 1\n",
      "accepted 2\n"
     ]
    }
   ],
   "source": [
    "!head data/alice_counts.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Check your results:__ How many times does the word \"alice\" appear in the book? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alice 403\n"
     ]
    }
   ],
   "source": [
    "# EXPECTED OUTPUT: 404\n",
    "!grep alice data/alice_counts.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Check your results:__ How many times does the word \"hatter\" appear in the book? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hatter 56\n",
      "hatters 1\n"
     ]
    }
   ],
   "source": [
    "# EXPECTED OUTPUT: 56\n",
    "!grep hatter data/alice_counts.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Check your results:__ How many times does the word \"queen\" appear in the book? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "queen 76\n",
      "queens 1\n"
     ]
    }
   ],
   "source": [
    "# EXPECTED OUTPUT: 76\n",
    "!grep queen data/alice_counts.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 5: Unix Sorting Practice\n",
    "Another common task in this course's assignments will be to make strategic use of sorting.     \n",
    "\n",
    "### Q5 Tasks:\n",
    "* __a) short response:__ What is the Big O complexity of the fastest comparison based sorting algorithms? [*HINT: If you need a Big O notation refresher, here's_ a [blog post](https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/), a [cheatsheet](http://bigocheatsheet.com), and a [thorough explanation](http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html).*]\n",
    "\n",
    "* __b) short response:__ What is the default sorting algorithm in MapReduce? What is the Big O complexity of this algorithm? Why do you think this algorithm was chosen? [*HINT: Julius Ceasar! (week 1 slides)*]\n",
    "\n",
    "* __c) code:__ write a unix command to check how many records are in your word count file.\n",
    "\n",
    "* __d) code:__ Write a unix command to sort your word count file alphabetically. Save (i.e. [redirect](https://superuser.com/questions/277324/pipes-vs-redirects)) the results to `data/alice_counts_A-Z.txt`. [*HINT: if Unix sort commands are new to you, start with [this biowize blogpost](https://biowize.wordpress.com/2015/03/13/unix-sort-sorting-with-both-numeric-and-non-numeric-keys/) or [this unixschool tutorial](http://www.theunixschool.com/2012/08/linux-sort-command-examples.html)*]\n",
    "\n",
    "* __e) code:__ Write a unix command to sort your word count file from highest to lowest count. Save (i.e. [redirect](https://superuser.com/questions/277324/pipes-vs-redirects)) your results to `data/alice_counts_sorted.txt`; then run the provided cell to print the top ten words. Compare your output to the expected output we provide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q5 Student Answers:\n",
    "> __a)__ The Big O complexity of the fastest comparison based sorting algorithims is O(nlogn)\n",
    "\n",
    "> __b)__ Merge sort is the default sorting algorithim for mapreduce. And the time complexity of it is O(nlogn). Merge sort is used beacuse in MapReduce the data come from different nodes to a single point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3006 data/alice_counts.txt\n"
     ]
    }
   ],
   "source": [
    "# part c - write a unix command to check how many records are in your word count file\n",
    "!wc -l data/alice_counts.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part d - unix command to sort your word counts alphabetically \n",
    "!sort data/alice_counts.txt -o data/alice_counts_A-Z.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a 695\n",
      "abide 2\n",
      "able 1\n",
      "about 102\n",
      "above 3\n",
      "absence 1\n",
      "absurd 2\n",
      "accept 1\n",
      "acceptance 1\n",
      "accepted 2\n"
     ]
    }
   ],
   "source": [
    "# part d - DO NOT MODIFY THIS CELL, run it as is to confirm your sort worked\n",
    "!head data/alice_counts_A-Z.txt   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part e - unix command to sort your word counts from highest to lowest count\n",
    "!sort -k 2nr data/alice_counts.txt -o data/alice_counts_sorted.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 1839\n",
      "and 942\n",
      "to 811\n",
      "a 695\n",
      "of 638\n",
      "it 610\n",
      "she 553\n",
      "i 546\n",
      "you 486\n",
      "said 462\n"
     ]
    }
   ],
   "source": [
    "# part e - DO NOT MODIFY THIS CELL, run it as is to confirm your sort worked\n",
    "!head data/alice_counts_sorted.txt  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table>\n",
    "<th>expected output for (d):</th>\n",
    "<th>expected output for (e):</th>\n",
    "<tr><td><pre>\n",
    "a\t695\n",
    "abide\t2\n",
    "able\t1\n",
    "about\t102\n",
    "above\t3\n",
    "absence\t1\n",
    "absurd\t2\n",
    "accept\t1\n",
    "acceptance\t1\n",
    "accepted\t2\n",
    "</pre></td>\n",
    "<td><pre>\n",
    "the\t1837\n",
    "and\t946\n",
    "to\t811\n",
    "a\t695\n",
    "of\t637\n",
    "it\t610\n",
    "she\t553\n",
    "i\t546\n",
    "you\t487\n",
    "said\t462\n",
    "</pre></td></tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 6: Parallel Word Count (part 1)\n",
    "What would happen if we tried to run our script on a much larger dataset? For one thing, it would take longer to run. However there is a second concern. The Python object that aggregates our counts (`defaultdict`) exists in memory on the machine running this notebook. If the vocabulary is too large for the memory space available we would crash the notebook. The solution? Divide and Conquer! Instead of running the script on the whole dataset at once, we could split our text up in to smaller 'chunks' and process them independently of each other. __In this question you'll use a bash script to \"parallelize\" your Word Count.__\n",
    "\n",
    "\n",
    "### Q6 Tasks:\n",
    "* __a) read provided code:__ The bash script `pWordCount_v1.sh` takes an input file, splits it into a specified number of 'chunks', and then applies an executable of your choice to each chunk. Read through this code and make sure you understand each line before you proceed. [`HINT:` _For now, ignore the 'student code' section -- you'll use that in part c._]\n",
    "\n",
    "\n",
    "* __b) short response:__ Below we've provided the command to use this script to apply your analysis (`wordCount.py`) to the _Alice_ text in 4 parallel processes. We'll redirect the results into a file called `alice_pCounts.txt.` Run this analysis and compare the count for the word 'alice' to your answer from Question 4. Explain what went wrong and describe what we have to add to `pWordCount_v1.sh` to fix the problem.\n",
    "\n",
    "\n",
    "* __c) code:__ We've provided a python script, `aggregateCounts_v1.py`, which reads word counts from standard input and combines any duplicates it encounters. Read through this script to be sure you understand how it is written. Then follow the instructions in `pWordCount_v1.sh` to make a one-line modification so that it accepts `aggregateCounts_v1.py` as a 4th argument and uses this script to combine the chunk-ed word counts. Run the cell below to confirm that you now get the correct results for your 'alice' count."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q6 Student Answers:\n",
    "> __b)__ This time we split the data into chucnks and found the count for each count but never aggregated counted to find the total count. We will have to pipe the output of each chunk's count into the reducer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part b - make sure your scripts are executable (RUN THIS CELL AS IS)\n",
    "!chmod a+x pWordCount_v1.sh\n",
    "!chmod a+x wordCount.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part b - parallel word count on Alice text (RUN THIS CELL AS IS)\n",
    "!./pWordCount_v1.sh 4 'data/alice.txt' 'wordCount.py' > 'data/alice_pCounts.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alice 113\n",
      "alice 126\n",
      "alice 122\n",
      "alice 42\n"
     ]
    }
   ],
   "source": [
    "# part b - check alice count (RUN THIS CELL AS IS)\n",
    "!grep alice data/alice_pCounts.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part c - make sure the aggregateCounts script is executable (RUN THIS CELL AS IS)\n",
    "!chmod a+x aggregateCounts_v1.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part c - parallel word count on Alice text (RUN THIS CELL AS IS)\n",
    "!./pWordCount_v1.sh 4 'data/alice.txt' \\\n",
    "                   'wordCount.py' \\\n",
    "                   'aggregateCounts_v1.py' \\\n",
    "                   > 'data/alice_pCounts.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alice\t403\n"
     ]
    }
   ],
   "source": [
    "# part c - check alice count (RUN THIS CELL AS IS)\n",
    "!grep alice data/alice_pCounts.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No manual entry for sort\n"
     ]
    }
   ],
   "source": [
    "!man sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 7: Parallel Word Count (part 2)\n",
    "Congratulations, you've just implemented a Map-Reduce algorithm! From here on out, we'll refer to the two python scripts you passed to `pWordCount_v1.sh` as '_mapper_' and '_reducer_'. The bash script itself served as our '_framework_' -- it split up the original input, then ___mapped___ our word counting script on to each chunk, then ___aggregated (a.k.a. reduced)___ the resulting files by piping them into our collation script.  Unfortunately, as you may have realized already, there is a major scalability concern with this particular implementation. __In this question you'll fix our implementation of parallel word count so that it will be scalable.__\n",
    "\n",
    "__HINT:__ MapReduce uses the Merge-Sort algorithm under the hood. Linux `sort` command has a merge option which you can use to simiulate the MapReduce framework. Use the `man sort` command to find more information on this option. \n",
    "\n",
    "### Q7 Tasks:\n",
    "\n",
    "* __a) short response:__ What is the potential scalability problem with the provided implementation of `aggregateCounts_v1.py`? Explain why this supposedly 'parallelized' Word Count wouldn't work on a really large input corpus.  [`HINT:` _see the intro to Q6_]\n",
    "\n",
    "\n",
    "* __b) code:__ Fortunately, a 'strategic sort' can solve this problem. Read the instructions at the top of `pWordCount_v2.sh` carefully then make your changes that alphabetically sort the output from the mappers (`countfiles`) before piping them into the reducer script.\n",
    "\n",
    "\n",
    "* __c) code:__ Write the main part of `aggregateCounts_v2.py` so that it takes advantage of the sorted input to add duplicate counts without storing the whole vocabulary in memory. Refer to the file docstring for more detailed instructions. Confirm that your implementation works by running it on both the test and true data files.\n",
    "\n",
    "\n",
    "* __d) short response:__ If you are paying close attention, this rewritten reducer sets us up for a truly scalable solution, but doesn't get us all the way there. In particular, while we chunked our data so it can be processed by multiple mappers, we're still streaming the entire dataset through one reduce script. If the vocabulary is too large to fit on a single computer, we might split the word counts in half after sorting them, then perform the reducing on two separate machines. Explain what could go wrong with this approach. (For now, ignore the question of how we'd sort a dataset that is too large to fit on a single machine and just focus on what might be wrong about the result of this split-in-half reducing).\n",
    "\n",
    "\n",
    "* __e) short response:__ Can you come up with a different way of splitting up the data that would allow us to perform the reducing on separate machines without needing any postprocessing? This is a theoretical question -- don't worry if you don't know how to implement your idea in a bash script, just describe how you'd want to split the sorted counts into different files to be reduced separately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q7 Student Answers:\n",
    "\n",
    "> __a)__ The problem we will run into If we try to run the script with a very large data is that the object \"defaultdict\" which aggregates our counts exists in memory on the machine running this notebook. If the vocabulary is too large for the memory space available the notebook will crash.\n",
    "\n",
    "> __b-c)__ _complete the coding portions of this question before answering d and e._\n",
    "\n",
    "> __d)__ If we try to perform the reducing in two different machines, there might be a syncarnization probelem where the same this might end up account for two times\n",
    "\n",
    "> __e)__ Use Hadoop or spark framework"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add permissions to your new files (RUN THIS CELL AS IS)\n",
    "!chmod a+x pWordCount_v2.sh\n",
    "!chmod a+x aggregateCounts_v2.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a 2\n",
      "file 1\n",
      "file 3\n",
      "for 1\n",
      "has 1\n",
      "is 2\n",
      "lines 1\n",
      "small 1\n",
      "small 3\n",
      "test 1\n",
      "test 3\n",
      "this 1\n",
      "this 3\n",
      "two 1\n"
     ]
    }
   ],
   "source": [
    "# part c - test your code on the test file (RUN THIS CELL AS IS)\n",
    "!./pWordCount_v2.sh 4 'data/alice_test.txt' \\\n",
    "                   'wordCount.py' \\\n",
    "                   'aggregateCounts_v2.py'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {},
   "outputs": [],
   "source": [
    "# part c - run your code on the Alice file (RUN THIS CELL AS IS)\n",
    "!./pWordCount_v2.sh 4 'data/alice.txt' \\\n",
    "                   'wordCount.py' \\\n",
    "                   'aggregateCounts_v2.py' \\\n",
    "                   > 'data/alice_pCounts.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alice 113\n",
      "alice 235\n",
      "alice 361\n",
      "alice 403\n"
     ]
    }
   ],
   "source": [
    "# part c - confirm that your 'alice' count is correct (RUN THIS CELL AS IS)\n",
    "!grep alice data/alice_pCounts.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 8: Scalability Considerations\n",
    "In your reading for Week 2's live session, [Chapter1, section 2](https://lintool.github.io/MapReduceAlgorithms/MapReduce-book-final.pdf) of _Data Intensive Text Processing with MapReduce_, Lin and Dyer discuss a number of \"Big Ideas\" that underlie large scale processing: __scale \"out,\" not \"up\"; assume failures are common; move processing to the data; process data sequentially and avoid random access; hide system-level details from the application developer; and seamless scalability.__ Part of our work this semester will be to interact with these ideas in a practical way, not just a conceptual one.\n",
    "\n",
    "### Q8 Tasks:\n",
    "* __a) short response:__ What do Lin and Dyer consider the two features of an \"ideal algorithm\" from a scalability perspective?\n",
    "\n",
    "\n",
    "* __b) short response:__ The mapper script below (created on the fly using a little Jupyter magic) will help us illustrate the concept of scalability. Run the provided code which passes this mapper script to our parallel computation 'framework' and runs the 'analysis' on the _Alice_ text file. Note that we've omitted a reducer for simplicity. What do you observe about the time it takes to run this \"algorithm\" when we use 1, 2 and 4 partitions? Does it meet Lin and Dyer's criteria?\n",
    "\n",
    "\n",
    "* __c) short response:__ Let's try something similar with your Word Count analysis. Run the provided code to time your implementation with 1, 2, 4 and 8 partitions. What do you observe about the runtimes? Does this match your expectation? Speculate about why we might be seeing these times. What conclusions should we draw about the scalability of our implementation? [`HINT:` _consider the limitations of both your machine and our implementation... there are some competing forces at work, what are they?_]\n",
    "\n",
    "\n",
    "* __d) OPTIONAL:__ Which components of your Map-Reduce algorithm are affected by a change in the number of partitions? Does increasing the number of partitions increase or decrease the total time spent on each of these portions of the task? What tradeoff does this cause?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q8 Student Answers:\n",
    "\n",
    "> __a)__ In terms of data: given twice the amount of data, the same algorithm should take at most twice as long to run, all else being equal. Second, in terms of resources: given a cluster twice the size, the same algorithm should take no more than half as long to run\n",
    "\n",
    "> __b)__ Yes it does meet the Lin and Dyer's criteria. \n",
    "\n",
    "> __c)__ It does match the expectaitons, every time the partition was doubled and using the reducer, the time was reduced by almost a half. However; with my algorithm, I noticed an inconsistency with the time pattern.  \n",
    "\n",
    "> __d)__ Type your (OPTIONAL) answer here!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Run the following cells to create the mapper referenced in `part b`__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mkdir: cannot create directory `demo': File exists\n"
     ]
    }
   ],
   "source": [
    "!mkdir demo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting demo/mapper.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile demo/mapper.py\n",
    "#!/usr/bin/env python\n",
    "\"\"\"\n",
    "This mapper reads from STDIN and waits 0.001 seconds per line.\n",
    "Its only purpose is to demonstrate one of the scalability ideas.\n",
    "\"\"\"\n",
    "import sys\n",
    "import time\n",
    "for line in sys.stdin:\n",
    "    time.sleep(0.001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make sure the mapper is executable\n",
    "!chmod a+x demo/mapper.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Run the next three cells to apply our demo mapper with 1, 2 and 4 partitions.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.77 s ± 4.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 1 'data/alice.txt' 'demo/mapper.py'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.75 s ± 5.21 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 2 'data/alice.txt' 'demo/mapper.py'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.73 s ± 6.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 4 'data/alice.txt' 'demo/mapper.py'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Run the following cells to repeat this process with your word count algorithm.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "755 ms ± 2.95 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 1 'data/alice.txt' 'wordCount.py' 'aggregateCounts_v2.py' > 'data/tmp'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "753 ms ± 9.85 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 2 'data/alice.txt' 'wordCount.py' 'aggregateCounts_v2.py' > 'data/tmp'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "767 ms ± 3.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 4 'data/alice.txt' 'wordCount.py' 'aggregateCounts_v2.py' > 'data/tmp'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "814 ms ± 3.82 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 8 'data/alice.txt' 'wordCount.py' 'aggregateCounts_v2.py' > 'data/tmp'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "909 ms ± 5.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 16 'data/alice.txt' 'wordCount.py' 'aggregateCounts_v2.py' > 'data/tmp'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.11 s ± 4.79 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "!./pWordCount_v2.sh 32 'data/alice.txt' 'wordCount.py' 'aggregateCounts_v2.py' > 'data/tmp'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 9: Embarrassingly Parallel\n",
    "`\"If any one of them can explain it,\" said Alice, (she had grown so large in the last few minutes that she wasn’t a bit afraid of interrupting him,) \"I’ll give him sixpence. I don’t believe there’s an atom of meaning in it.\"`\n",
    "<div style=\"text-align: right\">  -- Lewis Carroll, _Alice's Adventures in Wonderland_, Chapter 12  </div>\n",
    "\n",
    "### Q9 Tasks:\n",
    "\n",
    "* __a) short response:__ Describe what we mean by 'Embarrassingly Parallel' in terms of word counting. Does this term describe a 'task'? an 'implementation of a task'? \n",
    "\n",
    "* __b) OPTIONAL__: Define this concept in terms of 'associative' and 'commutative' operations. [`HINT:` _Refer to Chapter 2 in DITP_ ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q9 Student Answers:\n",
    "\n",
    "> __a)__ In terms of word counting, emabarrasingly parallel describes the task of spreating th words to a number of parallel loads.\n",
    "\n",
    "> __b)__ When the operation is both associative and commutative, reducers can directly serve as combiners. In general,however, reducers and combiners are not interchangeable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Congratulations, you have completed HW1! Please refer to the readme for submission instructions.\n",
    "\n",
    "If you would like to provide feedback regarding this homework, please use the survey at: https://docs.google.com/forms/d/e/1FAIpQLSce9feiQeSkdP43A0ZYui1tMGIBfLfzb0rmgToQeZD9bXXX8Q/viewform"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.5"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "297px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_position": {
    "height": "951px",
    "left": "0px",
    "right": "1561px",
    "top": "106px",
    "width": "600px"
   },
   "toc_section_display": "block",
   "toc_window_display": true,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}