Lab_ex_1_1_solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ex 1.1: MapReduce with Python Functional Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Python *map* function\n",
    "Python has e built in *map* function -> [see python docs](https://docs.python.org/3/library/functions.html#map)\n",
    "* ``map(function, iterable object)`` applies a function to every member of the object (=data structure)\n",
    "* iterable objects are e.g. lists, dicts, arrays, ... but also custom data structures (see [here](https://thispointer.com/python-how-to-make-a-class-iterable-create-iterator-class-for-it/))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "[2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "#example\n",
    "def Plus1(a):\n",
    "    return a+1\n",
    "\n",
    "A = [1,2,3,4]\n",
    "print(A)\n",
    "B = list(map(Plus1,A)) #need to cast map output to list\n",
    "print(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "[3, 4, 5, 6]\n",
      "[2, 3, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "#example 2 - map with an function that takes arguments\n",
    "from functools import partial\n",
    "\n",
    "def PlusX(a,x):\n",
    "    return a+x\n",
    "\n",
    "\n",
    "A = [1,2,3,4]\n",
    "print(A)\n",
    "B = list(map(partial(PlusX,x=2),A)) #use partial to fix parameters \n",
    "print(B)\n",
    "\n",
    "C = [1,1,3,3]\n",
    "D = list(map(PlusX,A,C)) #or input multiple iterable objects\n",
    "print(D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "#example 3 - map with lmbda functions\n",
    "A = [1,2,3,4]\n",
    "B = list(map(lambda x:x+1,A ))#implement function directly with lambda\n",
    "print(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1.36691163e+01, 1.16081894e+01, 1.37120847e+01, 1.91991025e+01,\n",
       "        1.90059722e+01, 1.23887328e+01, 7.02569513e+00, 5.40141882e+00,\n",
       "        5.58483169e+00, 9.28200851e+00],\n",
       "       [1.19472693e+01, 1.09313841e+01, 9.67121058e+00, 1.26998757e+01,\n",
       "        9.17013841e+00, 1.19564895e+01, 4.89097648e-04, 1.15094487e+01,\n",
       "        8.93705633e-01, 1.13762110e+01],\n",
       "       [3.09757314e-01, 4.94931732e+00, 1.02461709e+01, 3.40997642e+00,\n",
       "        3.59472747e-01, 3.48346780e+00, 1.42075364e+01, 3.97518079e+00,\n",
       "        1.77159990e+01, 6.57241568e+00],\n",
       "       [1.98746799e+01, 1.17357972e+00, 2.24796716e+00, 3.60969462e+00,\n",
       "        1.48534526e+01, 1.11338900e+01, 1.26198122e+01, 6.48757051e+00,\n",
       "        1.43298623e+01, 4.02227966e+00],\n",
       "       [1.35291557e+01, 1.89600300e+01, 1.58467061e+01, 8.16671297e+00,\n",
       "        1.38836915e+01, 6.68432791e+00, 3.18352768e-01, 2.94693449e+00,\n",
       "        1.35167916e+01, 1.73976897e+01],\n",
       "       [8.03193091e+00, 1.89156120e+01, 4.99902406e+00, 8.29842267e+00,\n",
       "        9.97384391e-01, 8.09540279e+00, 8.53533472e+00, 5.66961265e+00,\n",
       "        1.40854353e+00, 6.06308756e+00],\n",
       "       [6.11293774e+00, 1.04899022e+01, 1.11043854e+01, 1.23170039e+01,\n",
       "        2.24833232e+00, 9.55727488e+00, 1.61305382e+00, 9.07987453e+00,\n",
       "        1.65755760e+01, 1.56162431e+01],\n",
       "       [2.82618836e+00, 9.28877369e+00, 1.29193388e+01, 9.65129847e+00,\n",
       "        1.27401276e+01, 7.46763080e+00, 1.85298135e+01, 1.47006857e+01,\n",
       "        8.60139608e+00, 1.67001977e+01],\n",
       "       [4.47420519e+00, 1.10607011e+01, 1.06767500e+01, 1.06768533e+01,\n",
       "        4.93219459e+00, 1.63763709e+01, 1.04987060e+01, 5.30509905e+00,\n",
       "        3.53962239e-02, 9.60318509e+00],\n",
       "       [1.97565990e+01, 1.44158548e+01, 2.78107776e+00, 1.45603724e+01,\n",
       "        1.24666923e+01, 5.52154654e+00, 1.08500604e+01, 1.44921006e+01,\n",
       "        1.58734558e+00, 1.34703601e+01]])"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#example 4 - Numpy has map \"build in\"\n",
    "import numpy as np\n",
    "A = np.random.rand(10,10)*20\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "#apply function directly on each element of an array\n",
    "def isLarger10(x):\n",
    "    return x>10\n",
    "\n",
    "B = isLarger10(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ True,  True,  True,  True,  True,  True, False, False, False,\n",
       "        False],\n",
       "       [ True,  True, False,  True, False,  True, False,  True, False,\n",
       "         True],\n",
       "       [False, False,  True, False, False, False,  True, False,  True,\n",
       "        False],\n",
       "       [ True, False, False, False,  True,  True,  True, False,  True,\n",
       "        False],\n",
       "       [ True,  True,  True, False,  True, False, False, False,  True,\n",
       "         True],\n",
       "       [False,  True, False, False, False, False, False, False, False,\n",
       "        False],\n",
       "       [False,  True,  True,  True, False, False, False, False,  True,\n",
       "         True],\n",
       "       [False, False,  True, False,  True, False,  True,  True, False,\n",
       "         True],\n",
       "       [False,  True,  True,  True, False,  True,  True, False, False,\n",
       "        False],\n",
       "       [ True,  True, False,  True,  True, False,  True,  True, False,\n",
       "         True]])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### *Reduce* in Python\n",
    "*functools* also provides a *reduce* function. Again, it will take a function and one ore more iterable objects as arguments. (see [API](https://docs.python.org/3/library/functools.html#functools.reduce))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sum of the list elements is : 17\n",
      "The maximum element of the list is : 6\n"
     ]
    }
   ],
   "source": [
    "# importing functools for reduce() \n",
    "import functools \n",
    "  \n",
    "# initializing list \n",
    "lis = [ 1 , 3, 5, 6, 2, ] \n",
    "  \n",
    "def addIt(a,b):\n",
    "    return a+b\n",
    "\n",
    "# using reduce to compute sum of list \n",
    "print (\"The sum of the list elements is : \",end=\"\") \n",
    "print (functools.reduce(addIt,lis)) \n",
    "  \n",
    "# using reduce to compute maximum element from list \n",
    "print (\"The maximum element of the list is : \",end=\"\") \n",
    "print (functools.reduce(lambda a,b : a if a > b else b,lis)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Splitting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[4, 5, 6]\n",
      "[7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "import more_itertools as mit\n",
    "\n",
    "A=[1,2,3,4,5,6,7,8,9]\n",
    "B=list(mit.chunked(A, 3)) #split into lists of max size 3\n",
    "\n",
    "for i in B: #iterate over the spitts \n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['t', 'h', 'i', 's', ' ']\n",
      "['i', 's', ' ', 'a', ' ']\n",
      "['s', 'h', 'o', 'r', 't']\n",
      "[' ', 't', 'e', 'x', 't']\n",
      "[' ', 'i', 'n', ' ', 'f']\n",
      "['o', 'r', 'm', ' ', 'o']\n",
      "['f', ' ', 'a', ' ', 'p']\n",
      "['y', 't', 'h', 'o', 'n']\n",
      "[' ', 's', 't', 'r', 'i']\n",
      "['n', 'g']\n"
     ]
    }
   ],
   "source": [
    "A='this is a short text in form of a python string'\n",
    "B=list(mit.chunked(A, 5)) #split into lists of max size 5\n",
    "\n",
    "for i in B: #iterate over the spitts \n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: build a simple *Character Count* Algorithm based on the above *split, map* and *reduce* operators "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "#some text from NYTimes\n",
    "text = ' Byron Spencer, handing out water and burgers to protesters outside Los Angeles City Hall, said he was both “elated and defeated” by word of the new charges. He said he had seen countless surges of outrage over police brutality against black men, only to have it happen again. “I’m 55, I’m black and I’m male — I’ve seen the cycle,” he said. “It’s almost like PTSD constantly having this conversation with my son.” Cierra Sesay reacted to the charges at a demonstration in the shadow of the State Capitol in Denver. “It’s amazing, it’s another box we can check,” she said. “But it goes up so much higher. It’s about the system.” In San Francisco, Tevita Tomasi — who is of Polynesian descent and described himself as “dark and tall and big” — said he regularly faced racial profiling, evidence of the bigger forces that must be overcome. On Wednesday, he distributed bottled water at what he said was his first demonstration, but one that would not be his last. What would stop him from protesting?'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* HINT: use list pf *python* [dictionaries](https://docs.python.org/3/tutorial/datastructures.html#dictionaries) to store the character counts in the map\n",
    "* HINT 2: merge the dicts in reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CharCount(char):\n",
    "    return {char:1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 1}\n",
      "{'a': 1}\n",
      "{'b': 1}\n"
     ]
    }
   ],
   "source": [
    "#test the count function\n",
    "\n",
    "print(CharCount('a'))\n",
    "print(CharCount('a'))\n",
    "print(CharCount('b'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [],
   "source": [
    "#now run over the full text\n",
    "mapping=list(map(CharCount,text))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{' ': 1},\n",
       " {'B': 1},\n",
       " {'y': 1},\n",
       " {'r': 1},\n",
       " {'o': 1},\n",
       " {'n': 1},\n",
       " {' ': 1},\n",
       " {'S': 1},\n",
       " {'p': 1},\n",
       " {'e': 1}]"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mapping[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('g', 1),\n",
       " ('g', 1),\n",
       " ('h', 1),\n",
       " ('h', 1),\n",
       " ('h', 1),\n",
       " ('h', 1),\n",
       " ('h', 1),\n",
       " ('h', 1),\n",
       " ('h', 1),\n",
       " ('h', 1)]"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mapping.sort()#sort\n",
    "mapping[500:510]#just show a part of the list of tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t={'a':1}\n",
    "list(t.keys())[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def sumUp(a,b): #merge dictionaries - a:output b:single item to be merged\n",
    "    key = list(b.keys())[0] #get the only key in b \n",
    "    if key in a: #check if char is in a\n",
    "        a[key] += 1\n",
    "    else:\n",
    "        a[key] = 1\n",
    "    return a\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{' ': 176,\n",
       " 'B': 2,\n",
       " 'y': 13,\n",
       " 'r': 38,\n",
       " 'o': 52,\n",
       " 'n': 49,\n",
       " 'S': 5,\n",
       " 'p': 10,\n",
       " 'e': 89,\n",
       " 'c': 25,\n",
       " ',': 11,\n",
       " 'h': 39,\n",
       " 'a': 72,\n",
       " 'd': 36,\n",
       " 'i': 49,\n",
       " 'g': 19,\n",
       " 'u': 17,\n",
       " 't': 72,\n",
       " 'w': 13,\n",
       " 'b': 16,\n",
       " 's': 59,\n",
       " 'L': 1,\n",
       " 'A': 1,\n",
       " 'l': 28,\n",
       " 'C': 3,\n",
       " 'H': 2,\n",
       " '“': 6,\n",
       " 'f': 12,\n",
       " '”': 6,\n",
       " '.': 10,\n",
       " 'v': 9,\n",
       " 'k': 5,\n",
       " 'm': 18,\n",
       " 'I': 8,\n",
       " '’': 8,\n",
       " '5': 2,\n",
       " '—': 3,\n",
       " 'P': 2,\n",
       " 'T': 3,\n",
       " 'D': 2,\n",
       " 'z': 1,\n",
       " 'x': 1,\n",
       " 'F': 1,\n",
       " 'O': 1,\n",
       " 'W': 2,\n",
       " '?': 1}"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "functools.reduce(sumUp, mapping)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}