Modelagem de Dados Dependências Transitivas Exercíco

Prévia do material em texto

Dependências Transitivas
Vamos escrever algum código que calcula como dependências propagar entre as coisas tais como aulas de um programa.
Código altamente acoplado é o código onde as dependências entre as coisas são densos, muitas coisas dependem de outras coisas. Esse tipo de programa é difícil de entender, difícil de manter, e tende a ser frágil, quebra facilmente quando as coisas mudam.
Há muitos tipos diferentes de acoplamento no código. Um dos mais fáceis de trabalhar com programaticamente é acoplamento estático, onde nós estamos preocupados com as relações entre pedaços de código-fonte. Simplesmente, podemos dizer que a classe A é estaticamente acoplado a classe B, se o compilador precisa a definição de B para compilar
Em muitas linguagens, dependências estáticas pode ser determinada por análise de código fonte. Ferramentas como MakeDepend (para programas em C) e JDepend (para Java) podem procurar dependências explícitas na fonte e listá-los para fora.
Uma das coisas insidiosas sobre dependências é que eles são transitivos:
	Se A depende de B e B depende de C, então A também depende C.
Então, vamos escrever algum código que calcula o conjunto completo de dependências para um grupo de itens. O código toma como entrada um conjunto de linhas onde o primeiro símbolo é o nome de um item. Os restantes símbolos são os nomes das coisas que este primeiro item depende. Dada a sequência de entrada, sabemos que A depende diretamente B e C, B depende de C e E, e assim por diante. 
 A B C
 B C E
 C G
 D A F
 E F
 F H
O programa deve usar esses dados para calcular o conjunto completo de dependências. Por exemplo, olhando para B, vemos que depende diretamente em C e E. C, por sua vez depende de G, E baseia-se em F, e F se baseia em H. Isto significa que B, em última análise depende de C, E, F, G, e H de fato, o conjunto completo de dependências para o exemplo anterior é: 
 A B C E F G H
 B C E F G H
 C G
 D A B C E F G H
 E F H
 F H
Vamos expressar isso usando testes de unidade. O código a seguir supõe que a nossa calculadora de dependência é uma classe com um método add_direct () para adicionar as dependências diretas para um item, e um método dependencies_for () para retornar a lista completa de dependências para um item. O código usa% de Ruby w {...} construir, que constrói uma matriz de sequências de seu argumento.
def test_basic
 dep = Dependencies.new
 dep.add_direct('A', %w{ B C })
 dep.add_direct('B', %w{ C E })
 dep.add_direct('C', %w{ G })
 dep.add_direct('D', %w{ A F })
 dep.add_direct('E', %w{ F })
 dep.add_direct('F', %w{ H })
 assert_equal(%w{B C E F G H}, dep.dependencies_for('A'))
 assert_equal(%w{C E F G H}, dep.dependencies_for('B'))
 assert_equal(%w{G}, dep.dependencies_for('C'))
 assert_equal(%w{A B C E F G H}, dep.dependencies_for('D'))
 assert_equal(%w{F H}, dep.dependencies_for('E'))
 assert_equal(%w{H}, dep.dependencies_for('F'))
end
Pare de ler agora, e começar a programar. Uma vez que você tem seu trabalho código, tente alimentá-lo as seguintes dependências. 
 A B
 B C
 C A
Será que funciona corretamente? Se não, pergunte a si mesmo é esta é uma condição que você deveria ter considerado durante o teste.
Assim que tiver o seu código de trabalho com todos os vários casos de teste que você pode imaginar, vamos pensar por um minuto sobre o desempenho. Dizer que estávamos usando este código para encontrar todas as relações entre os habitantes do Reino Unido. Como seria o seu código executar com 55-60 milhões de itens?