domingo, 22 de novembro de 2015

Listas por Compreensão (II)

Estamos habituados em matemática a definir um conjunto de duas formas distintas: por extensão, quando indicamos os seus elementos, ou por intenção, quando indicamos uma regra que nos permite identificar os elementos do conjunto. Em Python podemos descrever uma lista de elementos também destas duas formas. À segunda chamamos listas por compreensão. As listas por compreensão estão ligadas à resolução de problemas que obedecem a um certo padrão. Por exemplo, admitamos que queremos um programa que gere números inteiros, aleatoriamente, entre um certo intervalo. Uma solução simples seria:
import random

def gera_numeros(n,inf, sup):
     res = []
     for i in range(n):
          num = random.randint(inf,sup)
          res.append(num)
     return res
Este padrão em que temos um acumulador onde vão sendo guardados elementos através de um processo repetitivo, pode ser implementado também por recurso a listas por compreensão:
def gera_numeros_b(n,inf, sup):
     res = [ random.randint(inf,sup) for i in range(n)]
     return res
Como se percebe a sintaxe envolve, nesta versão básica, os indicadores de lista (“[“ e “]”), seguido de uma expressão que nos permite gerar os elementos da lista, seguido do processo repetitivo (ciclo for). Podemos aplicar este modelo em diferentes situações.

Elevar os números de aula lista ao quadrado:
def quadrados(lista):
     return [elem**2 for elem in lista]
Produto escalar de dois vectores:
def escalar_comp(x,y):
     """ Produto escalar de dois vectores."""
     return sum([x[i]*y[i] for i in range(len(x))])
A lista por compreensão gera os produtos e a função sum faz a soma.
Somas parciais (percorrer a lista e gerar uma nova list em que na posição i é colocada a soma dos números da primeira lista desde o início até (inclusive) i):
def somas_parciais(lista):
     """ somas de 1 a i."""
     return [sum(lista[:i+1]) for i in range(len(lista))]
Podemos dizer que, de um modo geral ,este padrão obedece ao modelo:
def my_map(func, lista):
     return [func(elem) for elem in lista]
O leitor poderá pensar que não é muito poderoso este modo de programar. Por exemplo, não podemos filtrar elementos a incluir na lista em função de um dado critério. Mas as listas por compreensão têm uma sintaxe mais completa. Admitamos que queremos construir uma lista a partir de outra, retendo apenas os seus elementos positivos:
def filtro_nega(lista):
     return [ elem for elem in lista if elem > 0]
  
Agora temos a expressão, seguida do ciclo for, seguida do if. Outros exemplos: Lista dos índices das ocorrências de um dado elemento:
def ocorre(elem, lista):
     """ localizaçoes das ocorrências de elem na lista."""
     return [ i for i in range(len(lista)) if lista[i] == elem]
Conta o número de ocorrências:
def conta(elem, lista):
     """Quantas ocorrências de elem na lista."""
     return sum([ 1 for e in lista if e == elem])
Parece melhor. Mas e problemas em que existem mais do que um ciclo? Por exemplo, quando pretendemos construir a lista de pares ordenados formados com elementos de outras duas listas fazemos:
def combina(a,b):
     """ pares ordenados com elementos de a e de b."""
     res = []
     for elem_a in a:
          for elem_b in b:
               res.append((elem_a,elem_b))
     return res
Mas também esta situação está contemplada:
def combina_b(a,b):
     return [(elem_a,elem_b) for elem_a in a for elem_b in b]
Como se vê a sintaxe é dada pela expressão, seguida do ciclo mais externo, seguida do ciclo mais interno. No ciclo interno podemos referir objetos do ciclo externo.

Um exemplo simples consiste em obter a lista dos elementos de uma lista de listas:
def aplana(lista_listas):
     """Aplanar uma lista de listaas."""
     return [elem for linha in lista_listas for elem in linha  ]
Podemos ainda complicar mais as coisas? Podemos! Numa lista por compreensão no lugar da expressão podemos ter … uma lista por compreensão!!! Vejamos como esse facto nos permite obter a transposta de uma matriz de modo simples:
def transposta_b(matriz):
     """transposta de uma matriz."""
     return [ [matriz[j][i] for j in range(len(matriz))] for i in range(len(matriz[0]))]
Agora a expressão é uma lista por compreensão e deve ser considerada como estando no interior do ciclo for que aparece a seguir! Podemos usar este código para escrever um programa que roda 90 graus no sentido dos ponteiros do relógio uma imagem a preto e branco representada por uma lista de listas de 1s e 0s.
def roda_90(imagem):
     """ Rodar 90 graus uma imagem."""
     img_trans = transposta_b(matriz)
     nova_imagem = [linha[::-1]  for linha in img_trans]
     return nova_imagem
Estaremos limitados a dois ciclos? Mais uma vez a resposta é negativa. Segue-se um exemplo, que mostra como se podem obter três inteiros que verificam a condição do Teorema de Pitágoras:
def pitagoras(n):
     return [(x,y,z) for x in range(1,n) for y in range(1,n) for z in range(1,n) if x**2 + y**2 == z**2]
Executando o programa verificamos a ocorrência de repetições. Mas podemos resolver facilmente esse problema:
def pitagoras_b(n):
     return [(x,y,z) for x in range(1,n) for y in range(x,n) for z in range(y,n) if x**2 + y**2 == z**2]
E se em vez da potência ser 2 fosse outro inteiro maior do que 2? Estamos perante o chamado último Teorema de Fermat. Mas não aconselho a tentar prová-lo deste modo…
def fermat(n,k):
     return [(x,y,z) for x in range(1,n) for y in range(x,n) for z in range(y,n) if x**k + y**k == z**k]
O leitor continua a pensar que tudo isto é muito limitado. Vamos então a um exemplo em que a expressão é um pouco mais complexa, pois inclui uma condicional. Neste caso podemos implementar uma função em que todos os elementos de uma lista de determinado valor são substituídos por outro elemento:
def my_replace(novo, velho,lista):
     return [novo if elem == velho else elem for elem in lista]
Pois é, estamos perante um novo tipo de expressão: objecto if condição else objecto. Vamos usar esta ideia para obter o negativo de uma imagem a preto e branco:
def negativo_img(imagem):
     return [[ 0 if elem == 1 else 1  for elem in linha] for linha in imagem]
Para terminar, vamos deixá-lo com um exemplo que nos permite calcular uma lista de números primos, recorrendo ao algoritmo conhecido por Sieve of Erathostenes.
def primos(n):
     up = int(math.sqrt(n))
     no_primes = [j for i in range(2,up+1) for j in range(i**2,n+1,i)]
     return [ x for x in range(2,n+1) if x not in no_primes]
Interessante, não concorda? Talvez. Chegados aqui coloca-se a questão de saber se é possível realizar com listas por compreensão coisas que não se podem fazer de outro modo. E resposta é um redondo não. Então porquê usar? Se olharmos para os exemplos anteriores é claro que há medida que queremos fazer coisas mais complexas a legibilidade do programa diminui. No entanto existe uma razão forte: o uso de listas por compreensão torna os programas muito mais rápidos! Então o nosso conselho final é: use as listas por compreensão sempre que o tempo de execução for crítico ou, não sendo crítico, sempre que a legibilidade do programa não seja comprometida.

Sem comentários:

Enviar um comentário