---
title: Fatos interessantes sobre arrays
tags: talk
description: Para ver os slides, selecione "Slide Mode".
slideOptions:
transition: fade
theme: sky
---
<style>
body {
background: #ffffff;
background-color: #ffffff;
}
.reveal .slides {
font-size: 36px;
font-family: Palatino;
}
.reveal .slides h2 {
font-family: Palatino;
letter-spacing: 0.005em;
}
.reveal .slides h3 {
font-family: Palatino;
letter-spacing: 0.005em;
}
.reveal .slides h4 {
font-family: Palatino;
font-size: 48px;
letter-spacing: 0.005em;
}
.reveal pre {
display: block;
width: 90%;
}
.reveal pre code {
max-height: 500px;
font-size: 22px;
line-height: 24px;
}
ul {
font-size: 30px;
}
</style>

## Fatos interessantes sobre arrays, matrizes e tensores: o número 3 vai te surpreender

slides: `https://hackmd.io/@melissawm/rkXK894Ad`

---

<!-- 1 -->
### O que são arrays?

----

<!-- .slide: style="font-size: 28px; text-align: left" -->

Uma **array** é uma estrutura de dados que armazena uma coleção de elementos identificados por, pelo menos, um índice ou uma chave. **As arrays mantêm uma série de elementos de dados, geralmente do mesmo tamanho e tipo de dados.** O índice geralmente utiliza uma sequência de números inteiros, mas o índice pode ter qualquer valor ordinal. Os arranjos podem ser multidimensionais, significando que eles são indexados por um número fixo de números inteiros, por exemplo, por uma sequência finita de quatro números inteiros. Geralmente, arranjos unidimensionais (vetores) e bidimensionais (matrizes) são os mais comuns.

----

<!-- .slide: style="font-size: 28px; text-align:left" -->

- :smile: Elementos são acessíveis de forma rápida
- :disappointed: Tamanho fixo; incluir ou remover elementos envolvem cópias e algoritmos pouco eficientes.
- Se o acesso aos dados for **arbitrário**, e o tamanho for fixo, é melhor usar arrays. Se os elementos podem estar ordenados e o acesso será sequencial, é melhor usar listas.

---

<!-- 2 -->
### Por que precisamos de arrays?

