[SP-pm] Performance Comparando Listas

Blabos de Blebe blabos at gmail.com
Wed Sep 18 05:57:15 PDT 2013


Pessoal,

Um caso de performance:

Eu tenho um conjunto C contendo N listas de inteiros, possivelmente com
repetições, onde o tamanho L de cada lista é variável.

N é esperado ser menor que 1000 e L esperado ser menor que 50, mas isso não
é obrigatório, embora fortemente esperado.

Uma lista é considerada idêntica à outra se e somente se ambas tiverem os
mesmos tamanhos e elementos. A ordem dos elementos é irrelevante. Ex.:

@a = qw{ 1 2 3 4 5 }
@b = qw{ 5 4 3 2 1 }
@c = qw{ 1 2 3 4 }

@a == @b != @c

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.:

@a = qw{ 5 4 3 2 1 }
@b = qw{ 5 4 3 2 }
@c = qw{ 9 8 7 6 5 }
@d = qw{ 1 2 3 4 5 }

X( @a, @b ) > X( @a, @c )
X( @a, @b ) == X( @d, @b )

É 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.

N pode aumentar com o tempo.

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.

Além disso, eu preciso ser capaz de implementar essa bagaça em menos de uma
semana (duração, não prazo).

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.

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.

Desde já agradeço pela ajuda.

[]'s
-------------- Pr�xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130918/8a0ce305/attachment.html>


More information about the SaoPaulo-pm mailing list