<jupyter_start><jupyter_text>Lecture 15 Monday, October 30th 2017  Generators* A generator function looks like a normal function, but yields values instead of returning them. * The syntax is (unfortunately) the same otherwise ([PEP 255 -- Simple Generators](https://www.python.org/dev/peps/pep-0255/)).* A generator is a different beast. When the function runs, it creates a generator.* The generator is an iterator and gets an internal implementation of `__iter__` and `__next__`. * When `next` is called on the generator, the function proceeds 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`.* When next is called again, it gets `__next__` called again (implicitly) in the generator, and the next value is yielded.* This continues until we reach the end of the function, the return of which creates a `StopIteration` in next.Any Python function that has the `yield` keyword in its body is a generator function.  Example<jupyter_code>def mygen(N):
    for i in range(N):
        yield i**2

for vals in mygen(7):
    print(vals)<jupyter_output>0
1
4
9
16
25
36<jupyter_text>Exercise 1 Do the following exercise in a notebook called Exercise_1-Final.ipynb.Recall the `Sentence` iterator class:```pythonclass SentenceIterator:    def __init__(self, words):         self.words = words         self.index = 0            def __next__(self):         try:            word = self.words[self.index]         except IndexError:            raise StopIteration()         self.index += 1        return word     def __iter__(self):        return selfclass Sentence:  An iterable    def __init__(self, text):         self.text = text        self.words = text.split()            def __iter__(self):        return SentenceIterator(self.words)        def __repr__(self):        return 'Sentence(%s)' % reprlib.repr(self.text)```  Exercise 1 ContinuedCreate a `Sentence` iterator class that uses a generator.  You will write the generator in the `__iter__` special method.  Note that the generator automatically gets `__next__` (so no need to implement it).  Now you only need to create a single class instead of the two that we had originally.  How Things WorkWe've introduced some data structures and discussed why they're important.Now we'll go over where things live in the computer and how `Python` actually does things.  Process address spaceWhat do we mean when we say a program is "in memory"?- compiled code must be loaded from disk into memory. - 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. The code, the reserved space, and the generated data all constitute a program's memory footprint. 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*.In Linux, the most common object format is called `ELF`, short for "Executable and Linkable Format".A simplified view of our example program looks like this in memory: the `stack` and the `heap`: [Stack and Heap](https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap).  The StackThe stack keeps track of function calls and their data. - 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. - 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.  - The most recognizable value in this latter category is the return address. When a function calls `return`, the computer starts executing instructions at the location that the function was originally called from.- 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.- Removing the function stack from from the stack becomes a problem if you want to create space for variables and then access them after the function returns.   The Heap- The heap is another memory location which is not reclaimed after a function returns. It is explicitly managed, which means that you need to ask to allocate a variable in it. What's more, when you're finished with that space, you need to say so.- This interface, explicitly requesting and releasing memory from the heap, is typically called *memory management*.- In `C` you do this directly using `malloc`/`free`. Python takes care of this for you using **garbage collection**.  How does Python manage memory?So far, when you create a list in `Python` (e.g. `a=[1,2,3,4,5]`), we have been thinking of it as an array of integers.But that is not actually the case.An array would be 5 contiguous integers with some book-keeping at the beginning either on the stack or the heap.You are all highly encouraged to read the eminently readable article [Why Python is Slow](https://jakevdp.github.io/blog/2014/05/09/why-python-is-slow/) from Jake Vanderplas's blog.  Most of the following points come from his discussion.  `Python` objects are allocated on the heap: an `int` is not an `int`An `int` is represented in `Python` as a `C` structure **allocated on the heap**.The picture of this C structure looks a little bit like this:![](http://jakevdp.github.io/images/cint_vs_pyint.png) On Jake's blog, he shows how this integer is represented:```Cstruct _longobject {    long ob_refcnt; // in PyObject_HEAD    PyTypeObject *ob_type; // in PyObject_HEAD    size_t ob_size; // in PyObject_HEAD    long ob_digit[1];};```It's not just a simple integer!  Boxing and unboxing (or why `Python` is slow)Because `int`s are stored in this scheme, a simple addition involves a lot of work!    So it's not a simple addition...there is all this machinery around it.And that example was just to add two `int`s where `binary_add` is optimized in C!If these were user defined classes, there would be additional overhead from `dunder` methods for addition!  What About Lists?A `Python` list is represented by this struct:```Ctypedef struct {    long ob_refcnt;    PyTypeObject *ob_type;    Py_ssize_t ob_size;    PyObject **ob_item;    long allocated;} PyListObject;```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 an `IntStruct`. The `ob_size` tells us the number of items on the list.Thus this is **an array of pointers to heap allocated `IntStruct`**s: [Simple Example](https://goo.gl/jjfpNV).  What do others do?`Julia`:>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.```juliaa = Real[]     typeof(a) = Array{Real,1}if (f = rand()) < .8    push!(a, f)  f will always be Float64end```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. We should instead use:```juliaa = Float64[]  typeof(a) = Array{Float64,1}```which will create a contiguous block of 64-bit floating-point values. `C`:You allocate explicitly either on the heap or stack. In `Python` you can append to lists. So what's an `ob_size` doing in our struct then?```Ctypedef struct {    long ob_refcnt;    PyTypeObject *ob_type;    Py_ssize_t ob_size;    PyObject **ob_item;    long allocated;} PyListObject;```Turns out Python lists are implemented in something called a dynamic array.  ArraysA static array is a contiguous slab of memory of known size, such that `n` items can fit in.  This is a great data structure. Why?- constant time index access: `a[i]` is $O(1)$ --- just seek `i * sizeof(int)`- linear time traversal or search: $1$ unit per loop iteration means $O(n)$ in loop.- locality in memory: it's one int after anotherTuples in `Python` are fixed size, static arrays.But the big problem is, what if we want to add something more beyond the end of the array? Then we must use dynamic arrays.  Dynamic ArraysWhat `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.[`listobject.c`](https://svn.python.org/projects/python/trunk/Objects/listobject.c )```C/* This over-allocates proportional to the list size, making room     * for additional growth.  The over-allocation is mild, but is     * enough to give linear-time amortized behavior over a long     * sequence of appends() in the presence of a poorly-performing     * system realloc().     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...     */new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);```  Performance of Dynamic ArraysLets assume we start with an array of size of $1$ (one slot) and then double the size each time. After $n$ doublings, we have an array with $2^n$ slots.  So, it then takes $lg(n)$ doublings for the array to have $n$ slots (note, $\lg(n)$ means $\log_{2}(n)$). Notice that we might not get the continuously allocated memory we want. So we'll have to recopy to a larger array.The last $n/2$ numbers in the array don't move at all (they're the new ones). The previous $n/4$ numbers in the array would have moved once, the previous $n/8$ twice, and so on.Thus the total number of movements is $$\sum_{i=1}^{lg(n)} i\frac{n}{2^{i+1}} \leq \frac{n}{2} \sum_{i=1}^{\infty} \frac{i}{2^i} = 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! Here's the calculation.\begin{align*}  \sum_{i=0}^{\infty}{\left(i+1\right)x^{i+1}} &= x\sum_{i=0}^{\infty}{\left(i+1\right)x^{i}} \\      &= x\frac{\mathrm{d}}{\mathrm{d}x}\sum_{i=0}^{\infty}{x^{i+1}} \\      &= x\frac{\mathrm{d}}{\mathrm{d}x}\left[x\sum_{i=0}^{\infty}{x^{i}}\right] \\      &= x\frac{\mathrm{d}}{\mathrm{d}x}\left[\frac{x}{1-x}\right] \\      &= \frac{x}{\left(1-x\right)^{2}}.\end{align*}When $x = 1/2$ we have$$\sum_{i=0}^{\infty}{\left(i+1\right)x^{i+1}} = 2.$$From here we can easily get the result from the previous slide.  Containers  vs FlatsEarlier we saw how `Python` lists contained references to integer ("digit")+metdata based structs on the heap. We call sequences that hold such "references" to objects on the heap **Container Sequences**. Examples of such container sequences are `list`, `tuple`, `collections.deque`.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: `str`, `bytes`, `bytearray`, `memoryview`, `array.array`. You have probably extensively used a type of flat sequence not mentioned yet. This is `NumPy`'s ndarray: `np.array`.All of these are faster as they work with **contiguous blocks of uniformly formatted memory**.From Fluent Python:> 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. This is also a more general way of thinking about data structures. >**Contiguously-allocated** structures are composed of single slabs of memory, and include arrays, matrices, heaps, and hash tables.>**Linked** data structures are composed of distinct chunks of memory bound together by pointers, and include lists, trees, and graph adjacency lists.(<NAME>. The Algorithm Design Manual) - A critical advantage 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. - Other benefits include a tighter size and a locality of memory which benefits cache and general memory transport.  Mutable vs ImmutableThe mutability of objects has recurred often in this course.One can also study containers based on their mutability. **Mutable sequences** in `Python 3` are: `list, bytearray, array.array, collections.deque, memoryview`.**Immutable sequences** in `Python 3` are `tuple, str, bytes`.Lets learn about some of these collections in `Python`.  array.arrayThe `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.`array.array` 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. `array.array` *is* mutable, and you dont need to allocate ahead of time (reallocation will be done).<jupyter_code>from array import array
from random import random
#generator expression instead of list comprehension
floats_aa = array('d', (random() for i in range(10**8)))
print(floats_aa.itemsize, "   ", type(floats_aa), "   ", floats_aa[5])<jupyter_output>8     <class 'array.array'>     0.3176736026304541<jupyter_text>Now let's do the same thing with a list comprehension:<jupyter_code>floats_list = [random() for i in range(10**8)]
%%time
for f in floats_aa:
    pass
%%time
for f in floats_list:
    pass<jupyter_output>CPU times: user 2.15 s, sys: 179 ms, total: 2.33 s
Wall time: 2.33 s
{'fraction_non_alphanumeric': 0.08974453360818671, 'fraction_numerical': 0.011705808731502614, 'mean_word_length': 4.295906432748538, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 18, 'https://': 5, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '21792', 'license': 'MIT', 'n_tokens_mistral': 3801, 'n_tokens_neox': 3591, 'n_words': 1899, 'path': 'lectures/L15/L15.ipynb', 'repo_name': 'syj19950301/cs207_yijun_shen', 'size': '13592'}