Fortemente influenciado por este artigo do Leandro Proença https://dev.to/leandronsp/how-to-reduce-the-time-complexity-of-nested-loops-1lkd

Leia mais detalhes na thread que o Leandro escreveu no Twitter https://twitter.com/leandronsp/status/1467259424469364745

Temos que preencher uma tabela com o nome de uma transportadora, por motivos de regras de negócio. E agora, como proceder?

Definindo o problema um pouco mais rigidamente

Temos uma tabela na base de dados. Essa tabela contém dados sobre precificação de frete e um dos dados que serve para fazer esse cálculo é a transportadora que irá prover o serviço de frete. Essa informação é opcional.

Uma das modelagens possíveis é usar um esquema relacional e mencionar a transportadora numa chave estrangeira. Se adotarmos um esquema de integridade ocasional, precisamos assumir que a chave estrangeira aponta para algo que possivelmente não exista.

Vamos chamar a estrutura que lida com a precificação de PRECIFICACAO_FRETE. Ele tem uma chave estrangeira para transportadora chamada TRANSPORTADORA, para a tabela TRANSPORTADORA. A tabela TRANSPORTADORA de relevante para o caso de hoje contém a colunas CODIGO e NOME.

Modelando objetos

Temos algumas variações possíveis para modelar esses objetos. Vamos começar por Transportadora.

Nesse momento, não iremos precisar alterar em nada os campos de Transportadora, então precisamos ter acesso somente leitura para código e nome. Usando tradicionais getters, poderíamos colocar assim:

public class Transportadora {
	// não temos restrições para construtor, então ele está omitido
	// não assuma, entretanto, que precisa ser construtor padrão

	private int codigo;
	private String nome;

	public int getCodigo() {
		return codigo;
	}

	public String getNome() {
		return nome;
	}
}

Note que aqui estou assumindo que o tipo de dados dentro da coluna TRANSPORTADORA.CODIGO é um inteiro tradicional de 4 bytes, representável por um int do Java.

E precisamos modelar o objeto PrecificacaoFrete. A única informação que temos sobre ele até o momento é que ele pode ou não ter uma transportadora. Então a referência (seja ela direta ou indireta) precisa assumir que irá ter o valor nulo. Eu vejo algumas alternativas para isso.

A primeira é uma referência direta a transportadora:

public class PrecificacaoFrete_direta {
	// resto da classe omitida

	private Transportadora transportadora;

	public Transportadora getTransportadora() {
		return transportadora;
	}
}

Ou então uma referência a algo que pode ser tratado como transportadora, porém independente da implementação real por trás:

public class PrecificacaoFrete_ITransportadora {
	// resto da classe omitida

	private ITransportadora transportadora;

	public ITransportadora getTransportadora() {
		return transportadora;
	}
}

Note que, para isso funcionar corretamente, precisaríamos que Transportadora implementasse a interface ITransportadora e que essa interface tivesse alguma API nela definida. O caso específico que estamos tratando uma interface de marcação (como o java.io.Serializable) não seria a mais adequada.

E também tem o método mais tosco, guardar a referência ao código, e apenas isso:

public class PrecificacaoFrete_codigo {
	// resto da classe omitida

	private Integer transportadora;

	public Integer getTransportadora() {
		return transportadora;
	}
}

Como a referência inexistente se aplica, uso o tipo Integer para ter acesso ao null.

Foi mais simples para nós usar esse último padrão, em que a PrecificacaoFrete armazenasse apenas a referência da transportadoravai código. Um dos motivos pelo qual isso foi escolhido foi um mal entendimento com o MyBatis que não retornava referência nula quando existia um null em PRECIFICACAO_FRETE.TRANSPORTADORA, e também tratar o caso de transportadora que foi removida. Isso é algo passível de acontecer pois esse é um sistema de integridade ocasional, como foi definido no começo.

Outros fatores que colaboraram para se usar esse tipo de construção é porque a transportadora não tem nenhuma propriedade que, naquele momento específico, fosse útil para o cadastro de PRECIFICACAO_FRETE.

O resgate do objeto de PrecificacaoFrete é direto ao ponto: cada linha em PRECIFICACAO_FRETE vira um objeto e no campo transportadora eu coloco o valor da coluna TRANSPORTADORA. Similarmente com o objeto Transportadora.

Usando os objetos

No primeiro momento, vou falar sobre o uso dele no cadastro. O usuário precisa selecionar uma transportadora dentro da lista de transportadoras disponíveis. Ao fazer isso, o sistema chama algo que altera o estado do objeto PrecificacaoFrete que ele está trabalhando. Vamos supor que seja PrecificacaoFrete precificacaoFrete:

