{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"cs1001.py , Tel Aviv University, Fall 2017-2018
\n",
"![](\"http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Recitation 5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We continued discussing complexity. Then we discussed higher-order functions and mentioned lambda expressions.\n",
"\n",
"### Takeaways:\n",
"\n",
"\n",
" - In order to analyze the time complexity of a code, try to bound the number of \"basic operations\" performed by your code. If your code contains loops try to understand their structure (series or parallel, and dependent or independent). \n",
" This may help bounding the overall complexity.
\n",
" - Lambda expressions are a method for writing short functions. Note that they are rather limited as only expressions (which have a value) can appear after \":\".
\n",
" - Higher-order functions are quite useful and may lead to a more compact code.
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Code for printing several outputs in one cell (not part of the recitation):"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from IPython.core.interactiveshell import InteractiveShell\n",
"InteractiveShell.ast_node_interactivity = \"all\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Reminder: Big O notation\n",
"\n",
"Given two functions $f(n)$ and $g(n)$,\n",
"\n",
"$f(n) = O(g(n))$ \n",
" If and only if there exist $c > 0 $ and $n_{0}\\in \\mathbb{R}$ such that\n",
" $\\forall n>n_0$ \n",
" $|f(n)| \\leq c\\cdot|g(n)|$ "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Series Loops\n",
"Let $n$ denote the input size.\n",
"Let $f_1(n) = O(g_1(n))\\;$ and $f_2(n)=O(g_2(n))$.\n",
"\n",
" for i in range(f1(n))):\n",
" O(1)\n",
" for j in range(f_2(n)):\n",
" O(1)\n",
"\n",
"We showed that $f_1(n) + f_2(n) = O(g_1(n) + g_2(n))$ and that $f_1(n) + f_2(n) = O(max(g_1(n), g_2(n)))$\n",
"\n",
"\n",
"Show that $f_1 + f_2 + ... + f_k = O(f_{max})$. That is, in a finite constant sum of functions, the dominate function defines the growth rate.\n",
"A private case is that of a polynomial.\n",
"\n",
"\n",
"\n",
"### Independednt nested oops\n",
"\n",
" for i in range(f1(n)):\n",
" for j in range(f2(n)):\n",
" O(1)\n",
"\n",
"Show that $f_1(n) \\cdot f_2(n) = O(g_1(n) \\cdot g_2(n))$.\n",
"\n",
"\n",
"### Dependent nested loops\n",
"\n",
" for i in range(f1(n)):\n",
" for j in range(i):\n",
" O(1)\n",
" Use $\\sum$ to bound the time complexity in this case\n",
"\n",
"$\\sum_{i=1}^{n}{i} = O(n^2)$ - the arithmetic series\n",
"\n",
"$\\sum_{i=1}^{n}{2^i} = O(2^n)$ - the geometric series"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Exercise - Analyze loops:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"for i in range(1,n+1):\n",
" j=1\n",
" while j<=n:\n",
" j += 1 # O(n**2)\n",
" j += 7 # O(n**2), inner loop does n/7 iterations for each outer loop\n",
" j *= 2 # O(n*log(n))\n",
" j *= 7 # O(n*log(n)), change log bases is like multiplying by a constant\n",
" j **= 2 # O(n*log(log(n))), we need to take a log on both sides *twice* (also for this case, j should start from 2) \n",
" j += i # O(n*log(n)), the sum of 1/i from i=1 to n is O(log(n))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Lambda expressions and higher-order functions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Expressions:\n",
"Anonymous vs. named values"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1024\n",
"1024\n"
]
}
],
"source": [
"print(2**10)\n",
"\n",
"x = 2**10\n",
"print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Functions:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lambda expressions can be used for creating anonymous functions (and named ones as well)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(lambda x: x+2)(3)\n",
"\n",
"plus2 = lambda x : x + 2\n",
"plus2(3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Example: A function that returns a function: make power"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"100"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"1000"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def make_pow(n):\n",
" def fixed_pow(x):\n",
" return x**n\n",
" return fixed_pow\n",
"\n",
"square = make_pow(2)\n",
"cube = make_pow(3)\n",
"\n",
"square(10)\n",
"cube(10)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"100"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"1000"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def make_pow(n):\n",
" return lambda x : x ** n\n",
"\n",
"square = make_pow(2)\n",
"cube = make_pow(3)\n",
"\n",
"square(10)\n",
"cube(10)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Example: A function that takes a function as its argument (function as an input): sorted"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['amirgil', 'amirrub', 'daniel', 'michal']"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lst = [\"michal\", \"amirrub\", \"daniel\", \"amirgil\"]\n",
"\n",
"sorted(lst)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\"sorted\" can recieve a function as an argument and use it to sort the input list.\n",
"The function is given as the \"key\" argument to \"sorted\".\n",
"Note that the \"key\" is used for ordering the elements without changing them.\n",
"\n",
"examples: sort by length, sort by reverse lexicographical order"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['michal', 'daniel', 'amirrub', 'amirgil']"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"['michal', 'daniel', 'amirrub', 'amirgil']"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"['amirrub', 'michal', 'daniel', 'amirgil']"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sorted(lst, key = lambda s : len(s))\n",
"sorted(lst, key = len)\n",
"sorted(lst, key = lambda s : s[::-1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"another example: sort by the int value of the string elements"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['11', '232', '3']"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"['3', '11', '232']"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lst2 = [\"232\", \"11\", \"3\"]\n",
"sorted(lst2)\n",
"sorted(lst2, key=int)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Example: another function that gets a function as its input"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"55"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def sum_naturals(n):\n",
" total = 0\n",
" for k in range(1,n+1):\n",
" total += k\n",
" return total\n",
"\n",
"sum_naturals(10)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"385"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def sum_squres(n):\n",
" total = 0\n",
" for k in range(1,n+1):\n",
" total += k**2\n",
" return total\n",
"\n",
"sum_squres(10)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's make it a general function that gets another function as a parameter:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def summation(n, term):\n",
" total = 0\n",
" for k in range(1,n+1):\n",
" total += term(k)\n",
" return total"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The equivalent to sum_naturals and sum_squares:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"55"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"385"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"term_naturals = lambda x : x\n",
"summation(10, term_naturals)\n",
"\n",
"term_squares = lambda x : x**2\n",
"summation(10, term_squares)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Approximating $\\pi$:\n",
"\n",
"The following (infinite) sum slowly converges to $\\pi$:\n",
"$\\frac{8}{1\\cdot 3} + \\frac{8}{5\\cdot 7} + \\frac{8}{9\\cdot11} + \\ldots$\n",
"We use \"summation\" to compute the sum of the first $n$ elements in this series"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3.091623806667838"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"3.1365926848388144"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"3.1415926035880983"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"term_pi = lambda k : 8 / ((4*k-1) * (4*k-3))\n",
"\n",
"summation(10, term_pi)\n",
"summation(100, term_pi)\n",
"summation(10000000, term_pi)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Packing and Unpacking arguments using *\n",
"\n",
"The function below can recieve any number of of values as its input,\n",
"all are packed into a tuple named \"params\", in this case.\n",
"The content of a tuple can be unpacked using * when passed as input to another method, as if you'd passed every value separately."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Separate each param using * (unpacking):"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[50, 51, 52, 53, 54]\n",
"bad range\n"
]
},
{
"ename": "TypeError",
"evalue": "() takes 3 positional arguments but 4 were given",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m100\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m50\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m55\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m100\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m55\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m50\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m100\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m50\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m55\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m56\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m# more than three arguments given to func\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mprint_consecutive_sublist\u001b[0;34m(lst, func, *params)\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0mparams\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mfunc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0mparams\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0mfunc\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;32mlambda\u001b[0m \u001b[0mlst\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mj\u001b[0m \u001b[1;33m:\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m:\u001b[0m\u001b[0mj\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mi\u001b[0m \u001b[1;33m<\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32melse\u001b[0m \u001b[1;34m\"bad range\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m100\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m50\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m55\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: () takes 3 positional arguments but 4 were given"
]
}
],
"source": [
"def print_consecutive_sublist(lst, func, *params):\n",
" func(lst, *params)\n",
"\n",
"func = lambda lst, i, j : print(lst[i:j] if i < j else \"bad range\")\n",
"print_consecutive_sublist([i for i in range(100)], func, 50,55)\n",
"print_consecutive_sublist([i for i in range(100)], func, 55,50)\n",
"print_consecutive_sublist([i for i in range(100)], func, 50,55,56) # more than three arguments given to func"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Leave params as tuple:"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[43, 44, 50, 55, 90]\n"
]
}
],
"source": [
"def print_sublist(lst, func, *params):\n",
"# print(*params)\n",
"# print(params)\n",
" func(lst, params)\n",
" \n",
"func2 = lambda lst, tup : print([x for x in lst if x in tup])\n",
"print_sublist([i for i in range(100)], func2, 50,55, 43, 44, 90)"
]
}
],
"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.4.4"
}
},
"nbformat": 4,
"nbformat_minor": 1
}