Slides

# Intro to Python
## Week 10
### Big O analysis

---

## Agenda

- Big O (Complexity Analysis)
- A tree for your game

notes:

- [ ] finding a value in a list
- [ ] finding a key-value pair in a list
- [ ] big O
- [ ] while loop for game play

- [ ] dict for classify_text "mapping"
- [ ] poor-mans machine learning using dict lookup
- [ ] `.get()`
- [ ] global dict with game data
- [ ] `dict`s as kwargs instead of mutable args
- [ ] insidious semantic/logic `dict` errors (mutable default args to functions)
- [ ] `__dict__`

---

## Download a markdown file

```python
>>> import urllib.request
>>> url = 'https://nlpia.org/fall26/tlacs/'
>>> url += '12-Dictionaries.md'
>>> response = urllib.request.urlopen(url)
>>> text_bytes = response.read()
>>> text = text_bytes.decode('utf-8')
```

### Lab

- Write function do download the chapter 12 (or any other filename)
- Find first occurrence of the token 'KeyError'

---

tokens =

---

## Complexity analysis

- How much CPU?
- How much memory?
- Does it scale?
- Throughput

note:
- the inefficiency of crypto contributes to global warming
- the innefficiecy of AI is destroyed 100,000 ac
- can you add more and more rooms

---

## Does it matter?

- Google: illegally cut 250,000 trees
- Meta: 5GW of Methane at $27B datacenter
- Globally: 415 TWh / year

note:
- Goog: Finland - tight carbon emissions and enviromental impact law
- Meta: Louisiana - loose and corrupt environmental protections - Katrina
- Glob: 1.5% of all electricty, and it's mostly fossil fuels

---

```python
>>> tera = 10**12
>>> watt_hours = 415 * tera
>>> hours = 365.25 * 24
>>> watts = watt_hours / hours
>>> watts
47342003194.15925
```

---

```python
def get_multiples(value, base=10):
    """ Count the multiples of the base (default=10) required to get `1 <= value < 10`?

>>> get_multiples(1000, 10)
    -3
    >>> get_multiples(0.0999)
    2
    >>> get_multiples(47342003194)
    -10
    >>> get_multiples(0)
    0
    >>> 47342003194 * 10 ** get_multiples(47342003194)
    4.7342003194
    """
```

note:
- You have 10 minutes
- Pass as many doctests as possible
- Improve incrementally
- A stopped clock is correct once a day: 1st function should `return 0`

---

```python
def get_multiples(value, base=10):
    """ Count the multiples of the base (default=10) required to get `1 <= value < 10`?

>>> 47342003194 * 10 ** get_multiples(47342003194)
    4.7342003194
    """
    multiples = 0
    while value >= base:
        value /= base
        multiples -= 1
    while value < 1:
        value /= base
        multiples += 1
    return multiples
```

note:
- anyone come up with something simpler?
- anyone use the `math.log` function

---

## Run doctests

```python
>>> import doctest
>>> import your_module  # without .py
>>> doctest.testmod(your_module)
TestResults(failed=0, attempted=8)
```

---

```python
>>> hours = 365.25 * 24
>>> hours
8766.0
>>> watts / tera
0.04734200319415925
```

note:
- approx 10k hrs in a year
- 47 GW

---

```python
units = {
    'Mtoe': (11.63, 'TWhr'),
    'min': (60, 's'),
    'hr': (3600, 's'),
    'h': (3600, 's'),
    'yr': (365.24*3600, 's'),
    'min': (60, 's'),
    'g0': (9.8, 'm/s**2'),
    'gees': (9.8, 'm/s**2'),
    'J/s': (1, 'W'),
    'W*s': (1, 'J'),
    ' ': (1, ''),
    '^': (1, '**')
    '⋅': (1, ''),
}
```

---

```python
number_words = {
    'one': 1,
    'two': 2,
    'ten': 10,
    'twenty': 20,
    'hundred': 100,
    'thousand': 1000,
    'million': 1_000_000,
    'billion': 1_000_000_000,
    'trillion': 1_000_000_000_000,
    'googol': 10**100,
    'googolplex': 10**10**100,  # serial exponentiation right to left
}
```

note:
- 1920, Edward Kasner's 9 yo old nephew
- Milton Sirotta suggested googol = 100 0's
- suggested googolplex = "...writing zeroes until you get tired" 
- typical book has 2500 characters (500 words) per page
- silicon atom 0.2 nm (hydrogen 0.1 nm)
- EUV lithography 13.5 nm lambda (7 nm "resolution")
- transistors have layers 10-50 atoms wide

---

```python
number_words = {
    w: i
    for i, w in enumerate(
        'zero one two three four five six seven eight nine ten'.split() +
        'eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen'.split())
}
```

---

```python
multiples = {abbrev: 10**(3*(i-3)) for i, abbrev in enumerate('nμm kMGTPE')} 
multiples.update({abbrev: 10**(3*(i+1)) for i, abbrev in enumerate('k')})
multiples.update({
    'nano': 1e-9,
    'micro': 1e-6,
    'milli': 1e-3,
    'googol': 10**100,
    'kilo': 1000,
    'mega': 1_000_000,
    'giga': 1e9,
    'terra': 1e12,
    'peta': 1.
    })
```

---

```python
def convert_to_si(text):
    """ Try to convert text into a numerical value in SI units

>>> convert_to_si('2 gees')
    (19.6, 'm/s^2')
    >>> convert_to_si('3 km')
    (3000, 'm')
    >>> convert_to_si('2 GWhr')
    (2000, 'm')
    """
```

---

## Constant time

$$O(1)$$

```python
def do_something(a=0, v=0, x=0, dt=0.001):
    x += 0.5 * a * dt**2 + v * t
    v += a * dt
    return dict(a=a, v=v, x=x, dt=dt)
```

---

## constant time

$$O(1)$$

```python
do_something()
```

---

## Linear time

$$O(N)$$

```python
for i in range(n):
    do_something()
```

---

## Linear time

$$O(N)$$

```python
n = 1_000_000
answers = [dict(a=9.8, v=0, x=0, dt=0.001)]
for i in range(n):
    kwargs = answers[-1]
    answers.append(do_something(**kwargs))
```

---

## Quadratic time

$$O(N^2)$$

```python
for i in range(n):
    for j in range(m):
        do_something()
```

note:
- doesn't matter if n and m are different
- all that matters is that you want n and m to get big

---

## Quadratic time

$$O(N^2)$$

```python
n = 1_000_000
data_cube = []
for milligees in range(1, 2_000):
    answers = [dict(a=9.8*milligees/1000, v=0, x=0, dt=0.001)]
    for i in range(n):
        kwargs = answers[-1]
        answers.append(do_something(**kwargs))
    data_cube.append(answers)
```

## Cubic time

$$O(N^3)$$

```python
>>> import numpy as np
... N, M = 10, 10
... matrix = [
...     [j for j in range(M)]
...     for i in range(N)
...     ]
... product = np.matrix(matrix) * np.matrix(matrix)
...
>>> product
matrix([[  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405],
        [  0,  45,  90, 135, 180, 225, 270, 315, 360, 405]])
```

---

## Exponential time

$$O(2^N)$$

```python
for i in range(n):
    for j in range(i * 2):  # doesn't matter if it's 2 or 10 or 100
        do_something()
```

note:
- problem gets harder at each step