lectures/Lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# An iterative smorgasboard: `yield`, memory layouts, and containers\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import HTML"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Generators, briefly"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class SentenceIterator:\n",
    "    def __init__(self, words): \n",
    "        self.words = words \n",
    "        self.index = 0\n",
    "        \n",
    "    def __next__(self): \n",
    "        try:\n",
    "            word = self.words[self.index] \n",
    "        except IndexError:\n",
    "            raise StopIteration() \n",
    "        self.index += 1\n",
    "        return word \n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "class Sentence:#an iterable\n",
    "    def __init__(self, text): \n",
    "        self.text = text\n",
    "        self.words = text.split()\n",
    "        \n",
    "    def __iter__(self):\n",
    "        return SentenceIterator(self.words)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'Sentence(%s)' % reprlib.repr(self.text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "a= Sentence(\"Mary had a little lamb whose fleece was white as snow.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary\n",
      "had\n",
      "a\n",
      "little\n",
      "lamb\n",
      "whose\n",
      "fleece\n",
      "was\n",
      "white\n",
      "as\n",
      "snow.\n"
     ]
    }
   ],
   "source": [
    "for item in a:\n",
    "    print(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary\n",
      "had\n",
      "a\n",
      "little\n",
      "lamb\n",
      "whose\n",
      "fleece\n",
      "was\n",
      "white\n",
      "as\n",
      "snow.\n"
     ]
    }
   ],
   "source": [
    "it = iter(a) #it is an iterator\n",
    "while True:\n",
    "    try:\n",
    "        nextval = next(it)\n",
    "        print(nextval)\n",
    "    except StopIteration:\n",
    "        del it\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**EVERY** collection in Python is iterable.\n",
    "\n",
    "Lets pause to let that sink in.\n",
    "\n",
    "We have already seen iterators are used to make for loops.\n",
    "They are also used tomake other collections\n",
    "\n",
    "- to loop over a file line by line from disk\n",
    "- in the making of list, dict, and set comprehensions\n",
    "- in unpacking tuples\n",
    "- in parameter unpacking in function calls (*args syntax)\n",
    "\n",
    "An iterator defines both `__iter__` and a `__next__` (the first one is only required to make sure an iterator IS an iterable)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "SO FAR: Iterator: retrieves items from a collection. The collection must implement `__iter__`.\n",
    "\n",
    "## Yield and generators\n",
    "\n",
    "A generator function looks like a normal function, but instead of returning values, it yields them. The syntax is (unfortunately) the same otherwise.\n",
    "\n",
    "Unfortunate, as a generator is a different beast. When the function runs, it creates a generator.\n",
    "\n",
    "The generator is an iterator.. It gets an internal implementation of `__next__` and `__iter__`, almost magically."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def gen123():\n",
    "    print(\"Hi\")\n",
    "    yield 1\n",
    "    print(\"Little\")\n",
    "    yield 2\n",
    "    print(\"Baby\")\n",
    "    yield 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function gen123 at 0x1059a4268> <class 'function'>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "generator"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(gen123, type(gen123))\n",
    "g = gen123()\n",
    "type(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<method-wrapper '__iter__' of generator object at 0x1059bc570>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#a generator is an iterator\n",
    "g.__iter__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<method-wrapper '__next__' of generator object at 0x1059bc570>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.__next__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hi\n",
      "Little\n",
      "Baby\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1, 2, 3)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(g),next(g), next(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-21-5f315c5de15b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "When `next` is called on it, the function goes until the first `yield`. The function body is now suspended and the value in the `yield` is then passed to the calling scope as the outcome of the next.\n",
    "\n",
    "When `next` is called again, it gets `__next__` called again (implicitly) in the generator, and the next value is yielded..., and so on...\n",
    "...until we reach the end of the function, the return of which creates a StopIteration in `next`.\n",
    "\n",
    "Any Python function that has the `yield` keyword in its body is a **generator function**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hi\n",
      "1\n",
      "Little\n",
      "2\n",
      "Baby\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# it = iter(a) #it is an iterator\n",
    "# while True:\n",
    "#     try:\n",
    "#         nextval = next(it)\n",
    "#         print(nextval)\n",
    "#     except StopIteration:\n",
    "#         del it\n",
    "#         break\n",
    "for i in gen123():\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Use the language: \"a generator yields or produces values\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Sentence:#an iterable\n",
    "    def __init__(self, text): \n",
    "        self.text = text\n",
    "        self.words = text.split()\n",
    "        \n",
    "    def __iter__(self):#one could also return iter(self.words)\n",
    "        for w in self.words:#note this is implicitly making an iter from the list\n",
    "            yield w\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'Sentence(%s)' % reprlib.repr(self.text)\n",
    "a=Sentence(\"Mary had a little lamb whose fleece was white as snow.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary\n",
      "had\n",
      "a\n",
      "little\n",
      "lamb\n",
      "whose\n",
      "fleece\n",
      "was\n",
      "white\n",
      "as\n",
      "snow.\n"
     ]
    }
   ],
   "source": [
    "# it = iter(a) #it is an iterator\n",
    "# while True:\n",
    "#     try:\n",
    "#         nextval = next(it)\n",
    "#         print(nextval)\n",
    "#     except StopIteration:\n",
    "#         del it\n",
    "#         break\n",
    "for w in a:\n",
    "    print(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Process address space\n",
    "\n",
    "What do we mean when we say a program is \"in memory\"?\n",
    "\n",
    "- compiled code must be loaded from disk into memory. \n",
    "- once your program starts, it must create(reserve) space for the variables it will use, and it must store and read values from those variables. \n",
    "\n",
    "The code, the reserved space, and the generated data all constitute a program's memory footprint.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Every operating system has a (different) convention for exactly where and how these different resources are actually laid out in memory. These conventions are called object file formats\n",
    "\n",
    "In Linux, the most common object format is called ELF, short for \"Executable and Linkable Format\", see diagram below.\n",
    "\n",
    "A simplified view of our example program looks like this in memory:the stack and the heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![](./segments.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### The Stack\n",
    "\n",
    "The stack keeps track of function calls and their data. \n",
    "\n",
    "- Whenever a function is called, a new chunk of memory is reserved at the top of the stack in order to store variables for that function. \n",
    "- This includes variables that you have defined inside your function and function parameters, but it also includes data that were generated automatically by the compiler. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- The most recognizable value in this latter category is the return address. When a function calls return, the computer starts executing instructions at this location that the function was originally called from\n",
    "\n",
    "- When a function returns, it removes its stack frame from the stack. This means that at any given point, the stack contains a record of which functions the program is currently in. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### The Heap\n",
    "\n",
    "- This is a problem if you want to create space for variables and then access them after the function returns. \n",
    "- The heap is another memory location which is not reclaimed after a function returns. It is explicitly managed, which means that in order to allocate a variable in it, you need to ask. What's more, when you're finished with that space, you need to say so. \n",
    "- This interface, explicitly requesting and releasing memory from the heap, is typically called memory management.\n",
    "- In C you do this directly using malloc/free. Python takes care of this for you using **garbage collection**.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## How does Python manage memory?\n",
    "\n",
    "In python, when you create a list, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "a=[1,2,3,4,5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- the layout in memory you get is not what you might have expected, perhaps  5 continuous integers, with some book-keeping at the beginning, - - either on the stack or the heap. \n",
    "- Such a data structure is called an array, but the above in python is not an array of integers. (although, so far, we have been treating it as such)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Python objects are allocated on the heap: an int is not an int\n",
    "\n",
    "An int is represented in Python as a C structure **allocated on the heap**\n",
    "\n",
    "The picture of this C structure looks a little bit  like this (taken from Jake Vanderplas's excellent [Why Python is Slow](https://jakevdp.github.io/blog/2014/05/09/why-python-is-slow/):\n",
    "\n",
    "![](http://jakevdp.github.io/images/cint_vs_pyint.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "On Jake's blog, he shows how this integer is represented:\n",
    "\n",
    "```C\n",
    "struct _longobject {\n",
    "    long ob_refcnt; // in PyObject_HEAD\n",
    "    PyTypeObject *ob_type; // in PyObject_HEAD\n",
    "    size_t ob_size; // in PyObject_HEAD\n",
    "    long ob_digit[1];\n",
    "};\n",
    "```\n",
    "\n",
    "\n",
    "Jake shows us how to poke at it.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "IntStruct(ob_digit=5, refcount=243)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import ctypes\n",
    "\n",
    "class IntStruct(ctypes.Structure):\n",
    "    _fields_ = [(\"ob_refcnt\", ctypes.c_long),\n",
    "                (\"ob_type\", ctypes.c_void_p),\n",
    "                (\"ob_size\", ctypes.c_ulong),\n",
    "                (\"ob_digit\", ctypes.c_long)]\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return (\"IntStruct(ob_digit={self.ob_digit}, \"\n",
    "                \"refcount={self.ob_refcnt})\").format(self=self)\n",
    "num = 5\n",
    "IntStruct.from_address(id(num)) # 5 is a struct allocated on heap and pointed to 200+ times!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Why is the refcount so high? Turns out Python keeps pre-allocates the first few integers!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Boxing and unboxing (or why is python slow)\n",
    "\n",
    "( again based off jakedevp's blog)\n",
    "\n",
    "So now, because ints are stored in this scheme, a simple addition involves a lot of work!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def test_add():\n",
    "    a=1\n",
    "    b=2\n",
    "    c = a+b\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  2           0 LOAD_CONST               1 (1)\n",
      "              3 STORE_FAST               0 (a)\n",
      "\n",
      "  3           6 LOAD_CONST               2 (2)\n",
      "              9 STORE_FAST               1 (b)\n",
      "\n",
      "  4          12 LOAD_FAST                0 (a)\n",
      "             15 LOAD_FAST                1 (b)\n",
      "             18 BINARY_ADD\n",
      "             19 STORE_FAST               2 (c)\n",
      "\n",
      "  5          22 LOAD_FAST                2 (c)\n",
      "             25 RETURN_VALUE\n"
     ]
    }
   ],
   "source": [
    "import dis\n",
    "dis.dis(test_add)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Python Addition\n",
    "\n",
    "1. Assign 1 to a\n",
    "    - 1a. Set a->PyObject_HEAD->typecode to integer\n",
    "    - 1b. Set a->val = 1\n",
    "2. Assign 2 to b\n",
    "    - 2a. Set b->PyObject_HEAD->typecode to integer \n",
    "    - 2b. Set b->val = 2\n",
    "3. call binary_add(a,b)\n",
    "    - 3a. find typecode in a->PyObject_HEAD\n",
    "    - 3b. a is an integer; value is a->val\n",
    "    - 3c. find typecode in b->PyObject_HEAD\n",
    "    - 3d. b is an integer; value is b->val\n",
    "    - 3e. call `binary_add<int, int>(a->val, b->val)` \n",
    "    - 3f. result of this is result, and is an integer.\n",
    "4. Create a Python object c\n",
    "    - 4a. set c->PyObject_HEAD->typecode to integer\n",
    "    - 4b. set c->val to result\n",
    "    \n",
    "So its never a simple addition...there is all this machinery around it. And this is to add two ints where `binary_add` is optimized in C. If these were user defined classes, there would be additional overhead from dunder methods for addition that we will talk about later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Lists\n",
    "\n",
    "A python list is represented by this struct:\n",
    "\n",
    "```C\n",
    "typedef struct {\n",
    "    long ob_refcnt;\n",
    "    PyTypeObject *ob_type;\n",
    "    Py_ssize_t ob_size;\n",
    "    PyObject **ob_item;\n",
    "    long allocated;\n",
    "} PyListObject;\n",
    "```\n",
    "\n",
    "Notice the `PyObject**`. This points to the contents of the list. What is this a list of? This is a list of `PyObject*`.  Each of those pointers when dereferenced gives us one of the integer structure above. The `ob_size` tells us the number of items on the list.\n",
    "\n",
    "Thus this is **an array of pointers to heap allocated inststruct**s.\n",
    "\n",
    "This is illustrated next (int 1 means an instruct with digit 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+b(%29%3A%0A++++a%3D%5B1,2,3,4,5%5D%0Aa%3D%5B1,2,3,4,5%5D%0Ab(%29&origin=opt-frontend.js&cumulative=false&heapPrimitives=true&textReferences=false&py=3&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400\"> </iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML('<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+b(%29%3A%0A++++a%3D%5B1,2,3,4,5%5D%0Aa%3D%5B1,2,3,4,5%5D%0Ab(%29&origin=opt-frontend.js&cumulative=false&heapPrimitives=true&textReferences=false&py=3&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400\"> </iframe>')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class ListStruct(ctypes.Structure):\n",
    "    _fields_ = [(\"ob_refcnt\", ctypes.c_long), \n",
    "                (\"ob_type\", ctypes.c_void_p),\n",
    "                (\"ob_size\", ctypes.c_ulong),\n",
    "                (\"ob_item\", ctypes.c_long), # PyObject** pointer cast to long \n",
    "                (\"allocated\", ctypes.c_ulong)]\n",
    "    def __repr__(self):\n",
    "        return (\"ListStruct(len={self.ob_size}, \"\n",
    "           \"refcount={self.ob_refcnt})\").format(self=self) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ListStruct(len=5, refcount=1)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = [1,2,3,4,5]\n",
    "Lstruct = ListStruct.from_address(id(L))\n",
    "Lstruct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[IntStruct(ob_digit=1, refcount=2493),\n",
       " IntStruct(ob_digit=2, refcount=994),\n",
       " IntStruct(ob_digit=3, refcount=871),\n",
       " IntStruct(ob_digit=4, refcount=500),\n",
       " IntStruct(ob_digit=5, refcount=243)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PtrArray = Lstruct.ob_size * ctypes.POINTER(IntStruct)\n",
    "L_values = PtrArray.from_address(Lstruct.ob_item)\n",
    "[ptr[0] for ptr in L_values] # ptr[0] dereferences the pointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## What do others do?\n",
    "\n",
    "In julia, from the Julia Manual:\n",
    "\n",
    ">In the most general case, an array may contain objects of type Any. For most computational purposes, arrays should contain objects of a more specific type, such as Float64 or Int32.\n",
    "\n",
    "```julia\n",
    "a = Real[]    # typeof(a) = Array{Real,1}\n",
    "if (f = rand()) < .8\n",
    "    push!(a, f)\n",
    "end\n",
    "```\n",
    "\n",
    "Because a is a an array of abstract type Real, it must be able to hold any Real value. Since Real objects can be of arbitrary size and structure, a must be represented as an array of pointers to individually allocated Real objects. Because f will always be a Float64, we should instead, use:\n",
    "\n",
    "```julia\n",
    "a = Float64[] # typeof(a) = Array{Float64,1}\n",
    "```\n",
    "\n",
    "which will create a contiguous block of 64-bit floating-point values that can be manipulated efficiently.\n",
    "\n",
    "And in C, you allocate explicitly, either on the heap or stack:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting simple.c\n"
     ]
    }
   ],
   "source": [
    "%%file simple.c\n",
    "#include <stdlib.h>\n",
    "#include <stdio.h>\n",
    "\n",
    "int* just_a_func(){\n",
    "    int *heapintlist;\n",
    "    int i;\n",
    "    int stackintlist[3]; /*Allocate in this functions frame on stack*/\n",
    "    heapintlist = (int *) malloc(3*sizeof(int)); /*Allocate on heap*/\n",
    "    for (i = 0; i < 3; i++) {\n",
    "        stackintlist[i] = i;\n",
    "        heapintlist[i] =i;\n",
    "    }\n",
    "    for (i = 0; i < 3; i++) {\n",
    "        printf(\"stackintlist %d\\n\",stackintlist[i]);\n",
    "        printf(\"heapintlist %d :  %d\\n\", i, heapintlist[i]);\n",
    "    }\n",
    "    return heapintlist; /*stackintlist unallocated here */\n",
    "}\n",
    "int main() {\n",
    "    int* heapintlist;\n",
    "    int i;\n",
    "    \n",
    "    heapintlist=just_a_func();\n",
    "    for (i = 0; i < 3; i++) {\n",
    "        heapintlist[i] =i+5;\n",
    "        printf(\"heapintlist %d :  %d\\n\", i, heapintlist[i]);\n",
    "    }\n",
    "    free(heapintlist);\n",
    "    /* garbage in &heapinlist[i] after this */\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "stackintlist 0\n",
      "heapintlist 0 :  0\n",
      "stackintlist 1\n",
      "heapintlist 1 :  1\n",
      "stackintlist 2\n",
      "heapintlist 2 :  2\n",
      "heapintlist 0 :  5\n",
      "heapintlist 1 :  6\n",
      "heapintlist 2 :  7\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "gcc -o simple -g simple.c\n",
    "./simple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "But wait. In Python you can append to lists. Ad Infinitum (well upto VM memory). Whats a `ob_size` doing in our struct then? Turns out Python lists are implemented in something called a dynamic array!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\n",
    "### Arrays\n",
    "\n",
    "A static array is a contiguous slab of memory of known size, such that n items (ints ot structs or whatever) can fit in. This is a great data structure. Why?\n",
    "\n",
    "- constant time index access: a[i] is O(1)...just seek i*sizeof(int) for example down\n",
    "- linear time traversal or search: 1 unit per loop iteration means O(n) in loop.\n",
    "- locality in memory: its one int after another\n",
    "\n",
    "Tuples in Python are fixed size, static arrays..\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "But the big problem is, what if I want to add something more beyond the end of the array? Then we fall flat, so we use..\n",
    "\n",
    "### Dynamic Arrays\n",
    "\n",
    "What python does is first create a fixed size array of these `Pyobject*` pointers on the heap. Then, as you append, it uses its own algorithm to figure out when to expand the size of the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist=[1,2,3,4]\n",
    "alist.append(5)\n",
    "alist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "From https://svn.python.org/projects/python/trunk/Objects/listobject.c :\n",
    "\n",
    "```C\n",
    "/* This over-allocates proportional to the list size, making room\n",
    "     * for additional growth.  The over-allocation is mild, but is\n",
    "     * enough to give linear-time amortized behavior over a long\n",
    "     * sequence of appends() in the presence of a poorly-performing\n",
    "     * system realloc().\n",
    "     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...\n",
    "     */\n",
    "new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(64, 72, 80, 88)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys\n",
    "sys.getsizeof([]),sys.getsizeof([1]),sys.getsizeof([1,1]), sys.getsizeof([1,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[]\n",
    "sys.getsizeof(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "96"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.append(1)\n",
    "sys.getsizeof(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "96"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.append(1)\n",
    "sys.getsizeof(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1]\n",
      "96\n",
      "[1, 1, 1, 1]\n",
      "96\n",
      "[1, 1, 1, 1, 1]\n",
      "128\n",
      "[1, 1, 1, 1, 1, 1]\n",
      "128\n",
      "[1, 1, 1, 1, 1, 1, 1]\n",
      "128\n",
      "[1, 1, 1, 1, 1, 1, 1, 1]\n",
      "128\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "192\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "264\n",
      "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "264\n"
     ]
    }
   ],
   "source": [
    "for j in range(16):\n",
    "    a.append(1)\n",
    "    print(a)\n",
    "    print(sys.getsizeof(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Dynamic Arrays performance\n",
    "\n",
    "Lets assume we start with a size of 1 and then double the size each time. It then takes $lg(n)$ doublings for the array to have n slots.\n",
    "\n",
    "Notice that we might not get the continuously allocated memory we want. So we'll have to recopy to a larger array.\n",
    "\n",
    "The last n/2 numbers wouldnt move at all. The previous n/4 would have moved once, the previous n/8 twice, and so on\n",
    "\n",
    "Thus the total number of movements is \n",
    "\n",
    "$$ \\sum_{i=1}^{lg(n)} i*\\frac{n}{2^{i+1}} \\le \\frac{n}{2} \\sum_{i=1}^{\\infty} \\frac{i}{2^i} = n$$\n",
    "\n",
    "This is an amazing result. The work of reallocation is still $O(n)$ on the average, as if a single array had been allocated in advance! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Containers  vs Flats\n",
    "\n",
    "Earlier we saw how Python lists contained references to integer (\"digit\")+metdata based structs on the heap. \n",
    "\n",
    "We call sequences that hold such \"references\" to objects on the heap **Container Sequences**. Examples of such container sequences are `list, tuple, collections.deque`.\n",
    "\n",
    "There are collections in python which contain contiguous \"typed\" memory (which itself is allocated on the heap). We call these **Flat Sequences**. Such containers in python 3 are:\n",
    "`str, bytes, bytearray, memoryview, array.array`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "You have probably extensively used one of these which is not mentioned yet. This is numpy's ndarray: `np.array`.\n",
    "\n",
    "All of these are faster as they work with **contiguous blocks of uniformly formatted memory**.\n",
    "\n",
    "From Fluent Python:\n",
    "> Container sequences hold references to the objects they contain, which may be of any type, while flat sequences physically store the value of each item within its own memory space, and not as distinct objects. Thus, flat sequences are more compact, but they are limited to holding primitive values like characters, bytes, and numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is also a more general way of thinking about data structures. \n",
    "\n",
    ">**Contiguously-allocated** structures are composed of single slabs of memory, and include arrays, matrices, heaps, and hash tables.\n",
    "\n",
    ">**Linked** data structures are composed of distinct chunks of memory bound together by pointers, and include lists, trees, and graph adjacency lists.\n",
    "\n",
    "(Steven S Skiena. The Algorithm Design Manual)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- A critical advantake of something like a contiguous memory array is that indexing is a constant time operation, as opposed to worst-case O(n), as we saw in linked lists. \n",
    "- Other benefits include a tighter size and a locality of memory which benefits cache and general memory transport."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Mutable vs Immutable\n",
    "\n",
    "A recurrent theme in this course is that of the mutability of objects. One can also study containers based on their mutability. **Mutable Sequences** in python 3 are:\n",
    "\n",
    "`list, bytearray, array.array, collections.deque, memoryview`\n",
    "\n",
    "whereas immutable seuqnces in Python 3 are\n",
    "\n",
    "`tuple, str, bytes`\n",
    "\n",
    "Lets learn about some of these collections in python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### array.array\n",
    "\n",
    "The list type is nice and very flexible, but if you need to store many many (millions) of floating point variables, array.array is a better option. It stores just the bytes representing the type, so its just like a contiguous C array of things in RAM, and also just like a numpy array. \n",
    "\n",
    "`array.array` IS mutable, and you dont need to allocate ahead of time (reallocation will be done).\n",
    "\n",
    "The constructor is: \n",
    "\n",
    "`array(typecode [, initializer]) -- create a new array`\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from array import array\n",
    "from random import random\n",
    "#generator expression instead of list comprehension\n",
    "floats_aa=array('d', (random() for i in range(10**8)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floats_aa.itemsize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array.array, 0.5667536435553536)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(floats_aa), floats_aa[5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "floats_list=[random() for i in range(10**8)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Some behavior that you see might be unexpected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.88 s, sys: 424 ms, total: 3.31 s\n",
      "Wall time: 3.38 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "for f in floats_aa:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.27 s, sys: 3.36 s, total: 6.63 s\n",
      "Wall time: 8.06 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "for f in floats_list:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, so a regular python list on 100 million floats only costs double. Why would you use `array.array` then? And Why is accessing floats in an `array.array` so slow. The answer to the latter is that in using the standard python access, like in a `for` loop each float is **boxed** by the python runtime. You saw this earlier!\n",
    "\n",
    "Remember the int based structs we had earlier? In an `array.array` or in `numpy` for that matter, when you \"iterate\" over the array, and use the ints you get, what python does is to take that 32 bits or 64 bits from memory, wrap it up into one of these structs, and hand it to you. You asked for a python int after all."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "What it also means is that ops on `array.array` which can be done with C are fast, but access into python is slow. \n",
    "\n",
    "This is why `numpy.ndarray` is written in C, with ops like `numpy.dot` written in C as well. (None of the `array.array` functionality is exposed with any complex operations under the hood, so its current use remains limited)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "If you want to use numerical stuff, use `numpy` arrays. But `array.array`s are still useful when a buffer needs to be shlepped between Python and C, for quick access to things. If you are using legacy code in C which ops on these lists, this is the way to do it fast. Indeed, otherwise lists can be faster because of this \"boxing\" penalty. (see https://www.python.org/doc/essays/list2str/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### memoryviews\n",
    "\n",
    "Memoryviews, inspired by numpy and scipy, let you handle slices of arrays without expensively copying bytes.\n",
    "\n",
    "Travis Oliphant, as quoted in Fluent:\n",
    ">A memoryview is essentially a generalized NumPy array structure in Python itself (without the math). It allows you to share memory between data-structures (things like PIL images, SQLlite databases, NumPy arrays, etc.) without first copying. This is very important for large data sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(int, 2)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import array\n",
    "numbers = array.array('h', [-2, -1, 0, 1, 2])#short signed ints\n",
    "type(numbers[0]), numbers.itemsize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<memory at 0x1059ae348>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "memv = memoryview(numbers)\n",
    "memv_oct = memv.cast('B') # no copy\n",
    "memv_oct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[254, 255, 255, 255, 0, 0, 1, 0, 2, 0]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(memv_oct)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We can dive into a structure. Once we have read the data once from a file (get it at https://www.dropbox.com/s/e4rleswrcgwt3hp/pcanim.gif?dl=0 ), it does not need to be recopied just to inspect it. Here we use the struct module, which is useful to share data with C like systems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'GIF89a\\xe8\\x03\\x90\\x01'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import struct\n",
    "fmt = '<3s3sHH'#little endian, 2 seq 3 bytes, 2 unsigned shorts\n",
    "with open(\"pcanim.gif\", 'rb') as fd:\n",
    "    readit = fd.read()\n",
    "    msg = memoryview(readit) #no copy\n",
    "header = msg[:10] # 10 byte view, no copy, imagine the savings\n",
    "bytes(header)# finally a copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b'GIF', b'89a', 1000, 400)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "struct.unpack(fmt, header)#type/version/width/height"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### indexing and slicing\n",
    "\n",
    "As we saw above, **memoryviews support indexing and slicing**. Multidimensional, even."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'bytes'>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(111, <memory at 0x1059ae048>)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bs = b'Hello world'\n",
    "print(type(bs))\n",
    "memv = memoryview(bs)\n",
    "memv[4], memv[2:4] #the second is a view"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((11,), (1,))"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "memv.shape, memv.strides"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Or from numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "zerosmv = memoryview(np.zeros((10, 11, 12)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((10, 11, 12), (1056, 96, 8), 3, 8)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zerosmv.shape, zerosmv.strides, zerosmv.ndim, zerosmv.itemsize #c contigous, "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " Memoryviews, just like numpy arrays can be multi-dimensional, and come with some of the properties numpy arrays have..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### mutable vs immutable data structures\n",
    "\n",
    "bytestrings, also known as **bytes** such as `b'hello'` are read-only in python, and the corresponding memoryviews are too..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(memoryview, bytes)"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(msg), type(readit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'bytes' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-41-e0404bf63a4d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mreadit\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'bytes' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "readit[0]=5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "cannot modify read-only memory",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-42-a6dfc5182e57>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mmsg\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: cannot modify read-only memory"
     ]
    }
   ],
   "source": [
    "msg[0]=5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "memoryviews follow the \"read-only\" status of bytes.\n",
    "\n",
    "**bytearrays** as opposed to bytes, are read-write, which leads to being able to pre-allocate a \"buffer\", get a memoryview on it, and use the slice syntax.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import os.path\n",
    "with open(\"pcanim.gif\", 'rb') as fd:\n",
    "    data = bytearray(os.path.getsize(\"pcanim.gif\"))\n",
    "    fd.readinto(data)\n",
    "mv = memoryview(data)\n",
    "mv[0]=5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This gives us a way to do something we couldn't achieve by any other means - read from a file (or receive from a socket) directly into the middle of some existing buffer\n",
    "\n",
    "```python\n",
    "buf = bytearray(...) # pre-allocated to the needed size\n",
    "mv = memoryview(buf)\n",
    "numread = f.readinto(mv[some_offset:])\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### the buffer protocol\n",
    "\n",
    "Using memoryviews in this fashion\n",
    "is how Python objects expose raw byte buffers (arrays), to both C/cython as well as python. This is called the buffer protocol, and is specified at the C level. Its out of our scope, but google it!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Kurt Smith, in the O-Reilly cython book:\n",
    ">The new buffer protocol is a C-level protocol. The new buffer protocol’s most important feature is its ability to represent the same underlying data in different ways. It allows NumPy arrays, several Python built-in types, and Cython-level array-like objects to share the same data without copying. With Cython, we can also easily extend the buffer protocol to work with data coming from an external library.\n",
    "\n",
    "These are python types you can create a memoryview from:\n",
    "\n",
    "- ndarray, py2 string, py3 unicode\n",
    "- bytes and bytearray types, array.array, ctypes arrays\n",
    "- third party, like in PIL\n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}