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

cs1001.py , Tel Aviv University, Winter 2020

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recitation 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We talked about binary numbers (with some theory) and base conversions and implemented an algorithm for base conversion (from decimal to 2<=b<=36).\n", "We examined Python's memory model and analyzed the efficiency of constructing a list using + or += operators.\n", "\n", "\n", "\n", "### Takeaways:\n", "1. Make sure you understand binary numbers and base conversions (including the algorithms for conversion to and from a base b to decimal). It is a very useful tool in computer science.\n", "2. Elements of a list can be changed from inside a function, if this list is given as a parameter. Note that one should use dedicated list functions or the [] operator for mutating the list.\n", "3. Use [Python tutor](http://www.pythontutor.com) in order to understand what's going on in terms of memory. It can be very helpful.\n", "4. Try to analyze the number of operations your function does to see how will its runtime scale as a function of the input (we will elabore on this soon).\n", " \n", "### Python tutor guidelines:\n", "Before you click \"Visualize Execution\" button, you may want to use the following settings (can be adjusted via the drop boxes next to the textbox):\n", "
    \n", "
  1. Python 3.6
    2. \n", "
  2. \n", " Show exited frames (Python)
    3. \n", "
  3. Render all objects on the heap
    4. \n", "
  4. Draw pointers as arrows [default]
    5. \n", "
