Fatos interessantes sobre arrays, matrizes e tensores: o número 3 vai te surpreender
slides: https://hackmd.io/@melissawm/rkXK894Ad
O que são arrays?
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.
Elementos são acessíveis de forma rápida
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.
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, SO, código fonte)
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;
Arrays
-
Arrays contém elementos de tamanho fixo, o que permite guardá-los em um bloco contíguo de memória: (Link)
-
Se
arré uma array com inteiros, earr[0]está armazenado no endereçox, entãoarr[i]está armazenado no endereçox+i*sizeof(int)
Operações matemáticas
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)
NumPy: a base da computação científica no Python
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
Fonte: Harris et al., "Array Programming with NumPy", Nature volume 585, pages 357–362 (2020)
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)
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)
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
Fonte: Harris et al., "Array Programming with NumPy", Nature volume 585, pages 357–362 (2020)
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)
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
(O que são essas dimensões?)
https://www.oreilly.com/library/view/elegant-scipy/9781491922927/ch01.html
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])
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])
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])
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).
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
Interoperabilidade: Protocolos
-
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
objsuporta 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!
Outras implementações
- PyTorch
- Dask
- CuPy
- Tensorflow
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