void onChangeTranportadora(Transportadora novaTransportadora) {
	if (novaTransportadora != null) {
		this.precificacaoFrete.setTransportadora(novaTransportadora.getCodigo());
	} else {
		this.precificacaoFrete.setTransportadora(null);
	}
}

Ok, so far, so good. Mas tem um momento que precisamos mostrar esses dados de modo tabulado. Como proceder? Se considerarmos que cada coluna terá seu próprio trecho de código que mostra como exibir (Function<PrecificacaoFrete, String> para cada coluna da tabela), poderíamos maltratar o usuário assim: o usuário assim:

precificacaoFrete -> Optional.of(precificacaoFrete)
		.map(PrecificacaoFrete::getTransportadora)
		.map(Object::toString)
		.orElse("")

Assim eu exibo o código da transportadora. Funciona? Bem, sim, mas é maltratar o usuário. Não é uma experiência de uso muito adequada para o usuário mostrar o código da transportadora, o ideal seria mostrar o nome dela. Então, vamos agradar o usuário? Precisamos pegar uma função nomeTransp que transforme código da transportadora em seu respectivo nome. Bem, vamos assumir que existe essa função Function<Integer, String> nomeTransp:

precificacaoFrete -> Optional.of(precificacaoFrete)
		.map(PrecificacaoFrete::getTransportadora)
		.map(nomeTransp)
		.orElse("")

Até aqui ótimo. Agora, precisamos definir nomeTransp. E aqui iniciamos a matança de dragões.

Jeito naïve de obter o nome das transportadoras

A maneira mais ingênua de obter o nome das transportadoras seria fazer uma pergunta ao banco de dados qual o nome da transportadora X:

nomeTransp = codTransp -> {
	Transportadora t = transportadoraMapper.resgataTransportadora(codTransp);
	if (t != null) {
		return t.getNome();
	} else {
		return "Transportadora " + codTransp + " sem cadastro";
	}
};

Bem, parece razoável, não é? Mas, e se eu disser que isso implica fazer O(n) consultas aos banco de dados? Caímos no clássico problema n + 1. Sem garantir o bom funcionamento de transportadoraMapper.resgataTransportadora para fazer alguma espécie de cache de dados (talvez não esteja configurado), isso é catastrófico. Na minha situação, isso é proibitivo, pois o código da view no GWT executa no lado JavaScript e eu sou proibido de fazer consultas síncronas ao servidor, então precisaria de algum jeito de tornar isso assíncrono, mas isso são outros detalhes.

Ok, e como evitar o n + 1? Que tal carregar todas as transportadoras numa lista transportadoras?

Pois bem, com essa pré-condição de que temos todas as transportadoras carregadas, o código seria o seguinte:

nomeTransp = codTransp -> transportadoras.stream()
		.filter(t -> t.getCodigo() == codTransp)
		.findAny()
		.orElseGet(() -> "Transportadora " + codTransp + " sem cadastro");

Pois bem, fim de história?

O dragão da complexidade

Óbvio que não. Aqui temos que verificar o quanto de esforço é dedicado a buscar essa informação.

Falei no começo que transportadoras é uma lista, portanto posso assumir que é um List<Transportadora>. Isso ainda implica que ele terá um comportamento de complexidade distinto se a implementação for contígua em memória (como ArrayList) ou como lista ligada (como LinkedList). Porém talvez seja só um vício de linguagem meu e transportadoras poderia ser qualquer Collection<Transportadora>, como Set<Transportadora>. Por hora, vou ignorar esses detalhes e assumir que cada acesso a elemento custa algo de modo constante $O(1)$.

Em todas essas estruturas citadas, não está sendo feito nenhum acesso esperto, mas sim uma iteração comparando o elemento passado com um predicado arbitrário. Isso impede que algo esperto seja feito. Então, caso não exista o elemento na lista, será necessário passar o predicado por todos os elementos da lista. Podemos assumir que o predicado roda de modo oracular (na real, como vemos o código dele, ele é de fato $O(1)$).

Então, de modo geral:

• precisamos acessar $O(n)$ elementos
• acessar cada elemento custa $O(1)$
• testar cada elemento custa $O(1)$

Com isso temos que, para achar o nome de uma transportadora, fazemos uma operação em tempo linear $O(n)$. Bacana, né?

Pois bem… acessar o nome da transportadora é uma operação auxiliar dentro da operação principal de montar a tabela. Vamos por hora assumir que essa tabela só tenha essa única coluna. Portanto, vamos precisar fazer operações para $\Theta(m)$ precificações de frete. Para cada uma dessas operações, será realizada uma operação $O(n)$. Então, temos que teremos ao todo $O(m\times n)$ operações para rodar o povoamento de elementos.

Espera-se ter muito mais elementos de PrecificacaoFrete do que de Transportadora, então podemos dizer que $m \gg n$. Com isso, temos que $O(m\times n) > O(n\times n) = O(n^2)$. Bem, isso mesmo, temos um algoritmo quadrático $O(n^2)$ aqui.

