Teste Final - Pergunta 4

Era pedido um programa em que se somam dois vectores esparsos representados através de dicionários. Um vector esparso é aquele em que a esmagadora maioria dos seus elementos é zero. Usando um dicionário apenas representamos explicitamente os casos diferentes de zero, poupando muito espaço e salvando tempo nas operações. Por exemplo, o vector x = (0,0,0,2,0,0,0,5,0,0) pode ser representado, com economia, pelo dicionário d ={3:2, 7:5, ‘len’:10}. Notar a referência ao comprimento, um parâmetro importante da representação.

Das respostas dadas no teste, quase todos(as) optaram por transformar os dois vectores representados por dicionários em listas, seguido da soma das duas listas, par finalmente depois construir o dicionário resultado. Se pensarmos um pouco, isto é tudo menos boa programação, porque precisamente destrói o que se ganha em usar uma representação baseada em dicionários: espaço e tempo! Mesmo assim, as soluções apresentadas têm muitas deficiências (por exemplo, recurso errado a isdigit() ou a type(x) == int, em vez de isinstance(x,int)). Eis uma solução possível para essa abordagem.

view sourceprint?

01.def soma_vec_esparso_b(vec_1, vec_2):

02.    comp = vec_1['len']

03.    # Converte dicionários em listas

04.    list_1 = [vec_1.get(i,0) for  i in range(comp) ]

05.    list_2 = [vec_2.get(i,0) for  i in range(comp)]

06.    # soma listas

07.    list = [list_1[i] + list_2[i] for i in range(comp)]

08.    # constrói dicionário

09.    dic = {i: list[i] for i in range(comp) if list[i] > 0}

10.    dic['len'] = comp

11.    return dic

Fazemos uso de listas e dicionários por compreensão, que nos permite um código curto.Claro que podem ser substituídas por ciclos normais.

Então qual seria a solução baseada em dicionários? Como vão ver, simples e curta.

view sourceprint?

1.def soma_vec_esparso(vec_1, vec_2):

2.    vec_3 = {}

3.    vec_3.update(vec_2)

4.    for ch1,val1 in vec_1.items():

5.        if ch1 != 'len': # isinstance(ch1,int)

6.            vec_3[ch1] = val1 + vec_3.get(ch1,0)

7.    return vec_3

A ideia é começar por copiar um dos dicionários para a solução usando o método update ( isso inclui a chave ‘len’), e depois verificar os elementos relevantes (isto é, diferentes de ‘len’) do outro vector efectuando a soma. Em comentário, mostramos que podemos fazer o teste para saber se é ‘len’ ou um número de um modo mais geral.