- Listas em Python são vetores (em C) de ponteiros para os elementos da lista. Por isso, as listas podem conter objetos arbitrários. ([Python FAQ](https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython), [SO](https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented), [código fonte](https://github.com/python/cpython/blob/5c22476c01622f11b7745ee693f8b296a9d6a761/Include/listobject.h#L22))

----

typedef struct {
    // PyObject_HEAD contains a reference 
    // count and a type identifier
    PyObject_HEAD
    Py_ssize_t ob_size;

    // Vector of pointers to list elements.
    // list[0] is ob_item[0], etc.
    PyObject **ob_item;

    // ob_item contains space for 'allocated'
    // elements. The number currently in use
    // is ob_size.
    // Invariants:
    //   0 <= ob_size <= allocated
    //   len(list) == ob_size
    //   ob_item == NULL implies 
    //     ob_size == allocated == 0
    Py_ssize_t allocated;
} PyListObject;

---

<!-- 19 -->
### Arrays

- Arrays contém elementos de tamanho fixo, o que permite guardá-los em um bloco **contíguo** de memória: ([Link](https://medium.com/@gough.cory/performance-of-numpy-array-vs-python-list-194c8e283b65))

- Se `arr` é uma array com inteiros, e `arr[0]` está armazenado no endereço `x`, então `arr[i]` está armazenado no endereço `x+i*sizeof(int)`


---

<!-- 3 -->
### Operações matemáticas


---

<!-- 3 -->
### Histórico

- Fortran
- BLAS (1979) - especificação de rotinas de baixo nível para operações comuns de álgebra linear
- LAPACK
- MATLAB
- Python
- Numeric/Numarray
- NumPy (2005)

---

<!-- 4 -->
### NumPy: a base da computação científica no Python

<img src="https://i.imgur.com/cYNJSgW.png" style="background:none; border:none; box-shadow:none;">

---

<!-- 5 -->
### NumPy: a base da computação científica no Python

- objeto `ndarray` (array homogêneo n-dimensional)
- capacidade de **broadcasting**
- funções matemáticas padrão com capacidade de vetorização
- ferramentas para a integração de código C/C++ e Fortran
- álgebra linear, transformadas de Fourier, gerador de números aleatórios

---

<!-- 6 -->
<!-- .slide: style="font-size: 20px;" -->
<img src="https://media.springernature.com/full/springer-static/image/art%3A10.1038%2Fs41586-020-2649-2/MediaObjects/41586_2020_2649_Fig2_HTML.png" style="background:none; border:none; box-shadow:none; height:550px">

*Fonte: Harris et al., "Array Programming with NumPy", Nature volume 585, pages 357–362 (2020)*

---

<!-- 7 -->
### Conceitos básicos: Vetorização

Vetorização é a capacidade de expressar operações em arrays sem especificar o que acontece com cada elemento individual (em outras palavras: sem usar loops!)

- Código vetorizado é mais conciso e legível
- O código fica (ligeiramente) mais parecido com a notação matemática
- Mais rápido (usa operações otimizadas em C/Fortran)

---

<!-- 8 -->
### Vetorização: Exemplo 1

In [1]: v = [i for i in range(1000)]

In [2]: %timeit w = [i**2 for i in v]
235 µs ± 9.64 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [3]: v_np = np.arange(1000)

In [4]: %timeit w_np = v_np**2
1.27 µs ± 39.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

---

<!-- 9 -->
### Como isso acontece?

As arrays do NumPy são eficientes porque
- são compatíveis com as rotinas de álgebra linear escritas em C/C++ ou Fortran
- são *views* de objetos alocados por C/C++, Fortran e Cython
- as operações vetorizadas em geral evitam copiar arrays desnecessariamente

---

<!-- 10 -->
<!-- .slide: style="font-size: 20px;" -->
<img src="https://media.springernature.com/full/springer-static/image/art%3A10.1038%2Fs41586-020-2649-2/MediaObjects/41586_2020_2649_Fig1_HTML.png" style="background:none; border:none; box-shadow:none; height:400px; width:800px">

*Fonte: Harris et al., "Array Programming with NumPy", Nature volume 585, pages 357–362 (2020)*

---

<!-- 11 -->
### Vetorização: Exemplo 2

In [1]: import numpy as np

In [2]: v = np.array([1, 2, 3, 4])

In [3]: u = np.array([2, 4, 6, 9])

In [4]: u+v
Out[4]: array([ 3,  6,  9, 13])

In [5]: np.dot(u, v) 
Out[5]: 64

In [6]: u.dtype, type(u)
Out[6]: (dtype('int64'), numpy.ndarray)

---

<!-- 12 -->
### Vetorização: Exemplo 3

In [1]: A = np.array([[1, 2, 3],
   ...:               [4, 5, 6], 
   ...:               [7, 8, 9]])

In [2]: A.T
Out[2]:
array([[1, 4, 7],
       [2, 5, 8],
       [3, 6, 9]])

In [3]: A.shape, u.shape
Out[3]: ((3, 3), (4,))

In [4]: A.ndim
Out[4]: 2

In [5]: u.ndim
Out[5]: 1

---

<!-- 13 -->
### (O que são essas dimensões?)

<img src="https://fgnt.github.io/python_crashkurs_doc/_images/numpy_array_t.png" style="background:none; border:none; box-shadow:none;" width=600px>

<span style="font-size:20px">https://www.oreilly.com/library/view/elegant-scipy/9781491922927/ch01.html</span>

---

<!-- 14 -->
### Vetorização: Exemplo 4

In [6]: A[0, :]  
Out[6]: array([1, 2, 3])

In [7]: A.sum()
Out[7]: 45

In [8]: A.sum(axis=0)
Out[8]: array([12, 15, 18])

In [9]: A.sum(axis=1)
Out[9]: array([ 6, 15, 24])

---

<!-- 15 -->
### Vetorização: Exemplo 5

In [1]: x = np.arange(-np.pi, np.pi, np.pi/8)

In [2]: x
Out[2]: 
array([-3.14159265, -2.74889357, -2.35619449, -1.96349541, -1.57079633,
       -1.17809725, -0.78539816, -0.39269908,  0.        ,  0.39269908,
        0.78539816,  1.17809725,  1.57079633,  1.96349541,  2.35619449,
        2.74889357])

In [3]: np.sin(x)
Out[3]: 
array([-1.22464680e-16, -3.82683432e-01, -7.07106781e-01, -9.23879533e-01,
       -1.00000000e+00, -9.23879533e-01, -7.07106781e-01, -3.82683432e-01,
        0.00000000e+00,  3.82683432e-01,  7.07106781e-01,  9.23879533e-01,
        1.00000000e+00,  9.23879533e-01,  7.07106781e-01,  3.82683432e-01])

---

<!-- 16 -->
### Broadcasting

Permite fazer operações vetoriais de maneira generalizada.

In [1]: x = np.array([1, 2, 3])

In [2]: x + 5
Out[2]: array([6, 7, 8])

---

<!-- 17 -->
### Broadcasting

In [1]: A
Out[1]: 
array([[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]])

In [2]: x
Out[2]: array([1, 2, 3])

In [3]: A+x
Out[3]: 
array([[ 2,  4,  6],
       [ 5,  7,  9],
       [ 8, 10, 12]])

---

### Representação interna das ndarrays no NumPy

- *data buffer* + metadados
- Podemos manipular os metadados sem alterar o buffer (`.transpose`, views, `.reshape`, slices...)
- ndarrays diferentes podem compartilhar os mesmos dados, e mudanças numa array podem ser visíveis na outra (uma array é um *view* da outra, e isso também pode funcionar para strings ou objetos que implementem as interfaces de array ou buffer).

----

<!-- .slide: style="font-size: 20px;" -->
<img src="https://i.imgur.com/bMdPxej.png" style="background:none; border:none; box-shadow:none; width:800px">

*Fonte: Harris et al., "Array Programming with NumPy", Nature volume 585, pages 357–362 (2020)*

----

Algumas operações criam *views*, outras criam cópias:

In [2]: x = np.arange(10)
In [3]: y = x[:5]
In [4]: y
Out[5]: array([0, 1, 2, 3, 4])

In [5]: y.base is x
Out[5]: True

In [6]: y = x[x>2]
In [7]: y
Out[7]: array([3, 4, 5, 6, 7, 8, 9])

In [8]: y.base is x
Out[8]: False

----

https://webcourses.ucf.edu/courses/1249560/pages/python-lists-vs-numpy-arrays-what-is-the-difference

---

<!-- 21 -->
### Interoperabilidade: Protocolos

- [buffer protocol](https://docs.python.org/3/c-api/buffer.html)

    ptr = (char *)buf + indices[0] * strides[0] 
                      + ... 
                      + indices[n-1] * strides[n-1];
    item = *((typeof(item) *)ptr);

- Da documentação:

    int PyObject_CheckBuffer(PyObject *obj)

*Retorna 1 if `obj` suporta a interface de buffer, 0 caso contrário.*

---

### Interoperabilidade: Protocolos

Protocolos servem como interfaces para os dados.

- `__array__`
- `__array_ufunc__`

import numpy as np
import pandas as pd

serie = pd.Series([1, 2, 3, 4])
np.exp(serie)  # serie não é uma ndarray!

---

<!-- 23 -->
### Outras implementações

- PyTorch
- Dask
- CuPy
- Tensorflow

----

### PyTorch


[Blog post sobre implementação do PyTorch](http://blog.ezyang.com/2019/05/pytorch-internals/)

----

### Dask


----

### CuPy


---

### Pontos importantes

- Arrays são úteis!
- Nem todas as arrays são iguais
- Interoperabilidade é o objetivo
- A escolha da estrutura de dados pode ter grande impacto na implementação

---

### Obrigada! :heart:

## `@melissawm`

---