# 1. Performance Optimization¶

## 1.2. Seven strategies¶

### 1.2.1. Line Profiling¶

• `pip install line_profiler`

### 1.2.2. Numpy vectorization¶

Fig. 1.8. Scipy Ecosystem

### 1.2.3. Specialized data structures¶

• `scipy.spatial` - for spatial queries like distances, nearest neighbours, etc.
• `pandas` - for SQL-like grouping and aggregation
• `xarray` - for grouping across multiple dimensions
• `scipy.sparse` - sparse metrics for 2-dimensional structured data
• `sparse` (package) - for N-dimensional structured data
• `scipy.sparse.csgraph` - for graph-like problems (e.g. finding shortest paths)

### 1.2.4. Cython¶

```def primes(int kmax):   # The argument will be converted to int or raise a TypeError.
cdef int n, k, i    # These variables are declared with C types.
cdef int p[1000]    # Another C type
result = []         # A Python type

if kmax > 1000:
kmax = 1000

k = 0
n = 2

while k < kmax:
i = 0

while i < k and n % p[i] != 0:
i = i + 1

if i == k:
p[k] = n
k = k + 1
result.append(n)

n = n + 1
return result
```
```In [1]: %load_ext Cython

In [2]: %%cython
...: def f(n):
...:     a = 0
...:     for i in range(n):
...:         a += i
...:     return a
...:
...: cpdef g(int n):
...:     cdef int a = 0, i
...:     for i in range(n):
...:         a += i
...:     return a
...:

In [3]: %timeit f(1000000)
42.7 ms ± 783 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [4]: %timeit g(1000000)
74 µs ± 16.6 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# which gives a 585 times improvement over the pure-python version
```

Fig. 1.9. Cython compiling

### 1.2.5. Numba¶

Numba gives you the power to speed up your applications with high performance functions written directly in Python. With a few annotations, array-oriented and math-heavy Python code can be just-in-time compiled to native machine instructions, similar in performance to C, C++ and Fortran, without having to switch languages or Python interpreters.

Dask natively scales Python. Dask provides advanced parallelism for analytics, enabling performance at scale for the tools you love

## 1.3. Use `set` instead of `list`¶

Jeżeli masz listę w której sprawdzasz czy element występuje, to zamień listę na `set`, dzięki temu będzie lepsza złożoność

```NAMES = ['José', 'Иван', 'Max']

if 'Max' in NAMES:
pass
```
```NAMES = {'José', 'Иван', 'Max'}

if 'Max' in NAMES:
pass
```

## 1.4. Use `list.append()` instead of `str + str`¶

```# Performance - Method concatenates strings using + in a loop
html = '<table>'

for element in lista:
html += f'<tr><td>{element}</td></tr>'

html += '</table>'
print(html)
```
```# Problem solved
html = ['<table>']

for element in lista:
html.append(f'<tr><td>{element}</td></tr>')

html.append('</table>')
print(''.join(html))
```

## 1.5. Range between two `float`¶

• Uwaga na set zawierający floaty, bo pomiędzy dwoma wartościami jest nieskończona ilość wyrażeń
```range(0, 2)
# 0
# 1

range(0.0, 2.0)
# ...
```

## 1.6. Inne¶

• Jeżeli coś `collections.deque` - Double ended Queue
• Serializowanie kolejki przy wielowątkowości

## 1.8. Assignments¶

### 1.8.1. Memoization¶

• Filename: `performance_memoize.py`
• Lines of code to write: 5 lines
• Estimated time of completion: 15 min
• Input data: Code Listing 1.73.
1. Skopiuj kod z listingu poniżej

2. Stwórz pusty `dict` o nazwie `CACHE`

3. W słowniku będziemy przechowywali wyniki wyliczenia funkcji dla zadanych parametrów:

• klucz: argument funkcji
• wartość: wynik obliczeń
4. Zmodyfikuj funkcję `factorial_cache(n: int)`

5. Przed uruchomieniem funkcji, sprawdź czy wynik został już wcześniej obliczony:

• jeżeli tak, to zwraca dane z `CACHE`
• jeżeli nie, to oblicza, aktualizuje `CACHE`, a następnie zwraca wartość
6. Porównaj prędkość działania

Code Listing 1.73. Memoization
```def factorial_cache(n: int) -> int:
raise NotImplementedError

# Do not modify anything below
from timeit import timeit

def factorial_nocache(n: int) -> int:
if n == 0:
return 1
else:
return n * factorial_nocache(n - 1)

duration_cache = timeit(
stmt='factorial_cache(500); factorial_cache(400); factorial_cache(450); factorial_cache(350)',
globals=globals(),
number=10000,
)

duration_nocache = timeit(
stmt='factorial_nocache(500); factorial_nocache(400); factorial_nocache(450); factorial_nocache(350)',
globals=globals(),
number=10000
)

print(f'factorial_cache time: {round(duration_cache, 4)} seconds')
print(f'factorial_nocache time: {round(duration_nocache, 3)} seconds')
print(f'Cached solution is {round(duration_nocache / duration_cache, 1)} times faster')
```