Dicionários, álgebra e outras coisas misteriosas...

O princípio da economia é cada vez mais fundamental na nossa vida. Em programação, isso significa, entre outras coisas, poupar nos recursos da máquina, por exemplo na memória. Para conseguir essa poupança recorre-se a representações dos dados que sejam económicas passando para os algoritmos a tarefa de manipular essas representações. Que mecanismos de representação de dados temos em Python? Bom, para dados não numéricos, as listas e os dicionários. Parece pouco, mas na realidade estes dois tipos de contentores resolvem, quase sempre de modo elegante, a questão da representação. Vejamos um exemplo.


Suponhamos que queremos manipular vectores esparsos. Estes vectores caracterizam-se por ter quase todas as posições a 0. Como representar? Uma solução interessante é usar um dicionário em que a chave é o índice do vector e, o valor, o valor nessa posição. Assim:


O vector: [2,0,0,0,0,3,0,0,0,4,0,0,0] origina o dicionário = {0:2,5:3,9:4}


Agora temos que resolver a questão das operações. Escolhemos duas: soma e produto escalar. Na soma, somam-se os valores com o mesmo índice. No produto, multiplicam-se os valores nas mesmas posições e, no final, somam-se esses produtos. Eis o resultado:

def soma_vec(v1,v2):
    """ soma dois vectores esparsos, organizados como dicionários.
    vec = [2,0,0,0,0,3,0,0,0,4,0,0,0] --> {0:2,5:3,9:4}
    """
    v = v1.copy()
    for ch in v2.keys():
        v[ch] = v.get(ch,0) + v2[ch]
    return v

def dot_produto(v1,v2):
    """ Produto escalar  dois vectores organizados como dicionários.
    vec = [2,0,0,0,0,3,0,0,0,4,0,0,0] --> {0:2,5:3,9:4}
    """
    v = dict()
    for ch in v2:
        if ch in v1:
            v[ch] = v1[ch] * v2[ch]
    prod = sum(v.values())
    return prod

Notas. No caso da soma, criámos uma cópia de um dos dicionários originais. Porquê? No caso do produto, usámos o construtor do tipo dict(). O acesso às chaves pode ser feito, num ciclo, de dois modos distintos, for chave in dicio ou for chave in dicio.keys().


Uma referência final para os que usam Python 3.0 ou superior. A partir desta versão foi introduzido o conceito de vista. As operações dic.key(), dic.items() e dic.values() devolvem um iterável com características acrescidas: todas as mudanças dinâmicas que ocorrem no dicionário são imediatamente reflectidas na vista e, existem novas operações, do tipo das operações sobre conjuntos, que podem ser usadas com as vistas (intersecção, união, diferença, diferença simétrica). Usando essas novas potencialidades o nosso produto escalar pode ser implementado assim:

def dot_produto_b(v1,v2):
    """ Produto escalar  dois vectores organizados como dicionários.
    vec = [2,0,0,0,0,3,0,0,0,4,0,0,0] --> {0:2,5:3,9:4}
    Funciona apenas em Python 3.0 ou superior!
    """
    v = dict()
    for ch in (v1.keys() & v2.keys()):
        v[ch] = v1[ch] * v2[ch]
    prod = sum(v.values())
    return prod