Estou com um problema em que preciso comparar Strings e definir sua proximidade.
O problema é que tenho uma lista com 21 mil registros e preciso comparar todos, um com o outro, o que daria uma complexidade quadrática e no total seriam 21mil*21mil comparações, o que não leva pouco tempo. Preciso fazer isso de modo mais rápido e prático.
Eu estou inserindo esses registros num banco de dados para facilitar a manipulação mas faço algumas alterações e filtros nele através da programação em Java, antes de inserir. Abaixo segue um trecho do código:
for (int i = 0; i < limite; i++) {
for (int j = 0; j < limite; j++) {
if (searchForItem(listaoComp, listao.get(j).id, listao.get(i).id)) {
naoInsere++;
} else {
insere++;
listaoComp.add(new Comparacao(listao.get(i).id, listao.get(j).id));
}
total++;
}
}
Basicamente, estou fazendo a verificação quadrática. Como isso acontece, por exemplo, estou comparando os registros (0,1) e (1,0) e inserindo eles na lista. No meu caso, registros assim significam a mesma coisa e não precisam estar os dois na lista então o searchForItem verifica antes de inserir (1,0) se já existe (0,1) na lista. O searchForItem faz isso. Esse método vai ficando pior ao longo da execução do código pois a lista vai aumentando consideravelmente.
Para contextualiza-los, tenho uma lista de princípios ativos de remédios (id e nome) que formam a classe Princípio, a qual o listão é uma lista deste objeto.
List<Principio> listao = new ArrayList<Principio>();
Já a listaoComp é uma lista de Comparacao.
Na classe Comparacao, guardo os ids dos principios ativos comparados e sua proximidade, por exemplo
new Comparacao(1, 2, 98.5);
Ah, e a variável limite dentro dos For's indicam o tamanho do listao.
int limite = listao.size()
Como dito anteriormente, estou comparando todos os ids duas vezes, por exemplo 0 - 0 / 0 - 1 / 0 - 2 / 1 - 0 / 1 - 1 / 1 - 2 / 2 - 0 / 2 - 1 / 2 - 2
O searchForItem procura na listaoComp se já existe o registro 0 - 1 antes de inserir o 1 - 0, entende?
Estava tentando usar o Stream Parallels do Java 8 mas não sei utilizar a ferramenta com direito e não consegui montar esta lógica nos filters. (Não sei nem se é ai mesmo que devo montar as condições.)
A minha dúvida é se alguém já passou por algo parecido e tem algum algorítimo que não seja quadrático para fazer isso e se poderiam me indicar uma direção.
searchForItem
e nem essa classeComparacao
. O tipo delistao
éList<String>
? O que élistaoComp
?hashcode
eequals
com a sua definição de "igual" e, então, armazená-los em umSet
?listaoComp
como resultado? Do jeito que você descreve seu problema, não ficou claro se seriam 21.000, se seriam 441.000.000, se seriam 210.000.000 ou se seria outra coisa.listaoComp
, deve existir uma solução simples que seja O(n log n) ou O(n), provavelmente usando umSet
ou umMap
. O problema é que está difícil entender o que é que você está tentando fazer exatamente. Coloque na sua pergunta o código desearchForItem
e deComparacao
que deve ficar mais fácil. E descreva o tipo delistao
(dado esse.id
, então não éString
, mas então não sei o que é).