[SP-pm] Performance Comparando Listas

[Bruno Buss]

Oi Blabos,

Você pode comparar duas listas em O(L) usando hashes. Sua complexidade
ficaria em O(N^2 * L) e para a os limites que você deu (N <= 1000, L <= 50)
isso deve demorar (bem) menos de 1 segundo para ser computado. Até N <=
10_000 você não teria problemas para executar esse processamento em um
tempo bem pequeno (poucos segundos...).

Para casos maiores, ou se você realmente quiser atualizar o seu "índice de
similaridade" a cada alteração... supondo que o seu índice seja calculado a
partir dos tamanhos de cada lista e número de itens em comum, dependendo de
onde/como você guarda a informação dos itens da sua lista acredito ser
tranquilo recalcular os índices a cada inserção ou remoção de um item de
alguma lista. (E.g. se você tiver uma tabela que contenha a tupla
(id_lista, id_elemento) para cada item em uma lista, é possível fazer com
uma query o ajuste da contagem dos itens em comum.)

[ ]'s

2013/9/18 Blabos de Blebe <blabos at gmail.com>

> 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
>
>
>
>
>
> =begin disclaimer
>    Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>  SaoPaulo-pm mailing list: SaoPaulo-pm at pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>


-- 
Bruno C. Buss
http://www.brunobuss.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130918/c5462761/attachment.html>