{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

cs1001.py , Tel Aviv University, Fall 2017-2018

\n", "" ] }, { "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", "
  1. In order to analyze the time complexity of a code, try to bound the number of \"basic operations\" performed by your code.\n", " If your code contains loops try to understand their structure (series or parallel, and dependent or independent). This may help bounding the overall complexity.
    2. \n", "
  2. Lambda expressions are a method for writing short functions.\n", " Note that they are rather limited as only expressions (which have a value) can appear after \":\".\n", "
    3. \n", "
  3. Higher-order functions are quite useful and may lead to a more compact code.\n", "
    4. \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "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": "markdown", "metadata": {}, "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 \n", " # for each outer loop\n", " j *= 2 # O(n*log(n))\n", " j *= 7 # O(n*log(n)), change log bases is like \n", " # multiplying by a constant\n", " j **= 2 # O(n*log(log(n))), we need to take a log on both sides \n", " # *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": [ "Anonymous vs. named values" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "x = 2**10\n", "print(x)\n", "\n", "print(2**10)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lambda expressions can be used for creating anonymous functions (and named ones as well)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "12" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "8" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "12" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(lambda x: x+2)(6)\n", "(lambda x: x+2)(10)\n", "plus_2 = lambda x: x+2\n", "plus_2(6)\n", "plus_2(10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Example: A function that returns a function" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "100" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "1000" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "100" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def make_pow(n):\n", " return lambda x: pow(x,n)\n", "\n", "sqr = make_pow(2)\n", "sqr(10)\n", "\n", "cub = make_pow(3)\n", "cub(10)\n", "\n", "make_pow(2)(10)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "and now without lambda" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "100" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def make_pow(n):\n", " def fixed_exp_pow(x):\n", " return pow(x,n)\n", " return fixed_exp_pow\n", "\n", "make_pow(2)(10)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Example: A function that takes a function as its argument (function as an input)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "lst = [\"michal\", \"daniel\", \"amirr\", \"amirg\"]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lexicographical string sorting:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['amirg', 'amirr', 'daniel', 'michal']" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "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": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['amirr', 'amirg', 'michal', 'daniel']" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['amirr', 'amirg', 'michal', 'daniel']" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['amirg', 'michal', 'daniel', 'amirr']" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lst = [\"michal\", \"daniel\", \"amirr\", \"amirg\"]\n", "sorted(lst, key= lambda x : len(x))\n", "sorted(lst, key= len)\n", "sorted(lst, key= lambda x : x[::-1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "another example: sort by the int value of the string elements" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['111', '22', '3']" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "['3', '22', '111']" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lst = [\"3\", \"22\", \"111\"]\n", "sorted(lst)\n", "sorted(lst, key = int)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Example: another function that gets a function as its input" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "55" ] }, "execution_count": 19, "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": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "385" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def sum_sqrs(n):\n", " total = 0\n", " for k in range(1, n+1):\n", " total += k*k\n", " return total\n", "\n", "sum_sqrs(10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These two functions are quite similar.\n", "We could write a function that computes the summation of $n$ elements, for a given natural number $n$ and a function \"term\" that for every $i$ returns the $i$th element in the sum." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3025" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def summation(n, term):\n", " total = 0\n", " for k in range(1, n+1):\n", " total += term(k)\n", " return total\n", "\n", "def cub(k):\n", " return k*k*k\n", "\n", "summation(10, cub)\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following (infinite) sum slowly converges to pi:\n", "\n", "$\\frac{8}{1\\cdot 3} + \\frac{8}{5\\cdot 7} + \\frac{8}{9\\cdot11} + \\ldots$\n", "\n", "We use \"summation\" to compute the sum of the first $n$ elements in this series" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3.091623806667838" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "3.1365926848388144" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "3.1415426535898203" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def pi_term(i):\n", " return 8/((4*i-3)*(4*i-1))\n", "\n", "def pi(n):\n", " return summation(n, pi_term)\n", "\n", "pi(10)\n", "pi(100)\n", "pi(10000)" ] }, { "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", "\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": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 10 55 3\n", "(2, 10, 55, 3)\n" ] }, { "data": { "text/plain": [ "3300" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def mult(*params):\n", " result = 1\n", " print(*params)\n", " print(params)\n", " for elem in params:\n", " result *= elem\n", " return result\n", "\n", "mult(2,10,55,3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Example: Another two functions that gets a function as an input" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[50, 51, 52, 53, 54]\n", "bad range\n" ] }, { "ename": "TypeError", "evalue": "() missing 1 required positional argument: 'j'", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[0;32m 7\u001b[0m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ml\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;32m 8\u001b[0m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ml\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;36m45\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 9\u001b[1;33m \u001b[0mprint_consecutive_sublist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ml\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;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m\u001b[0m in \u001b[0;36mprint_consecutive_sublist\u001b[1;34m(lst, func, *params)\u001b[0m\n\u001b[0;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[1;32m----> 2\u001b[1;33m \u001b[1;32mreturn\u001b[0m \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[0;32m 3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 4\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 5\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;31mTypeError\u001b[0m: () missing 1 required positional argument: 'j'" ] } ], "source": [ "def print_consecutive_sublist(lst, func, *params):\n", " return func(lst, *params)\n", "\n", "\n", "func = lambda lst, i, j : print(lst[i:j] if i