11. Array 2D

A estrutura de dados Pilha é considerada linear pois possui apenas uma dimensão. Vimos que sua implementação pode ser realizada diretamente por meio de uma lista em Python, outra estrutura linear. Apesar dessa semelhança, os conceitos de pilha e lista são distintos, como podemos comprovar pelo comportamento oferecido por cada uma dessas estruturas.

A habilidade de resolver problemas computacionais é fundamentada por esses conceitos pois nos permite pensar usando ferramentas cognitivas mais poderosas, libertando-nos dos problemas de implementação. Em nossa aula anterior vimos como o uso do conceito de Pilha nos permitiu criar um algoritmo simples e elegante para o cálculo de expressões posfixas e como o uso de objetos facilita a implementação dessa solução.

Nessa aula vamos trabalhar com uma estrutura muito utilizada em computação científica, conhecida como array.

11.1. Objetivos de aprendizagem

Ao final dessa aula você será capaz de:

  • descrever o comportamento da estrutra de dados Array2D;
  • criar uma classe Array2D representada por uma lista 1D em Python;
  • realizar operações com arrays;
  • usar objetos do tipo Array2D em seus programas.

11.2. Introdução

Arrays são estruturas de dados semelhantes às listas do Python mas não tão flexíveis pois, em um array, todos os elementos devem ser de um mesmo tipo, tipicamente, de um mesmo tipo numérico como int ou float. Em contrapartida, o uso de arrays é muito mais eficiente e facilita a computação de grandes volumes de dados numéricos. Isso faz com que arrays sejam particularmente úteis em computação científica.

11.3. Array1D usando uma lista linear

Em operações numéricas com inteiros e reais o símbolo + é interpretado como soma, onde 2 + 2 resulta em 4. Você deve se recordar que esse mesmo símbolo é usado para concatenar duas strings em Python, onnde '2' + '2' resulta em '22', enquanto outros símbolos como *, / e - não tem significado quando usadas com strings.

Na Física, podemos representar algumas grandezas vetoriais como uma velocidade em 2D, por exemplo, por uma tupla \((v_x, v_y)\). Em certas circunstâncias é conveniente realizar operações numéricas elemento-a-elemento com essas grandezas. Assim, uma soma vetorial (1,2) + (3,4) resultaria em (4,6). Nesse caso, podemos estender esse mesmo comportamento para outros operadores como subtração e até multiplicação por um escalar.

O trecho de código abaixo cria uma classe Array1D representada usando uma lista linear em seu atributo dados. Essa estrutura pode ser usada, por exemplo, para representar um ponto n-dimensional capaz de realizar operações numéricas elemento-a-elemento.

Execute os testes passo-a-passo clicando no botão Forward > e observe que, ao construir um Array1D, o construtor pode receber um inteiro d ou uma lista. Caso seja um inteiro, um Array1D de tamanho d é criado. Nesse caso os dados do array são armazenados em um lista inicialmente com zeros. Caso receba uma lista, o construtor cria uma cópia da lista referenciada pelo atributo dados.

Exercício

A classe ilustra apenas como o operador + pode usado para somar elemento-a-elemento. Estenda a classe usando o Trinket abaixo para realizar as demais operações básicas de multiplicação, divisão e subtração.

A seguir, complemente o método __add__() para que, quando other for do tipo int ou float, o método retorne um novo Array1D com o valor de other somado elemento-a-elemennto.

O teste abaixo ilustra o comportamento esperado.

