comprehensions-and-generators.jupyter

nbformat 4
nbformat_minor 1
markdown
    # List Comprehensions, Generators, Generator Expressions
    
    [back to main page](../index.ipynb)
    
    These are some of the greatest features of Python, you should definitely know how to use them!
markdown
    ## List Comprehensions
    
    Python's [list comprehesion](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions) feature allows us to concisely create new lists from existing sequences.
    
    This doesn't sound too spectacular, but wait until you see what you can do with them ...
    
    First of all, we need a sequence of example data that we will use as basis for the following list comprehension examples:
code 1
    numbers = 4, 9, 7, 20, 6, 33, 13, 23, 16, 62, 8
  metadata
    {
     "collapsed": true
    }
markdown
    ### Shallow Copy
    
    The simplest (and mostly useless) form of a list comprehension is just a dull repetition of all sequence elements into a new list:
code 2
    [x for x in numbers]
  execute_result
  - text/plain
    [4, 9, 7, 20, 6, 33, 13, 23, 16, 62, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    I'm showing this just for didactical purposes, in practice there is a simpler and less confusing way to get the exact same thing:
code 3
    list(numbers)
  execute_result
  - text/plain
    [4, 9, 7, 20, 6, 33, 13, 23, 16, 62, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    The [list()](https://docs.python.org/3/library/stdtypes.html#list) constructor takes any *iterable* and turns it into a list, so there is no need for a list comprehension here.
markdown
    ### Map
    
    Imagine you want to evaluate an expression (e.g. `2 * x`) for every item in a sequence and store all the results in a new list.
    
    It's as easy as that:
code 4
    [2 * x for x in numbers]
  execute_result
  - text/plain
    [8, 18, 14, 40, 12, 66, 26, 46, 32, 124, 16]
  metadata
    {
     "collapsed": false
    }
markdown
    Alternatively, we could also use the built-in function [map()](https://docs.python.org/3/library/functions.html#map) to map a given function to each of the items in a sequence.
    
    But to be able to do that, we have to turn our expression into a proper function:
code 5
    def two_times(x):
        return 2 * x
  metadata
    {
     "collapsed": true
    }
markdown
    Now we can pass this function, together with the initial sequence, to `map()`:
code 6
    map(two_times, numbers)
  execute_result
  - text/plain
    <map at 0x7fdc845fb358>
  metadata
    {
     "collapsed": false
    }
markdown
    What comes out of this is not a list, but a `map` object.
    This is a *lazy sequence*, i.e. an iterator (see [below](#Iterators) for an explanation) that yields its items *on demand*, not all at once.
    
    If you want to see them at once anyway, you can use the `list()` constructor again, which iterates over all results and puts them into a new list:
code 7
    list(map(two_times, numbers))
  execute_result
  - text/plain
    [8, 18, 14, 40, 12, 66, 26, 46, 32, 124, 16]
  metadata
    {
     "collapsed": false
    }
markdown
    Defining a named function (and especially coming up with a meaningful name) can be cumbersome, especially if the function only returns a single expression.
    
    In this case you can use Python's [lambda](https://docs.python.org/3/reference/expressions.html#lambda) keyword to define an in-line anonymous function directly within the call to `map()`:
code 8
    list(map(lambda x: 2 * x, numbers))
  execute_result
  - text/plain
    [8, 18, 14, 40, 12, 66, 26, 46, 32, 124, 16]
  metadata
    {
     "collapsed": false
    }
markdown
    This is nearly as concise, but the list comprehension above is easier to grasp, isn't it?
markdown
    ### Filter
    
    Imagine you want to create a list with items from another sequence, but only those which satisfy a given condition.
    
    This can be done by throwing an `if` into the list comprehension:
code 9
    [x for x in numbers if x > 10]
  execute_result
  - text/plain
    [20, 33, 13, 23, 16, 62]
  metadata
    {
     "collapsed": false
    }
markdown
    It should be quite clear what the above line does.
    
    But as before, there is also an alternative way to get the same result, namely using the built-in [filter()](https://docs.python.org/3/library/functions.html#filter) function:
code 10
    list(filter(lambda x: x > 10, numbers))
  execute_result
  - text/plain
    [20, 33, 13, 23, 16, 62]
  metadata
    {
     "collapsed": false
    }
markdown
    Here we directly used a lambda function to express our condition.
    
    If the condition is more complicated, it can of course be encapsulated in a function, e.g.:
code 11
    def my_condition(x):
        """A very strange condition."""
        if x % 2 == 0:
            x //= 2
        elif x % 3 == 0:
            x += 4
        return 3 < x < 10
  metadata
    {
     "collapsed": true
    }
markdown
    Such a conditional function (sometimes called *predicate*) can be used in a list comprehension ...
code 12
    [x for x in numbers if my_condition(x)]
  execute_result
  - text/plain
    [7, 16, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    ... and with `filter()`:
code 13
    list(filter(my_condition, numbers))
  execute_result
  - text/plain
    [7, 16, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    In this case it is largely a matter of taste which of the two alternatives you should use.
markdown
    ### Map + Filter
    
    As you can imagine, it's possible to combine the mapping of an expression to a list and the filtering of this list:
code 14
    [2 * x for x in numbers if x > 10]
  execute_result
  - text/plain
    [40, 66, 26, 46, 32, 124]
  metadata
    {
     "collapsed": false
    }
markdown
    This can of course also be done with a combination of `map()` and `filter()`, but list comprehensions are often easier to read.
code 15
    list(map(lambda x: 2 * x, filter(lambda x: x > 10, numbers)))
  execute_result
  - text/plain
    [40, 66, 26, 46, 32, 124]
  metadata
    {
     "collapsed": false
    }
markdown
    ### Map With `if`/`else`-Expression
    
    The first part of a list comprehension can be an arbitrary *expression*, but *statements* are not allowed.
    That's one of the situations where an `if`/`else`-expression (a.k.a. [conditional expression](https://docs.python.org/3/reference/expressions.html#conditional-expressions)) can come in handy:
code 16
    [x * 100 if x < 5 else x * 10 for x in numbers]
  execute_result
  - text/plain
    [400, 90, 70, 200, 60, 330, 130, 230, 160, 620, 80]
  metadata
    {
     "collapsed": false
    }
markdown
    ### Nested Sequences
    
    A sequence can itself contain sequences, e.g. a sequence of numbers consists of sequences of digits:
code 17
    [str(x) for x in numbers]
  execute_result
  - text/plain
    ['4', '9', '7', '20', '6', '33', '13', '23', '16', '62', '8']
  metadata
    {
     "collapsed": false
    }
markdown
    If the initial sequence is such a nested sequence, the list comprehension can operate on the flattened sequence by using multiple `for`-parts:
code 18
    [int(c) for x in numbers for c in str(x)]
  execute_result
  - text/plain
    [4, 9, 7, 2, 0, 6, 3, 3, 1, 3, 2, 3, 1, 6, 6, 2, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    Note that the first `for`-part concerns the outer list and the second one the inner lists, just as in two nested `for` loops:
code 19
    mylist = []
    for x in numbers:
        for c in str(x):
            mylist.append(int(c))
    
    mylist
  execute_result
  - text/plain
    [4, 9, 7, 2, 0, 6, 3, 3, 1, 3, 2, 3, 1, 6, 6, 2, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    However, if you want the output list also to be nested, you can use a separate (inner) list comprehension as the first part of another (outer) list comprehension:
code 20
    [[int(c) for c in str(x)] for x in numbers]
  execute_result
  - text/plain
    [[4], [9], [7], [2, 0], [6], [3, 3], [1, 3], [2, 3], [1, 6], [6, 2], [8]]
  metadata
    {
     "collapsed": false
    }
markdown
    ### Filtering Nested Sequences
    
    Of course, you can also add an `if`-part to a nested list comprehension:
code 21
    [int(c) for x in numbers if x > 10 for c in str(x)]
  execute_result
  - text/plain
    [2, 0, 3, 3, 1, 3, 2, 3, 1, 6, 6, 2]
  metadata
    {
     "collapsed": false
    }
markdown
    Apparently, the position of the `if`-part doesn't matter, it can be either between the `for`-parts or after them.
code 22
    [int(c) for x in numbers for c in str(x) if x > 10]
  execute_result
  - text/plain
    [2, 0, 3, 3, 1, 3, 2, 3, 1, 6, 6, 2]
  metadata
    {
     "collapsed": false
    }
markdown
    And you can have more than one `if`-parts. You can have one for each `for`-part.
code 23
    [int(c) for x in numbers if x > 10 for c in str(x) if c not in ('3', '6')]
  execute_result
  - text/plain
    [2, 0, 1, 2, 1, 2]
  metadata
    {
     "collapsed": false
    }
markdown
    ### Replacing `for`-Loops With List Comprehensions
    
    People who come to Python from other languages tend to create empty lists and then `append()` to them within a `for`-loop like this:
code 24
    newlist = []
    for n in numbers:
        if n % 2 != 0:
            newlist.append(n**2)
  metadata
    {
     "collapsed": false
    }
markdown
    It's of course *possible* to do this, but for reasonably short expressions it is much *nicer* to replace this with a list comprehension:
code 25
    newlist = [n**2 for n in numbers if n % 2 != 0]
  metadata
    {
     "collapsed": false
    }
markdown
    This is the way how it's done in Python!
markdown
    ## Set Comprehensions, Dictionary Comprehensions
    
    For completeness' sake, let me mention `set` and `dict` comprehensions here.
    
    Set comprehensions look very much like `list` comprehensions, except that they are enclosed in a pair of braces instead of brackets.
    
    And of course they create a `set`, i.e. there are no duplicates and you shouldn't rely on the order of items.
code 26
    {int(c) for x in numbers for c in str(x)}
  execute_result
  - text/plain
    {0, 1, 2, 3, 4, 6, 7, 8, 9}
  metadata
    {
     "collapsed": false
    }
markdown
    All the rest works the same as in list comprehensions.
    
    There is another type of comprehensions that is enclosed in braces: dictionary comprehensions.
    The difference is that `dict` comprehensions use a pair of values with a colon inbetween.
    The expression in front of the colon is evaluated and specifies a *key*, while the expression after the colon provides the corresponding *value*.
    
    Let's look at this very silly example for a dict comprehension (which also includes a list comprehension just for the sake of it):
code 27
    {str(x): [int(c) for c in str(x)] for x in numbers}
  execute_result
  - text/plain
    {'13': [1, 3],
     '16': [1, 6],
     '20': [2, 0],
     '23': [2, 3],
     '33': [3, 3],
     '4': [4],
     '6': [6],
     '62': [6, 2],
     '7': [7],
     '8': [8],
     '9': [9]}
  metadata
    {
     "collapsed": false
    }
markdown
    Set comprehensions and dictionary comprehensions are by far not as common as list comprehensions, but it's still good to know them.
    
    But now for something completely different ...
markdown
    ## Iterators
    
    *Iterators* are a completely different topic, but they are necessary to understand [generators](#Generators) which, combined with features from list comprehensions will finally lead us to [generator expressions](#Generator-Expressions) (which are awesome).
    
    There are many *iterable* built-in objects in Python, e.g. lists, tuples, strings, files. There are many more *iterable* objects in the standard library and in third-party libraries.
    The concept of iterable objects (often just called *iterables*) is very important in Python.
    
    If you want to *iterate* over an *iterable* you can get an *iterator* by calling the built-in [iter()](https://docs.python.org/3/library/functions.html#iter) function.
code 28
    it = iter(numbers)
  metadata
    {
     "collapsed": false
    }
markdown
    Iterators are very simple (but powerful!). The only thing you can do to them, is call the built-in function [next()](https://docs.python.org/3/library/functions.html#next) on them:
code 29
    next(it)
  execute_result
  - text/plain
    4
  metadata
    {
     "collapsed": false
    }
markdown
    ... and again ...
code 30
    next(it)
  execute_result
  - text/plain
    9
  metadata
    {
     "collapsed": false
    }
markdown
    ... and again ...
code 31
    next(it)
  execute_result
  - text/plain
    7
  metadata
    {
     "collapsed": false
    }
markdown
    ... and again ...
code 32
    next(it)
  execute_result
  - text/plain
    20
  metadata
    {
     "collapsed": false
    }
markdown
    An iterator object is itself iterable, therefore we can use the `list()` constructor to turn the remaining elements into a list:
  metadata
    {
     "collapsed": true
    }
code 33
    list(it)
  execute_result
  - text/plain
    [6, 33, 13, 23, 16, 62, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    This basically calls `next(it)` repeatedly and collects the results into a list.
    
    But what happens if the iterator is exhausted?
    How does the list constructor know that there are no more items left to iterate over?
    
    That's easy: if `next()` is called on an exhausted iterator, an exception of the type [StopIteration](https://docs.python.org/3/library/exceptions.html#StopIteration) is raised.
    
    A very common use of an iterator is in a `for` loop.
    In this case the interpreter internally calls `iter()` and then calls `next()` on the resulting iterator assigning the result to the loop variable.
    After the loop body, `next()` is called again and the process is repeated until a `StopIteration` is raised.
    
    When we just use a `for`-loop, we don't have to worry about `iter()` and `next()`, but that's what's going on under the hood.
  metadata
    {
     "collapsed": true
    }
code 34
    for n in numbers:
        print(n * '.')
  stream stdout
    ....
    .........
    .......
    ....................
    ......
    .................................
    .............
    .......................
    ................
    ..............................................................
    ........
  metadata
    {
     "collapsed": false
    }
markdown
    As I mentioned above, an *iterator* is itself *iterable*, i.e. we can again call `iter()` on it.
    But don't worry about calling `iter()` too often.
    If it is called on something that's already and iterator, it will just return the thing unchanged:
code 35
    it = iter(numbers)
    it is iter(it) is iter(iter(it)) is iter(iter(iter(it)))
  execute_result
  - text/plain
    True
  metadata
    {
     "collapsed": false
    }
markdown
    ## Generators
    
    Iterating over an existing sequence is very simple and useful, but there are two cases where this may not be feasible anymore:
    
    * If creating a single list element takes a non-negligible amount of time you might not want to create a whole list of them before you start working with the list elements.
    Wouldn't it be nice to create a sequence one item at a time? Then we could start processing the first element immediately and don't have to wait for the whole list to be created.
    
    * If we are dealing with a very long sequence, building a list of it will need a lot of memory at once.
    If we only need to process one item element at a time, wouldn't it be nice to avoid wasting all that memory and just process the sequence elements one by one?
    
    That's where *generators* come in.
    *Generator objects* are *iterable*, but they don't necessarily store all items.
    They only produce one item at a time.
    
    *Generator objects* are created by calling *generator functions*.
    A *generator function* looks very much like a normal function, but instead of a `return` statement (or several) it has one or more `yield` statements.
    
    This is a really silly example of a *generator function* which yields our numbers from above one by one:
code 36
    def my_generator():
        yield 4
        yield 9
        yield 7
        yield 20
        yield 6
        yield 33
        yield 13
        yield 23
        yield 16
        yield 62
        yield 8
  metadata
    {
     "collapsed": true
    }
markdown
    When we call this *generator function* we get a *generator object*:
code 37
    my_generator()
  execute_result
  - text/plain
    <generator object my_generator at 0x7fdc846157d8>
  metadata
    {
     "collapsed": false
    }
markdown
    Let's assign it to a variable:
code 38
    g = my_generator()
  metadata
    {
     "collapsed": true
    }
markdown
    Note that when running a *generator function*, the code *inside* is not (yet) executed.
    
    Every *generator object* is an *iterator*, so we can call `next()` on it:
code 39
    next(g)
  execute_result
  - text/plain
    4
  metadata
    {
     "collapsed": false
    }
markdown
    When we call `next()`, the body of the *generator function* is executed until the first `yield` expression is encountered.
    The value on the right side of the `yield` keyword is produced and the execution is stopped.
    
    When we call `next()` again, the execution of the function continues at the statement where it was stopped before and the following statements are executed until the next `yield` expression is encountered.
    At this point the corresponding value is produced and the execution is "frozen" again.
code 40
    next(g)
  execute_result
  - text/plain
    9
  metadata
    {
     "collapsed": false
    }
markdown
    Viewed from the outside, this just looks like any old iterable.
    Let's turn whatever is left in the *generator object* into a list:
code 41
    list(g)
  execute_result
  - text/plain
    [7, 20, 6, 33, 13, 23, 16, 62, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    After that the generator is exhausted (a `StopIteration` exception was raised within the `list()` constructor), we cannot really do anything else with it.
    
    Calling `next()` again would just raise another `StopIteration` exception.
    
    But of course we can call the *generator function* again to get a completely new *generator object* which can again be iterated over exactly once:
code 42
    list(my_generator())
  execute_result
  - text/plain
    [4, 9, 7, 20, 6, 33, 13, 23, 16, 62, 8]
  metadata
    {
     "collapsed": false
    }
markdown
    This example is really silly, the same thing could also be done with just a `list` of numbers.
    But imagine producing one of these number would take a long time.
    Then it would be perfectly reasonable to compute and yield them one by one in a generator function.
    
    And there is another use case where a `list` just wouldn't work: generators can be infinite!
    
    To show this, we can create a generator function with an infinite loop that yields a value at each iteration:
code 43
    def integers_starting_from(n):
        while True:
            yield n
            n += 1
  metadata
    {
     "collapsed": true
    }
markdown
    When we call this function we get a generator ...
code 44
    i = integers_starting_from(42)
  metadata
    {
     "collapsed": true
    }
markdown
    ... on which we can call `next()` ...
code 45
    next(i)
  execute_result
  - text/plain
    42
  metadata
    {
     "collapsed": false
    }
markdown
    ... and again ...
code 46
    next(i)
  execute_result
  - text/plain
    43
  metadata
    {
     "collapsed": false
    }
markdown
    ... and again ...
code 47
    next(i)
  execute_result
  - text/plain
    44
  metadata
    {
     "collapsed": false
    }
markdown
    ... and we can do this arbitrarily often, until we get bored.
    
    > Side note: Since Python can handle arbitrarily large integers, we can *really* do this arbitrarily often and we will each time get an even larger number, the numbers will never overflow (unless there is a bug in the Python interpreter).
    
    This time we cannot create a `list` of the remaining items, because this list would grow infinitely large!
    
    To avoid an infinitely large list, we can create another generator function that takes a generator, yields a finite number of items and then stops:
  metadata
    {
     "collapsed": true
    }
code 48
    def take15(it):
        for _ in range(15):
            yield next(it)
  metadata
    {
     "collapsed": true
    }
code 49
    many_integers = integers_starting_from(42)
  metadata
    {
     "collapsed": false
    }
code 50
    list(take15(many_integers))
  execute_result
  - text/plain
    [42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56]
  metadata
    {
     "collapsed": false
    }
code 51
    list(take15(many_integers))
  execute_result
  - text/plain
    [57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71]
  metadata
    {
     "collapsed": false
    }
markdown
    But is wasn't even necessary to write our own generator function for this, the Python standard library already has such a thing: [itertools.islice()](https://docs.python.org/3/library/itertools.html#itertools.islice).
    It's only an import away ...
code 52
    import itertools
  metadata
    {
     "collapsed": true
    }
markdown
    With the help of this, let's create a helper function that returns a list with the first 15 elements of a (possibly infinite) generator.
code 53
    def list15(it):
        return list(itertools.islice(it, 15))
  metadata
    {
     "collapsed": true
    }
code 54
    list15(integers_starting_from(42))
  execute_result
  - text/plain
    [42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56]
  metadata
    {
     "collapsed": false
    }
markdown
    We will use this below to quickly check the first few values of an infinite generator.
    
    By the way, our `integers_starting_from()` generator function is also already available in the `itertools` library under the name [itertools.count()](https://docs.python.org/3/library/itertools.html#itertools.count).
code 55
    itertools.count(42)
  execute_result
  - text/plain
    count(42)
  metadata
    {
     "collapsed": false
    }
markdown
    This returns a special `count` object, which is iterable and yields increasing values forever, just like the generator returned by `integers_starting_from()`.
code 56
    list15(itertools.count(42))
  execute_result
  - text/plain
    [42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56]
  metadata
    {
     "collapsed": false
    }
markdown
    ### Map and Filter for Generators
    
    Similar to what we saw above, we can also *filter* elements from a generator and we can also *map* a function/expression on the sequence yielded by a generator.
    
    One way to do this, is to create a new generator function:
  metadata
    {
     "collapsed": true
    }
code 57
    def square_evens(it):
        for x in it:
            if x % 2 == 0:
                yield x**2
  metadata
    {
     "collapsed": true
    }
code 58
    list15(square_evens(itertools.count(1)))
  execute_result
  - text/plain
    [4, 16, 36, 64, 100, 144, 196, 256, 324, 400, 484, 576, 676, 784, 900]
  metadata
    {
     "collapsed": false
    }
markdown
    It is of course also possible to do this with the functions `map()` and `filter()`:
code 59
    list15(map(lambda x: x**2, filter(lambda x: x % 2 == 0, itertools.count(1))))
  execute_result
  - text/plain
    [4, 16, 36, 64, 100, 144, 196, 256, 324, 400, 484, 576, 676, 784, 900]
  metadata
    {
     "collapsed": false
    }
markdown
    This doesn't really look nice, wouldn't it be great if we could use a similar syntax as with list comprehensions?
    
    Which leads us to the climax of this page ...
markdown
    ## Generator Expressions
    
    Generator expressions look very similar to list comprehensions, but instead of a finite-size `list`, they return a generator object.
    
    In fact, they look exactly like list comprehensions, just without the brackets surrounding the expression.
    In some cases, we have to surround generator expressions with parentheses, because otherwise the code would be ambiguous:
code 60
    squares_of_evens = (x**2 for x in itertools.count(1) if x % 2 == 0)
  metadata
    {
     "collapsed": false
    }
markdown
    The whole generator expression evalutes to a *generator object*:
code 61
    squares_of_evens
  execute_result
  - text/plain
    <generator object <genexpr> at 0x7fdc84615258>
  metadata
    {
     "collapsed": false
    }
markdown
    In this case the generator object is infinite, so let's only look at the first few items:
code 62
    list15(squares_of_evens)
  execute_result
  - text/plain
    [4, 16, 36, 64, 100, 144, 196, 256, 324, 400, 484, 576, 676, 784, 900]
  metadata
    {
     "collapsed": false
    }
markdown
    If we only need the generator expression once, we can drop the assignment and use it directly (in any place where an *iterator* is expected).
code 63
    list15(x**2 for x in itertools.count(1) if x % 2 == 0)
  execute_result
  - text/plain
    [4, 16, 36, 64, 100, 144, 196, 256, 324, 400, 484, 576, 676, 784, 900]
  metadata
    {
     "collapsed": false
    }
markdown
    Note: Here we didn't need an additional pair of parentheses!
    
    Conceptually, a list comprehension is just a generator expression that's immediately turned into a `list`:
code 64
    list(x for x in numbers if x > 10)  # a generator expression as argument to list()
  execute_result
  - text/plain
    [20, 33, 13, 23, 16, 62]
  metadata
    {
     "collapsed": false
    }
code 65
    [x for x in numbers if x > 10]  # a list comprehension
  execute_result
  - text/plain
    [20, 33, 13, 23, 16, 62]
  metadata
    {
     "collapsed": false
    }
markdown
    ## Reduce
    
    TODO: sum, any, all, min, max
    
    TODO: mention [functools.reduce()](https://docs.python.org/3/library/functools.html#functools.reduce)?
markdown
    ## Example: The Sieve Of Eratosthenes
    
    This example is taken from the very famous book "Structure and Interpretation of Computer Programs" (SICP).
    The example can be found in [chapter 3.5](https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html) and in the [Video Lecture 6B on YouTube](https://youtu.be/DCub3iqteuI).
    
    Let's look at this video where Hal Abelson explains the [Sieve Of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes):
code 66
    from IPython.display import YouTubeVideo
    YouTubeVideo("DCub3iqteuI", start=495)
  execute_result
  - image/jpeg
    /9j/4AAQSkZJRgABAQAAAQABAAD/2wCEABALDA4MChAODQ4SERATGCgaGBYWGDEjJR0oOjM9PDkz
    ODdASFxOQERXRTc4UG1RV19iZ2hnPk1xeXBkeFxlZ2MBERISGBUYLxoaL2NCOEJjY2NjY2NjY2Nj
    Y2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY//AABEIAWgB4AMBIgACEQED
    EQH/xAAbAAEAAgMBAQAAAAAAAAAAAAAAAQIDBAUGB//EAEYQAAIBAgMDCAcGBAQFBQEAAAABAgMR
    BBIhBTFRExQWQVORktEGFSIyUmGBIzNCcaHSJEPh8DRigqJEY2RysRdUssHxB//EABkBAQEBAQEB
    AAAAAAAAAAAAAAABAgMEBf/EACQRAQADAAICAwEBAQADAAAAAAABAhESEwMhFDFRQWEEIjJC/9oA
    DAMBAAIRAxEAPwD5+AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAD1HRvB9pX8S8iejWDv97X8S8jj30a4y8sD1fRjBdriPEvId
    GMF2uI8UfId1DjLygPV9GMF2uI8UfIdGcF2uI8S8h3UOMvKA9X0ZwXa4jxLyHRnBdrX8S8i91ThL
    ygPVdGcF2tfxLyHRnBdrX8UfId1DjLyoPVdGcH2tfxR8h0awfaV/FHyHdQ4y8qD1XRrB9rX8S8h0
    awfa1/EvId1DhLyoPVdGsH2tfxLyHRrB9rX8S8h3UOMvKg9V0awfa1/EvIdGsH2tfxLyHdQ4y8qD
    1PRrB9rX8S8h0bwfa1/EvId1TjLywPUdG8H2lfxLyC9G8G/5lfxLyHdQ4y8uD1PRrB9rX8S8h0aw
    fa1/EvId1DhLywPU9GsH2lfxLyHRrB9rX8S8id1DhLywPU9GsH2tfxLyHRvB9rX8S8h3UOEvLA9T
    0bwfaV/EvIdGsH2lfxLyL3UOMvLA9T0awfaV/EvIdGsH2lfxLyHdQ4y8sD1PRrB9rX8S8h0awfa1
    /EvId1DjLywPVdGsH2tfxLyI6NYPtK/ij5DuocJeWB6ro1gu1r+JeQ6NYPta/iXkO6icZeVB6ro1
    gu1r+JeQ6NYLta/iXkO6i8ZeVB6rozgu1r+JeRC9GsHf72v4l5DuocZeWB6ro1gu1r+JeQ6M4Lta
    /iXkO6hwl5UHqujOC7XEeJeRPRnBdpiPEvId1DhLygPV9GcF2mI8S8h0YwXaYjxLyHdQ4S8oD1fR
    jB9piPEvIdGMH2mI8UfId1DhLygPWdGMH2mI8S8h0XwnaYjxLyHdQ4S8mD1vRbCdpiPEvIleiuE+
    PE+KPkO6hwl5EHruiuE+PEeJeQ6KYT48T4o+Q7qHGXkQev6J4T48T4o+RPRLC/HifFHyJ3UOMvHg
    9j0Rwvx4jxR8jHX9FcNToymp4i6/zR8jUeWspxl2Vhqvwlua1b+6zkxxmI7RmRY3Edqzj8f/AFz+
    ZR1Xhqnwsjm1X4WcznuI7Rk89xHaMvx/9Pl0dLm9T4WRzep8LOa8biO1Y57iO0Y+OfKo6XN6nwsc
    hU+E5nPMR2jHPMR2jHR/p8ujp8hU+Ec3qcDl88xHaMc6r9ox0f6fLo6nN6nAjm9Tgct4qv2jI5zW
    7Rk6P9X5dHV5vMchP5HJ5xW7Rh16r/mMvRH6nzK/jrchP5EchLiu85PL1e0kRy1T42OiP0+XX8df
    kHxXeORfxR7zkOrU+NkcrP433joj9Pl1/HX5H/NHvHJf5495xuUn8b7wpz+N946Y/T5dfx2eR19+
    PeSsNK12zl4WcnXSu+87VZ/ZyHRDUf8ARE/xhdGK/mR7xyUe1j3nKnOWd6veVzy4sdEMT/1RDrcn
    DtY95GSn2se85OaXFkZnxL0Qny/8dfLS7aPeRal20e85GZi7HRB8v/HXtS7aPePse2j3nITfEm7H
    TCfLda9HtY94vQ7WPecm7CbJ01Pluteh2se8KWH66qOVchsvTU+W6+fDdqu8cphe1ORcDpqny5dj
    lcJ2g5bBr+YcdkDpqfKn8drl8F8Y5fBfEcW5JemifLl2uc4JddwsVgUzigvVQ+XZ2ue4H4Qsdgl+
    A4pKHVRPlWdnn+D7MescJ2X6HGFx1UPlWdj1lhVupD1nh+xRxwOqifKs7D2nR6qC/v6FXtWmt1Bd
    /wDQ5WbQMvVT8T5V3U9bQ7Bd/wDQj1wv/brv/ocsDrp+JP8A03dT1xwoLv8A6G1gcY8VJ3gkjgo6
    2xVpJkmtfxa/9F5dLETVOm5JLQ5M9q1U7KETo4x/w8jz8tZM6U8dJj6dbeW0Q3fW1f4UV9a4j5Gk
    LDjT8ef5F249p4jiYMRtHESw8k5GFlK6+wkMrH8WPPeUxRdIqkXSM68+e0WFiwsXVxVogsyLDTEA
    mwaIYgCwsUxBBNiAAYIYAABRkEgaIFgCKzYT/ERO1Wf2cji4V/xMTsVXeEiRLvRx8rlOT4EKLb0R
    OfLOS4llVknohaZYtEaxOLTtYZXwMnK2nmylXUbne2hOTHFSwtbejLykV+HUiclLcXTiog1YmLs7
    l5TTktBpxYrPqJRmU6bW6zK1MujViacWMgnqBUlBKIZKLqDBNiGNEFipIEgACCQAgACgBYETAEEg
    CLghlE3OvsZ+wzj9R19kfdMxLdPtuYx/w8jgS3s7eLf8PI4berO9Pp38n0GWEYy3P6GG5kpTjB6q
    5yn7eWCSi5W3IxYpKNGVmXnLNK9jFidaEg3CyLl1Qa6y3Iu28ejPbFcm5kdFrrQ5CYaxiBk5KVyH
    Ta32BihBkyP5DI/kDGMuoprQZHwEcy3AVt8irRklKT0ZW3yB6Y7EGRxIylTFAXy6kWBioLxhmZVp
    XsgmKgvk0Iy2CxC+Gf8AEROvU9yRyMOvt4nVqP2JEd6OTP32ZKdnHR2Zin77HUSYc7z7ZGo3s39S
    Y04Nv29DFFXdizp8CZKatOCXXoW5GOW+azMfJyfVcZGuoez0zOjFRWurIdJJq7MeVtkunPLfqJ7X
    0ySoU4vWZiqQyNa6dRV0572S4SdroqbC0Iqe9lJLK9S0YTjuTRE4yWskVFSUTGDkm+pEFQIZLIGC
    GSR1koIkAAQALASAADK3LFba7yokkizZa24Igqy+R3sQ4aAxR7jrbJ+6ZyWdXZmlF2JMN0+2fFP+
    HkcZ72dfEv8Ah2cd72dY+nbyfSbkAGHlhJjxH+HkXKV/uJEbq2HOcdL6BVZ7iuaUmrIuozZj0vtO
    eb3kurNvRllCS32KR03oemo1ZVpResSKk1NXtZlbshtdaJhsouLviSsvzHscWb09ou+IUpE2j8QS
    je7ZPQiUpEZ3xLTUW9GVyfND0IcmISeZEum1vkiIQedaoehNR2mUuXqU25vVEKm72CIjPKzI4Ju6
    6yrpyhrZNEObbuTVhkhG7s9CakEkYsz37jHOvGOlya1Eay0dKyOnP3ZHEWIyzUlFs2I7TUrqpGxq
    JdYrMQpL32CudTba3EmpcL/aU3F3RLqybvoVIM4msqqze4Ko7a6siOqtexd1IW0RnVidVU2ncOpJ
    /kSpx4FXLXQAqk7ZS2eppcrn0138SY1WnuuBbPUfEh8pJWabDqvgiHUk1vAmOaF1/wCSkpNvckFN
    3I3sqMsad6eZshUm/wAiuZ5cvUIycdzHtEulq9StrOwzyTvci7buX2el4JORZNZrSiYlxLNtrUC6
    SctySElG+jRiuEPZsMjhfcTBRd2zHdkD2mwyWi3wLyhBRTVjALshsMtrO+lmWS1s9z3GBNls7vce
    19MrjlhfruQ7cpZdZiu+IjLK7osanoqRtJnR2c7UWcyTvdvedHZ7+yYap9suJd6DOU95067/AIdn
    Lb1OsT6dfJ9JBW4Rh5GSFk9VcripWoSWVEXsTidcM2R0p9ppuzLPRlI70ZJ9RnGkZnfeWcm97KE7
    y4qyIIGowxJDJ14ENPgAFyLPgLPgAbIJyvgSoPgMgRNaImkvaE1oTB2ZFUmrzZCunuJk/aZFyiW2
    yr3EuRFzNpxukbKrp1KkbmDIov22tDcdaEVZysYZYeNSLnFvU56+l4/HER6YZyll9hmKq3KG6zNz
    D4SKg5Xd+BeWH5SD9nUsTDpamw0MLVkp5Xqmbxqww1SNe7WhtNNb0dXy/NXJCCdC2TQY4KhF+Sb6
    yu52IYIkgkqqveSQyVv1IgC8kluKMsCCQ92guUGShJ3IRDFnB2uVRflGo2tcpmJ7MSlrZl5xypGO
    5ZvMUVAuStSoAE2IYixFi4BiiRNiwKYqVLsqwmIe46GBdqLOe9xvYPSiSW6fa9d/YM5zOhXf2Jzz
    pH06eX6AgEZeVPURV1ws0TcrVf2EjMt0I3vuMuaVtxhjOXFl1OS62F1e8uA9vgVzvi+8jPL4n3lX
    Vnn4Ee3wIc5PrZGZ8WDV7TGWTKZnxIuDYZFCXFDK/iRjuAavlS/Gh7K/EUZAw1duPFjNFcTGyC4c
    lmxci4BupbFyASY1qtsWcqfXG7Lxqpq3UYt7skZObNRc7o4zSX0vD565jLGdjJCavp3HPg6sp5YK
    643OlgalOlPLUjr8TLXxS9E+WrcoYfNaVRacCMVgoVHeDs+BtOayrLrcnJub3npjx5Dw+TLuLUwd
    Wn+FsxSUlo00ej0tqYqlGlU3xRJo88+OXnm2EnvOlidn2Wenr8jRcnGVmrMxMYxNZhWz4EbjLKre
    2iMUndk1lBZK7Ki9rWKal6OxMbX1K31uAEvedi0Fm0sivWOsCZWUtCLkAJq+dZLMog78AvyAsTfg
    QFoACIJiBJYgJkEkBsi5VWuLlMwuE1LZS5NypWZSb+Ff2Jzzew33RJbonEfcmibuIf2RpG4+m/L9
    JIAJDzQNlaz+wkWsUr/cSJLdZIstcQpVH+Bl+RqfCwzntW4uW5Kp8LK8nU+FkaLkMsqc+uLIlGS3
    plEAJN9TJcWuoKgkWfAloCjBazFgKMgvYqDEAl7iLgCSOsm4xW5gqSleTRuQwaqJqfukYCGWmsxu
    ZklobrD1UhpypU8P7NGldmxyUNPYRki1vCaeqOjolL2fZ0sOUlF66kOT6ijlPin+YRKrOV0XjL2T
    TlUy1LWs2bUG3FAZk7o520MMl7aR0IsxYtN4eVjEwxaHFtdbtxW3s3sjHKTzNMhS6jlkvPOMj3X0
    Edb7jFmDlwJjOsmZ8C0bP8zDctGq4xski4LSlZiPtMo5Nu7IjNxdxgvmYTbZRyu7sZi4Ms4tK6KK
    Q5V5bFLkwZMwzGNSFxhq9yblLk3LiLXZKkY7hMmJq7k2RcrmGYuGrXFyuYZgLXIK3Fyosjew33Zo
    XN7DP7Iy6+NFd+xY1bGzXehrG4+mvKACxHnSUxH3EixjxH3EiS3WG+9p05fybfk/6Ec+p/DLvEcN
    T4F3h6Wnsnk5a+pHihTndN8QsXS4syPC0uBHNKfAa11wo8VSf4/0MU50pv7+S+hsc0p8BzSnwNck
    6YKOJwcF7XtfQzc9wPwLuMHM6ZHM4F5sdFWxzzA/Au4c8wHwR7jW5nTHMoF7Dohs872f8Ee4jnGz
    31LuNbmUBzKBe1OiGzy+z31LuKVKuBy+xluYOZR4kcyjxHadEJ5Si+qHeispUn1Q70TzGPEjmUeI
    7JT49WSisI39q4r8jZhQwNR/ZtP6GlzJcTZwkI0IvrZYmZOisNmcow0RMKmZbjSrYhKV3uRs0KkK
    sFKD16z1QmYzNvLoY4Ta0dzPG2W7KSSfu2ZoRKooohV4v5iKu7PQpUwzesdAimInG6klqbNGopwV
    jm16VRR94vgqjScZt6cDOtY6qZadpU2jReMUNFSnL5lfWE3pGjp8yTaISazLUq0YKpLTrIhhac/x
    W/MrVpVKk3JXVzHzer8T7zlbyQx8fW3zCn2sQtnw6qsTT5Ct8b7xyFb433mOa/Ghu+ro9rEj1Yu1
    iafI1/jfeTyeI+N947E+NDb9WLtUPVn/ADImpyeI+N95GTEfG+8dh8Zueq32iI9Vy6qi7jUy4ntH
    3i2KX8x945p8ZtS2bKMbuSt+RrchFuyqK/5GGrUxMdJVXbgYJ1Zxa1Mz5LfxY/5q/wBlnq5aUnGU
    kWglJXVu80KlVyneTuXpTlf2b2MTa7pHh8Ufbq08DOrHNBot6srf2jRp42vGVqbaubKxeL+N9xuv
    kn+sX8FZ/wDVl9V1v7RD2bX4foU53jPifciee41fi/RG+xz+Mstm1/h/Qera3w/oQsfjFvf6In1j
    i+P6IdifGR6vr/C+4lbNxD3QfcPWWL4/oiVtTFr/APESfJJ8ZHq3E9m+4q9nYlb4PuMnrbF/2kQ9
    q4mWjV/ojMeWf7B8Zi5lW+E2KNKdOFpIxc4q1HrD9S/LySs4G+WtR4JhNSjOa9hXMawtbs5dxeGO
    qU/dj+hf1pWS1gu412QW8MywPDVr/dy7hzet2cu42PW9TrgT64l2aHOHP48tXm9Xs5dxjxGHqrDy
    eSXcb/rd9mjHidrZsNJcmhyWPBMLotwMFOvCW5ou60I2u9DxvpQzsGNVqclpNd5bPF7mirqwIuLj
    VSQGUqTVOm5PqKi4MVGo6sM1rJ7jJcCWQLkASCBfiQAQmuINQJI0aBhn7Es05WXAuqpXpqWlzYpK
    NGmlHQ01isPKolexsVFnh7MtPkda3YvVtxnGUfaZXVbpo5vOPtOTgpTl8kbMaMpL288GeiLRjhja
    U4VNJStIl/Z+62/qaUsO29KjM9KCpxs5N/mzE+SIWKTKzlKpvRMYqK0MdSvCmrtpfU5+I2rThe0r
    v5M4TaZ+neKxH26bklp1/IOLSvLR8Dg+uKm+nBJ8XqdDAY2WLi3U94zMSTaG4CLi/wAjEyJBAAkE
    ACyBFxcInQx1YqUX1fkXBRzp1503leq+aOfiV7d+J1MXhqtR3g01wObPCVYT9p2Nw42mWtZuRtU5
    QX3iuYp0Jxd7mKWZPVOxZcnWwUJRV3TzI34NSWsbGhga6hTy5lL/AFHQjJtaqxymXesLWXAWXAEj
    XRGWPAZI8CQDDJHgMkeAuSBXk48CeTjwJA0Mq4EcnHrKyqxh7zKRxVOTspIaMvJQ4Dko9SEasX1l
    lJdQ1VeSjwHIQ4F0ybjUxj5CD6jFisPBYaehsmPFP+FmarJMOBFtapmeniZLSWqNZEreYbisNp1q
    e9JxZEsRZaSua0ihYlJo6OHrRk/bqWNy0mr0q6fyZwQrp6Oxr0nGztOtWg/aSZgxGJdTLBppX1Of
    mnvzMnlZX3j/AMUyzrxxdKKSWiRkhXhPc0zi8s+BkhPW70Ivt2sySuY54iEfmc54pbrmOpX0vewy
    Vb7xV9yMc602nvNFYizvcyLGXVhxk9NzCSk5+1c3bN9Rx44xwehkW0KnUkzE7Cum4y6jA1WhO/J5
    1wNZbTqL8KLx2tNb6cWTZVtqtwwbv9PM2aEZYiElKlyfyNGO3JR05CBmj6QStrRX0NZLMyTpvDya
    hTsYJYiq9Mku42V6RcaL7y3SGD30H3muM/qRb/GvGtOVkqU/zZStDF1NKeWC+ZudIKX/ALd95Se3
    Yv3aNh7hvlrk1dlYur71a5g9Q1/jizsS2tCW+DJhtHDfjUhHltH8YmuuP6kxC/FA2tn7OxGHqPM4
    2fA6y2rgUvdfd/Qn1tgupfozU3tLnNYhVYao9Uiea1vhMsds4W1tV9GW9bYT4/0ZOOrya/Nqvwjm
    9VfhNn1phLfefoyPWmF6p/oxxg5tfm9X4WRKjUjvjY2JbUoW9mRgljKUnd1EYmYhYnVMsuAyy4Fu
    cUn+NGfD1aDleVSJItrTXyS4EOEuB1lXoP8AmQ7yeVoy0zw1+Z04yxzhw6laFLWTOZicXCrO6V7G
    ztim6ddyjaSfBnHcp391osRJOSyzrzlLdZDlFL3o3MOaf5ExUnvHtjjDr4ajQSU8tpG65JK73HKw
    lVQeeacmtxmlWnVd3ouBzbiIhvxqRnudy5pUKmRGalNzlqGmcEX1JAABFVE5qEbs59fH78g2jXy+
    ymciUnJmorpLaq4yU+u5hjVlmutDGmkRKd3oa4sSzyxdRaOZsUdoSgveucySzcCYzXu2E0g136W0
    ov3kzcpVo1FeDPLKq4mxhca6NVa+y2Y4yuvS3MWKf8LMmnUU6cZLc0VxX+Fn+QiTXBixfUiI6zLt
    C0txQtLcVuWFQSQ2RcotchuxS7IuXE1fMVdYlM1qm81WGLSyyrte6isKut5u5gbCZ0iHPWV1XfTc
    TyrMVxcYayOo2ZqFS7tc1Mxek7SMzHpYs6VlxJUU+s1eXit5bnEeJyyXWJbGUW+Zr84jxHLx+IZK
    ti3zJua/LR+InlY/ETJTWe5JhVSL/EZIQdR2jqBfQKLluVzoYTZqftVbnRhRo0VaFNfmyGvP5Gt6
    sRrwPRZqS96CMU8Ph57oFHDtZalGdyeyadSnmhKzNCrs+tS3RzIYNO4UkuomVOUd6sRYYi12QVsy
    U2TFXRDKp2JuMTBN8WWzyW6T7yE7Et36ipxhDlJ75N/myuj6i30BdlchVxj8K7iVFcEGLjlJkLJF
    0jHF6mzSjnlYms4Qi3uNulTyL5iFNQXzLkRIAKBJAKribTl9q0c6U7HT2tRalnOS7HWrNkObGcoy
    Lm8c9Xc7kLiiugukMNZVLiTL3bow3LKWliYPSbIrcrhEuuKNvEv+Fmc7YUHGhOT3O1v1Ohif8NM4
    f/TUODDcWW8yrCyg7PeY2rSaMu1UVHZGG5kq7jEahdGwbdPZuMqwU6eHnKL3NIS2ZjYrXDzX0NDT
    vYi5mlha696lNfQxulUj70GiotRjndma9ZZZGaLyMitGNTVby1lJhq7yLEyTiVvodHFJDIbG8oI2
    cPFPeY6FCVXduNqMVDRGLy3WNVdKNyOSiZSDnsuuKcjEcirbzItw6hylMY+RVt45BPrMttC1JKVS
    KfEnKTGzs/Y8q7zzllhod2hg6GGjaKV+Jjp1VTpQhHTQpUqtdZmZ0xuzlGMbpmlUxDvruKU6z/E7
    irBVFmi/oFY6la73kc4aklcxujInknvsBtqvOyszPSxM90jQi7GSNT2tQjZr4ehi46ezLijh43B4
    nDSdnJx6mjs5lHVGRSjXpunPVNbzXIeVdSsutkctW+Zv47Dc3quzujVaLsGSw8vWRPL1i6VybDYT
    JU5xVJ5zU4ItZcBZW3DYPavPKi/Ciedy+FENLgTkXAej2c7fXFGWnVc+oxZI8DaowSjojMzC5K0d
    5tYT7wwJWNnCe8zGrjbYBFjTCQCSogkADHXpRrQyyR53G4V4ebPTM5O1uRmve9o6VJcJlC0lZlbn
    bHGUXFyAVEmfCUJYirGEV16mKnBzdlvPTbNwMcLTTteb6zne2Daw1JUKEaa6kWxP+FmXSsUxX+Fn
    +Rwj7dYhTGUst5M5zoq97s79WnHEwypq/Eweo69rqcTlES1VxJYdS6zZ2bsvnOIjvyxep0fUeJ4x
    OhgcHjMLHJGNM6xEtzMN6jFU4Rpw0jFWMqjUW7LYxw5zFaxgZU61tYx7yTWXG2p9t74xsVlDNvpJ
    ls+X3mjHUxUYvR3GSzqebUZe9RicXbUMJC1KnRjyj4HRq7SyK0Um/wAzhTV68q055pM3FZWJcfE4
    KUm3GOppSwVZfgueglUS1lfuMLrw+fcd4rJMw40MBXl+Cxlhsuo3qv1OtHERe5NkrExvbIxxk1pz
    wkqdJRjE1cj4HaVXMt3ezFUwLqyvTmkYnxtxfHKcGR12OlPZleO53+hansacvalUV+Bia41zctbg
    9x1vV1SN8yS+hrzo5XaULfQ5y39tHqM2EhnrxtuMuSPBG7hYwpRzWRNMlmm1FpcDnYzF5XaJtVq0
    Vc5VWLqVHwLEDPhsRUqR1LPGSpSsyi9iForUwyozqu3EuGuhDFOWt0zNCrfrNCFPkI5Wy8aii95m
    RsVajUi8JXRr5oy1uZI1oJEVlVXNOz3G1RkkjmOur6IzQxNlqUblaCrU3FrXicKrBwk4yVjt06uZ
    I2obKwuMjnqZlL5M3X2kzjy0dLko9PL0aw8vdqyj+pTovDqxL8P9TXCWOcPNEvcehl6LT/DiF9Y/
    1MM/RnFL3akZfT+pOMryhwyTry9HMcuqL+pR+j+P7OPiJxldhy0bdH3SlbB1sNPLUjZ/IyUotQMT
    CwlGzhPeZrJWMkXOPuysZhZdAf8Ag0OUq/EzHWxdSEGnLU7UrynHOWfF46NDRas589oVZ6qVjTqS
    lOV5Mi9j6ni/5a57cLeTPps89r/Gxz2v8bNXMLnf4/j/ABjnLYnja8tHIwSm3v1Kg1HhpH0c5Yp6
    9RjaXA2HYhifDEs6wZEMi4mWyGVHP49V1FNKMk0z0OE2jSnTSnK0jz+VFor5nK//ACRJFserjXpy
    Wk0RipJ4Wep5uNTL1mfntRUHG90eef8AktV07Yej2bnq1FwPQJWSR88w2150PdlJfQ24+kE0/fke
    aPX8ae7SLWPDL0ik/wCZLuHrzNvrPuHL/DjL3Ro47FOEskHqeUW1oP8A4iXcbFHFKazKWb5ssTpN
    ZdWpiJ2tfUxNTy5nL9TSeJjFXveRSeNqZbaWOsQzjNUk03dmFxbV7M1qUqmJr5I72dp7IqpK1YbE
    GOa42W5mN0W90TqPY+JvdVYkPZeLW5p/Ucq/o5sKbj1FWssrnQezMb8H6o162zsYnfk33ouwIp2l
    1GeKSV2v1MVLC4iK9qlIvKNRRs4S7ho2aFOVSXsysvmb9PCwtrNt/kc/CSnSvJxbX5HSpSzQU1dX
    J6VKwkL2nK6+RkngcFyTzRcnYo5tJu70NGW04VJyi4zvHfoZnJWNhb1Xgp+/DKvzZo7Qo08PFqnf
    KbscZnjanSl9StacK9B06ytLqscprDpW0vMVqt779DAqmup057KnKblntHqL0tmU4yzSd2ZzHT7a
    VONaovZgZY4XEt3ukdPkWutWGSXVJDG+LlVcDipO6lEwyweLjvjc7ihNdaLpyfUXDi87CFaLtJMt
    PNDemehnRuvaiatXDp9WhmYTHMoxco57G7hMFUxV8u6JmpUoQjZLedrZOG5OMptWvYkV1i041aGy
    6mVbjfp4OpTjZM3VFF0dq0cJtrTVKuusPnEd5vIiTS3m8ZaTqVrXUboLEyW+Jlr4unRg22kjhYrb
    N3JU7P6Mk6Y7CxbelilbFRpxvUnlPPxx2Jl+JRTMNSp+KV5P5meTcVZsfiY162aCutdWTs3CSxWI
    3LIt5s4PZXOaSq1ZNReqSOtg6NDAxtBPXiT7/izPFaps3CSetFfRswz2LhJLSLj+TZt88op6tr6D
    neHeiqLuZuKVZ5y42O2PHDUXVhU0XUzy9abnLU9jt3Fwhgsqkm2zxMpLievw+Ou6lrTiJGNpITqW
    MSm2z37EOP2yXFypN7IRIXJIuhcuoDQi4uNAEkDRKJSIRIBoiT9hk3KTfssxf6R9MhsPZk1rgqPg
    XkS/RrZE9+Dh9EkeYj6duP8AwX+4zL/+g2X+B/3Hycd+TvP0T2Q/+HSMb9Dtkv8AlyX1ON/6hf8A
    Qf7h/wCoX/Q/7hhrrP0L2U+qa+r8zIvRvZ+Hp5eUkl+f9Tg1fT+c1aODy/6jXfpq5e9hL/6iezZd
    2WwsPU9nDVGn8zWxHo5VhBt16aVt8tP/ALOVH01nTTdPCpSe55txzq3pRjq83KpK64aeRfY9RsfZ
    fIVZVJzhNLrW469m5e/Gx5LZ3pfSpUcmLo1G/wDlpeaNxemOy7/4fFW+UY/uONqWldejk5JaW7yI
    zfC7/M4D9Mtj5bLD4zwx/cY36Y7MXuYfFfVL9xz67I9Pra9inKvNZwlbieZ6YYDqhi1/pj+4leme
    By2dLFeCPmXruvp6V1o33PuGei9+U8y/TPBJexQxDfzjHzMXTHDp+zQqpf8AbHzLwubD0ePsqDdN
    a/JGDCuvyeaq0l1JI4/THBTilUpYn6Qj5jpbsvscX4Y/uNxFv66Rav8AXclVb0jFGB02228sfocr
    pZsrssZ4I/uKv0p2VLfSxnhj+43kryq60lpaFmVVF39pI5S9J9kLdSxnhj+4dKNl9njPDH9xOMtR
    5KutKm48LcDFKGbcrHLn6T7Na9ini/rGP7iKfpPs5P2qWKf5Rj+4cZXsq6TpS4FeTa3mn0q2Zf7j
    E+GP7jHU9J9nS3UsSl/2x/cOMr2w6Sp3M8KaW6xxOk+BSsqWI8K8x0nwVtKWI8K8yZP4nZDuSoqe
    +RCw0etvuOJH0owi/l1/CvMuvSzCL+VX8MfMuf4dlXWWFhGaeuhvquoU7U966jza9LMH+KliPDHz
    HS3B9VKv4Y+ZOLEzWf69D6wqwXtUpP8AIstrQ/FFr8zzr9LsHfShX8K8yH6WYB/8PX8MfM37c5iH
    oa216MVfPFfXU59fbM6jtSg3/mbOFiNubNxLvOhiE+KS8zB6y2d1PGL/AEx8yTpGOpUlWryvVqN/
    K+hHJxS0RoR2vs1b1i3/AKY+ZljtvZa30sU/ov3GJrd0iatm1iKVPlsXCDajG+rZjW39kLfhsS/o
    v3EVNv7Knuw2Ii+KS/cZilvxZvX+PVrEUKVOMISi8qtozWq4hTfvxX1PNevNl3+7xfcv3E+vNlPf
    DGd0f3HT3+Ofp26laCX3if8AqNWU4t3zrvOd652M/wAGN8Mf3EPa+xWtYY7wx/caiE9MW0q7lLLm
    0XzOZfTedKeM9H6jvKG0PDH9xXl/Ry33e0PDH9x66WrEMWcmbLU91zcqV9jZvsqGJa/zb/8A5ERx
    ey0rc3rd/wDU6dkfrONfKw0Zp4vZ7XsUaq/v8zDzjDfDU/v6mu6qZKLIkq6+H6oT/v6kvEUPgl/f
    1HfUwIuOcUfgkUdan1KRe6v6YyXCZi5aPBjlo8GXur+nFlRNzFy8ODHLx4Md1f04styk9zK8vHgy
    HWg1azMW8tZ/qcWAAHjdAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB//2Q==
    
  - text/html
    
            <iframe
                width="400"
                height="300"
                src="https://www.youtube.com/embed/DCub3iqteuI?start=495"
                frameborder="0"
                allowfullscreen
            ></iframe>
            
  - text/plain
    <IPython.lib.display.YouTubeVideo at 0x7fdc8461de48>
  metadata
    {
     "collapsed": false
    }
markdown
    To implement the *sieve*, we can use a recursive generator function:
code 67
    def sieve(stream):
        x = next(stream)
        yield x
        yield from sieve(y for y in stream if y % x != 0)
  metadata
    {
     "collapsed": true
    }
markdown
    In SICP, they are using what they call "streams" (implemented in LISP) to represent the infinite sequences of natural numbers and of prime numbers, respectively.
    
    We can get a similar thing in Python by using generators.
    The generator function `sieve()` takes the first element from a "stream" and yields it.
    Afterwards, it calls itself recursively using a generator expression that filters the remaining sequence.
    
    The filtering could of course also done with filter(), see [above](#Filter), but the generator expression is more Pythonic.
    
    To get our infinite sequence of prime numbers, we have to apply the `sieve()` to the natural numbers starting with 2.
code 68
    def primes():
        return sieve(itertools.count(2))
  metadata
    {
     "collapsed": true
    }
markdown
    Calling this function returns an infinite generator object that yields all primes on demand.
code 69
    list15(primes())
  execute_result
  - text/plain
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
  metadata
    {
     "collapsed": false
    }
markdown
    Those seem to be the right numbers, but this recursive Python implementation has a problem when we look for larger prime numbers.
    
    To see that, let's create a helper function that shows only one given item from the sequence instead of the first few:
code 70
    def nth(n, it):
        """Return n-th element (0-based) from iterable it."""
        return next(itertools.islice(it, n, None))
  metadata
    {
     "collapsed": true
    }
code 71
    nth(0, primes())
  execute_result
  - text/plain
    2
  metadata
    {
     "collapsed": false
    }
code 72
    nth(9, primes())
  execute_result
  - text/plain
    29
  metadata
    {
     "collapsed": false
    }
markdown
    While we're at it, let's measure how long the computation takes for a somewhat larger number ...
code 73
    %time nth(482, primes())
  stream stdout
    CPU times: user 44 ms, sys: 8 ms, total: 52 ms
    Wall time: 66.5 ms
  execute_result
  - text/plain
    3457
  metadata
    {
     "collapsed": false
    }
markdown
    This works fine with small numbers, but there is a limit (depending on your Python interpreter settings), you can try it on your own:
code 74
    #nth(490, primes())  # maximum recursion depth exceeded!
  metadata
    {
     "collapsed": false
    }
markdown
    The problem is that (C)Python doesn't eliminate tail recursion.
    In other languages (e.g. LISP) this would work fine, but not in Python.
    It's possible to increase the recursion depth in the Python interpreter, but this would just shift the problem to slightly larger numbers.
    
    But anyway, why would we solve an iterative problem with a recursive solution?
    
    We can easily create an iterative implementation by applying a few minor changes:
code 75
    def primes2():
        collected_primes = []
        for x in itertools.count(2):
            if all(x % p != 0 for p in collected_primes):
                yield x
                collected_primes.append(x)
  metadata
    {
     "collapsed": true
    }
markdown
    Now, instead of storing the intermediate state on the stack (where it's hidden in the recursive implementation), we just explicitly create a list of all so far known primes and append each newly found prime number to this list.
    
    > Important Note: The function all() is short-circuiting, i.e. the divisibility test is only executed until the first match.
    It's important to use a generator expression here, because if we would use a list comprehension instead, the predicate would be calculated for all items and the whole intermediate list would have to be created on each iteration. This would be much slower and use more memory.
    
    Let's compare this with our previous implementation:
code 76
    %time nth(482, primes2())
  stream stdout
    CPU times: user 28 ms, sys: 0 ns, total: 28 ms
    Wall time: 28.8 ms
  execute_result
  - text/plain
    3457
  metadata
    {
     "collapsed": false
    }
markdown
    The new iterative implementation of course yields the same result as before, but it is also faster!
    
    And now we don't have this silly recursion limit, it also works with much larger numbers:
code 77
    %time nth(5000, primes2())
  stream stdout
    CPU times: user 2.56 s, sys: 0 ns, total: 2.56 s
    Wall time: 2.89 s
  execute_result
  - text/plain
    48619
  metadata
    {
     "collapsed": false
    }
markdown
    Some time after writing the above implementation, I stumbled upon a blog post called [List, Dict and Set Comprehensions By Example](https://www.smallsurething.com/list-dict-and-set-comprehensions-by-example/), which also uses the Sieve of Eratosthenes as an example.
    However, it doesn't use generators but set comprehensions (which I only mentioned very shortly [above](#Set-Comprehensions,-Dictionary-Comprehensions)).
    It also has a different API, since it doesn't produce the results one by one, but instead calculates all prime numbers up to a given upper limit.
    
    The original code has a second set comprehension in the last line.
    I took the liberty of changing that into a list comprehension, since there are no duplicates anymore at this point and the order is actually relevant.
code 78
    def eratosthenes(n):
        # Based on: https://www.smallsurething.com/list-dict-and-set-comprehensions-by-example/
        not_prime = {j for i in range(2, n) for j in range(i * 2, n, i)}
        return [i for i in range(2, n) if i not in not_prime]
  metadata
    {
     "collapsed": true
    }
markdown
    As it turns out, this not only works but it is also significantly faster!
code 79
    %time result = eratosthenes(48622)
    len(result), result[-1]
  stream stdout
    CPU times: user 76 ms, sys: 4 ms, total: 80 ms
    Wall time: 78.6 ms
  execute_result
  - text/plain
    (5001, 48619)
  metadata
    {
     "collapsed": false
    }
markdown
    That's it, have fun generating prime numbers!
markdown
    <p xmlns:dct="http://purl.org/dc/terms/">
      <a rel="license"
         href="http://creativecommons.org/publicdomain/zero/1.0/">
        <img src="http://i.creativecommons.org/p/zero/1.0/88x31.png" style="border-style: none;" alt="CC0" />
      </a>
      <br />
      To the extent possible under law,
      <span rel="dct:publisher" resource="[_:publisher]">the person who associated CC0</span>
      with this work has waived all copyright and related or neighboring
      rights to this work.
    </p>
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.5.2rc1"
     }
    }