Mas, será que essa complexidade é irredutível mesmo?

Entra São Jorge

O que queremos é acessar a partir de um código uma transportadora. Sabemos que, devido a natureza desse dado, o código da transportadora é único. Portanto, o mapeamento transportadora e código é uma bijeção. Então, com isso, podemos montar um mapa, não é? Vamos chamar esse mapa de cod2transp, ele é do tipo Map<Integer, Transportadora> (posso usar HashMap para operações em média $O(1)$ de resgate porém $O(n)$ em casos degenerados, ou TreeSet que fornece acesso em $O(\log(n))$).

A partir desse mapeamento (ainda iremos montá-lo, se acalme), conseguimos definir nomeTransp de modo bem mais simples:

nomeTransp = codTransp -> {
	Transportadora t = cod2transp.get(codTransp);
	if (t != null) {
		return t.getNome();
	} else {
		return "Transportadora " + codTransp + " sem cadastro";
	}
}

E, pronto. Como estamos usando um Map, podemos assumir sem perder generalidade que é uma operação esperta, com custo médio de $O(1)$ para acessar. Logo, com isso, temos que a complexidade total que na estratégia naïve era de $O(n^2)$ para $O(m)$. Porque ainda precisamos percorrer os elementos do tipo PrecificacaoFrete. São $\Theta(m)$ elementos e precisamos percorrer todos eles, porém agora a operação auxiliar custa apenas $O(1)$, o que não altera o valor geral da complexidade. Estamos lidando com complexidade agora linear.

Mas, isso não é a história toda, não é mesmo? Como temos $\Theta(n)$ transportadoras, armazenar em um mapa essas transportadoras todas ocupará no mínimo $\Theta(n)$ de memória extra, porém com mais meta-dados do que se tinha anteriormente (considere como sendo o fator constante multiplicando a função maior). Se for necessário por algum motivo manter a lista de transportadoras, isso significa que precisaremos de mais do que o dobro de memória extra do que a estratégia ingênua. Além disso, precisamos de mais código para manter e também computar minimamente o tempo que se passa criando o mapa dentro das equações.

Para criar o mapa, podemos ser simples e delegar o trabalho a um Collector. De todos os disponíveis, o melhor para o nosso caso é o Collectors.toMap(keyMapper, valueMapper).

cod2transp = transportadoras.stream()
		.collect(
			Collectors.toMap(
				Transportadora::getCodigo,
				Function.identity()
			)
		);

Se quiser algo mais old school:

cod2transp = new HashMap<>();

for (Transportadora t: transportadoras) {
	cod2transp.put(t.getCodigo, t);
}

Ambas as alternativas usam $\Theta(n)$ operações para construir o mapa. Elas não são estritamente equivalentes, entretanto, porque o Collectors.toMap usado não aceita duplicações de chave. É possível, entretanto, tornar essas implementações “equivalentes” se usarmos a seguinte função de merge:

cod2transp = transportadoras.stream()
		.collect(
			Collectors.toMap(
				Transportadora::getCodigo,
				Function.identity(),
				(__, a) -> a
			)
		);

Pondo mais dragões nas lanças

Eu peguei um exemplo simplificado logo no começo do artigo, propositalmente. Mas, se levar em consideração mais fatores, a coisa começa a brilhar.

De início, coloquei como fator que impacta na precificação do frete apenas a transportadora. Mas na aplicação onde isso reside existem diversas outras informações que são tratadas de maneira bem semelhante. São elas (citando novamente a transportadora só por questões de completude):

• loja vendedora
• tipo do frete
• transportadora
• comprador
• praça do comprador
• região em que se situa a praça

Tudo com integridade ocasional, pois esses dados são importados de um sistema externo (inclusive quando ele é removido da origem, essa remoção deve ser propagada para o lado da aplicação para evitar problemas maiores no cadastro).

Cada peça dessas adiciona, para cada linha de precificação de frete, uma busca separada pelo nome do elemento. A complexidade ao todo não sai da quadrática, entretanto, mas o fator multiplicando o fator quadrático aumenta.

Além disso, fatores auxiliares levam a escolha da preferência por usar referência indireta aos objetos no lugar da referência propriamente dita de objetos. Imagina resgatar, em uma consulta, os elementos da precificação e dos 6 tipos citados acima. Se for considerar apenas chave/nome, na tupla de retorno seriam mais 6 colunas além das de referência ao código, isso envolvendo uma junção de 7 tabelas. Também tem a questão de que há um desentendimento com o MyBatis, que não conseguimos fazer a referência nula ainda. Ou, se não for resgatar em uma única consulta, temos o problema n+1 nas mãos.