<div dir="ltr">Pessoal,<div><br></div><div style>Um caso de performance:</div><div style><br></div><div style>Eu tenho um conjunto C contendo N listas de inteiros, possivelmente com repetições, onde o tamanho L de cada lista é variável.</div>

<div style><br></div><div style>N é esperado ser menor que 1000 e L esperado ser menor que 50, mas isso não é obrigatório, embora fortemente esperado.</div><div style><br></div><div style>Uma lista é considerada idêntica à outra se e somente se ambas tiverem os mesmos tamanhos e elementos. A ordem dos elementos é irrelevante. Ex.:<br>

</div><div style><br></div><div style>@a = qw{ 1 2 3 4 5 }</div><div style>@b = qw{ 5 4 3 2 1 }</div><div style>@c = qw{ 1 2 3 4 }</div><div style><br></div><div style>@a == @b != @c</div><div style><br></div><div style>
Eu preciso comparar todas as listas duas a duas e saber qual a taxa de similaridade X entre essas duas, necessariamente, onde X é uma grandeza qualquer que represente o quanto uma lista é parecida com outra. Ex.:</div>
<div style><br></div><div style><div>@a = qw{ 5 4 3 2 1 }</div><div>@b = qw{ 5 4 3 2 }</div><div>@c = qw{ 9 8 7 6 5 }</div><div style>@d = qw{ 1 2 3 4 5 }</div><div><br></div><div style>X( @a, @b ) > X( @a, @c )</div>
<div style>
X( @a, @b ) == X( @d, @b )<br></div><div style><br></div><div style>É esperado que as listas variem com frequência (diariamente, no mínimo) e que as similaridades sejam atualizadas a cada variação de qualquer elemento de qualquer lista.</div>

<div style><br></div><div style>N pode aumentar com o tempo.</div><div style><br></div><div style>Problema enunciado, eu gostaria que vocês me indicassem documentação, módulos, artigos, dicas e truques de como comparar as listas com Perl, sem que eu tenha que escrever XS, da forma mais eficiente possível.</div>

<div><br></div><div>Além disso, eu preciso ser capaz de implementar essa bagaça em menos de uma semana (duração, não prazo).</div><div><br></div><div style>Meu objetivo é que dada uma lista qualquer, eu encontre as top 5 mais parecidas com ela, para analisar um atributo arbitrário que não faz parte do enunciado deste problema, ou seja, encontrar as top 5 mais parecidas é só uma ferramenta para o objetivo real.</div>

<div style><br></div><div style>Sim, como enunciado, a combinação é aplicação de força bruta, resulta em um algoritmo na casa dos O(n^2) (supondo o cálculo de X constante) e por isso estou recorrendo a vocês por ideias melhores.</div>

<div style><br></div><div style>Desde já agradeço pela ajuda.</div><div style><br></div><div style>[]'s</div></div><div style><br></div><div style><br></div><div style><br></div><div style><br></div></div>