changed 2 years ago  
Linked with GitHub

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.

  • Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    Elementos são acessíveis de forma rápida
  • Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    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, e arr[0] está armazenado no endereço x, então arr[i] está armazenado no endereço x+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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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?)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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).
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Interoperabilidade: Protocolos

  • buffer protocol

    ​​​​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!

Outras implementações

  • PyTorch
  • Dask
  • CuPy
  • Tensorflow

PyTorch

Blog post sobre implementação do PyTorch

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!
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

@melissawm

Select a repo