x = Array1D( [2, 3] )
y = x + 1.5
print(f"{y} deve ser [3.5, 4.5]"")

11.4. Array2D representada usando uma lista linear

Um array com duas dimensões pode ser entendido como uma matriz de tamanho \(m \times n\), onde \(m\) corresponde ao número de linhas e \(n\) ao número de colunas.

Uma forma de representar matrizes de 2 dimensões em Python é por meio de listas aninhadas, como ilustrado no seguinte trecho de código Python:

>>> m2d = [ [1, 2, 3], [4, 5, 6] ]
>>> print(m2d)
[[1, 2, 3], [4, 5, 6]]
>>> m2d[1][1] = -1
>>> print(m2d)
[[1, 2, 3], [4, -1, 6]]

Nesse caso, a lista aninhada m2d, que contém [[1, 2, 3], [4, 5, 6]], pode ser considerada uma matriz de dimensão (2,3), ou seja, com 2 linhas e 3 colunas, onde a primeira linha é representada pela lista linear [1, 2, 3] e a segunda linha por [4, 5, 6]. Observe que um elemento de m2d pode ser acessado usando dois pares de colchetes. O primeiro par define o índice da linha e o segundo define o índice da coluna.

Nesse exercício, ao invés de usar listas aninhadas para representar uma matriz, vamos começar a implementar a classe Array2D, cujos dados são armazenados em uma lista linear. Essa lista pode ser acessada pelo atributo de nome data (isso mesmo, data, não dados). Assim, usando o mesmo exemplo anterior, o conteúdo de data seria a lista [1, 2, 3, 4, 5, 6].

Nesse caso, a classe Array2D precisa de mais informação para saber qual a dimensão da matriz. Para isso a classe deve possuir um atributo de nome shape que armazena uma tupla com as dimensões da matriz que, nesse exemplo, corresponde a tupla (2, 3).

Vamos ver que é possível usar esses 2 atributos, data e shape, para trabalhar com matrizes 2D mas que internamente armazenam seus dados em uma lista 1D (linear). O primeiro problema que precisamos resolver é como acessar um elemento da lista data a partir de um par de coordenadas (lin, col). No exemplo, o elemento na posição (0, 1) é 2 e na posição (1, 2) é 6.

Felizmente a solução é relativamente simples. Como sabemos o tamanho de cada linha, que corresponde ao número de colunas da matriz armazenada na tupla shape, para acessar o elemento na coordenada (lin, col), basta converter a coordenada para o índice shape[1] * lin + col da lista data, ou seja, data[ shape[1] * lin + col ].

Por fim, inclusive para treinar o uso de tuplas, vamos usar tuplas também para acessar os elementos de um objeto Array2D. Ou seja, se a é um objeto Array2D, queremos usar a notação a[1, 2] (tupla entre colchetes) ao invés de a[1][2] (pares de colchetes) para acessar os elementos de um Array2D. As vantagens dessa notação serão reveladas em nossas próximas aulas.

11.5. Comportamento de um Array2D

Antes de implementar a classe, devemos definir como desejamos usar objetos desse tipo, ou seja, como esses objetos devem se comportar. A partir desse comportamento você deve implementar os métodos e atributos que tornem esse comportamento possível. Para entender o comportamento básico desejado, estude a seguinte função main() e verifique em seguida as saídas esperadas para cada chamada de print().

def main():
    print("Testes da classe Array2D\n")

    a = Array2D( (2,3), 3) # cria Array2D com valor inicial 3
    print(f'teste 1: Criação do Array2D a:')
    print(a)
    print(f'shape: {a.shape}')
    print(f'size : {a.size}')
    print(f'data : {a.data}')
    print()

    b = Array2D( (2,3), 1.7)   # criar Array2D com valor inicial 7
    print(f'teste 2: Criação do Array2D b:')
    print(b)
    print(f'shape: {b.shape}')
    print(f'size : {b.size}')
    print(f'data : {b.data}')
    print()

    print(f'teste 3: a[0,1] + 100 é: {a[0,1] + 100}') # acesso direto usando tupla: use o método __getitem__
    print()

    a[1,1] = -1    # atribuição usando tupla: use o método __setitem__
    print(f'teste 4: Array2D a:')
    print(a)

A saída desse programa, resultante das chamadas de print(), definem a parte do comportamento de objetos da classe Array2D que você deve implementar.

Testes da classe Array2D

teste 1: Criação do Array2D a:
3 3 3
3 3 3
shape: (2, 3)
size : 6
data : [3, 3, 3, 3, 3, 3]

teste 2: Criação do Array2D b:
1.7 1.7 1.7
1.7 1.7 1.7
shape: (2, 3)
size : 6
data : [1.7, 1.7, 1.7, 1.7, 1.7, 1.7]

teste 3: a[0,1] + 100 é: 103

teste 4: Array2D a:
3 3 3
3 -1 3

11.6. Exercícios

  1. Escreva uma classe Array2D que implemente essa parte do comportamento definido anteriormente. Você pode estender a classe com outros atributos e métodos, caso desejar, desde que não entrem em conflito com esses comportamentos.

    Dica: os métodos especiais __getitem__() e __setitem__() permitem o uso de tuplas para acessar o valor e atribuir um valor a um Array2D usando tuplas para indicar os elementos. Procure entender o seu funcionamento a partir do docstring desses métodos no esqueleto abaixo e discuta suas dúvidas no fórum de discussão.

11.7. Onde estamos e para onde vamos?

Arrays são estruturas muito utilizadas em computação científica. Nessa aula começamos a entender sua estrutura para evidenciar, nas próximas aulas, suas diferenças com relação as matrizes em Python representadas na forma de listas aninhadas. Nossa classe Array2D ilustra também que pode haver uma grande diferença entre um conceito (abstração de um tipo 2D) e sua implementação interna (lista linear 1D).

A estrutura Array2D que começamos a desenvolver tem grande semelhança com o tipo ndarray oferecido pelo módulo NumPy. Esse módulo é um módulo do Python muito usado em computação científica e buscamos também facilitar o uso desse módulo introduzindo primeiramente a classe Array2D.