\n", "\n", "\n", "## The binary system and base conversions\n", "When we count natural numbers, we use the decimal system. That is, we represent numbers in base 10, using 10 digits (0-9).\n", "Binary representation (base 2) uses two possible digits: 0-1.\n", "In general, a number in base $b$ will be represented using $b$ possible digits.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Base conversions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python has some built-in conversion methods from-and-to decimal, binary and other bases:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "bin(10)\n", "type(bin(10))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "hex(161)\n", "int(\"345\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "\n", "int(\"1101\", 2)\n", "int(\"a1\", 16)\n", "int(\"a1\", 2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Converting from binary to decimal\n", " \n", "Let $x_{[2]} = a_{n-1} ... a_1 a_0$ be the binary representation of a number with $n$ binary digits. \n", "The following formula returns its decimal representation:\n", " $$x_{[10]} = \\sum_{0 \\le k \\le n-1} a_k \\cdot 2^k$$\n", " \n", "Similarly, if $x_{[b]} = a_{n-1} ... a_0$ is represented in an arbitrary base with $b$ digits then:\n", " $$x_{[10]} = \\sum_{0 \\le k \\le n-1} a_k \\cdot b^k$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Converting from decimal to binary \n", "Converting from decimal to binary is done by integer division and modulo operations. \n", "Here is an implementation of the algorithm for conversion from decimal to a general base $b$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Our version for convert_base:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def convert_base(n,b):\n", " '''convert_base(int, int)->string\n", " Returns the textual representation \n", " of n(decimal) in base 2<=b<=10\n", " '''\n", " result = \"\"\n", " while n != 0:\n", " digit = n % b\n", " n //= b\n", " result = str(digit) + result\n", " \n", " return result\n", " \n", " \n", " \n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "convert_base(10,2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "convert_base(0, 2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Is the code above correct? What happens in the case where $n = 0$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Improved version of convert_base:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def convert_base(n,b):\n", " '''convert_base(int, int)->string\n", " Returns the textual representation \n", " of n(decimal) in base 2<=b<=10\n", " '''\n", " if n == 0:\n", " return \"0\"\n", " \n", " result = \"\"\n", " while n != 0:\n", " digit = n % b\n", " n //= b\n", " result = str(digit) + result\n", " \n", " return result\n", " \n", " \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "convert_base(0,2)\n", "convert_base(12,3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "convert_base(161,16)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The improved version above fails for $10string\n", " Returns the textual representation \n", " of n(decimal) in base 2<=b<=10\n", " '''\n", " assert 2 <= b <= 36\n", " \n", " if n == 0:\n", " return \"0\"\n", " \n", " result = \"\"\n", " alphabet = \"0123456789abcdefghijklmnopqrstuvwxyz\"\n", " while n != 0:\n", " ## Complete\n", " \n", " return result\n", " \n", " \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "convert_base(161, 16)\n", "convert_base(10, 2)\n", "convert_base(10, 80)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Memory model\n", "\n", "Understanding Python's memory model means understanding the way Python stores our variables in the memory and the way Python manipulates these variables when we perform operations on them.\n", "\n", "Memory management depends on various properties, including:\n", "* The precide method we use to change our variables\n", "* Whether our variable is of a mutable type or not\n", "* The specific location of our operation within the scope of the code\n", "\n", "Understanding this model will allow us to write better and more efficient code." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "#### Motivating examples:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def change_num(num):\n", " num = 999\n", "\n", " \n", "x = 30\n", "change_num(x)\n", "x\n", "\n", " \n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def add_to_list(lst):\n", " lst.append(999)\n", " \n", "mylst = [1,2,3]\n", "add_to_list(mylst)\n", "mylst" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def change_lst(lst):\n", " lst = []\n", "\n", "mylst = [1,2,3]\n", "change_lst(mylst)\n", "mylst" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Programs examined with [Python tutor](http:\\\\www.pythontutor.com):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#1 basics #####################################################\n", "a = 1000 #1\n", "b = \"hello\" #2\n", "a += len(b) #3\n", "c = 2*b[:2] #4\n", "if b!=c: #5\n", " c = b #6\n", "del c #7" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#2 lists #####################################################\n", "a = 1000 #1\n", "d = [a,2] #2\n", "d[1] = -1 #3\n", "a = 1003 #4\n", "for x in d: #5a\n", " x = 7 #5b" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#3 funcs #####################################################\n", "a = 1000 #1\n", "b = \"hello\" #2\n", "def is_palindrom(a): #3a\n", " b = a[::-1] #3b\n", " return a==b #3c\n", "is_pal = is_palindrom #4\n", "x = is_pal(b) #5" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#4 lists+funcs #####################################################\n", "a = 1000 #1\n", "d = [a,2] #2\n", "def f(a,d): #3a\n", " a = 2000 #3b\n", " d[0] = a #3c\n", " d = [] #3d\n", " return d #3e\n", "x = f(a,d) #4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Extend(), append(), sort(), and sorted():" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#5 – lists operators and methods #####################################################\n", "lst = [3,2,1]\n", "id(lst)\n", "lst\n", "lst = lst+[0] \n", "id(lst)\n", "lst\n", "lst.append(4)\n", "id(lst)\n", "lst\n", "lst.insert(1,5)\n", "id(lst)\n", "lst\n", "lst.extend([6,7])\n", "id(lst)\n", "lst\n", "lst += [8] \n", "id(lst)\n", "lst" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "lst\n", "id(lst)\n", "#sorted returns a sorted copy of the list, and does not change the original one\n", "lst2 = sorted(lst)\n", "id(lst)\n", "lst\n", "#list.sort() sorts in place, and does not return anything\n", "lst.sort()\n", "id(lst)\n", "lst" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## comparison between + and += " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In what follows we have two different implementations of the same operation: given an input $n$ we construct a list of the range $[0,...,n-1]$. The difference between the implementation is that in build_range1 we append items to our list using the command $lst = lst + [i]$ and in build_range2 we do this via the command $lst += [i]$, which, as we recall, invokes $lst.extend([i])$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### memory and running times" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "\n", "def build_range1(n):\n", " lst = []\n", " t0 = time.perf_counter()\n", " for i in range(n):\n", " lst = lst + [i]\n", " t1 = time.perf_counter()\n", " print(\"Extending a list n=\", n, \"times, using the + operator took\",t1-t0, \"seconds\")\n", "\n", "\n", "def build_range2(n):\n", " lst = []\n", " t0 = time.perf_counter()\n", " for i in range(n):\n", " lst += [i]\n", " t1 = time.perf_counter()\n", " print(\"Extending a list n=\", n, \"times, using the += operator (extend()) took\",t1-t0, \"seconds\")\n", "\n", "build_range1(20000)\n", "build_range2(20000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Empirically, calling $lst = lst + [i]$ is less efficient. Why is that?\n", "\n", "Since a new list is constructed every iteration the number of integers written to memory equals $1+2+ ... + n = \\frac{n \\cdot (n+1)}{2} \\approx \\frac{n^2}{2}$. Asymptotically speaking, the number of copy operations grows quadratically with $n$.\n", "\n", "Using invoke, the same list is extended again and again. The number of integers written to memory equals $n$. Asymptotically speaking, the number of copy operations grows linearly with $n$.\n", "\n", "What do we expect will happen if we double the input size $n=40000$?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "build_range1(40000)\n", "build_range2(40000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In accordance with the theory, the running time of the inefficient code increases by approximately $2^2 = 4$ as $n$ increased by a factor of $2$, while the running time of the efficient code increases by a factor of approximately $2$." ] } ], "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.0" } }, "nbformat": 4, "nbformat_minor": 1 }