[SP-pm] Performance Comparando Listas

Stanislaw Pusep creaktive at gmail.com
Wed Sep 18 07:20:22 PDT 2013


Hello, my name is Stanislaw and this is Jackass...

use common::sense;
use Text::Levenshtein::XS qw(distance);

# Unicode planes de 3 a 13 são "unassigned", o que permite N < 720000
sub stringify ($) { join q===> map { chr 0x30000 + $_ } sort { $a <=> $b }
@{shift()} }
sub delta ($;$) { distance stringify shift ,=> stringify shift }

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

say delta \@a => \@b; # 1
say delta \@a => \@c; # 5
say delta \@a => \@b; # 1
say delta \@d => \@b; # 1

2013/9/18 Blabos de Blebe <blabos em 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 em pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>
-------------- Pr�xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130918/bfd4b946/attachment-0001.html>


More information about the SaoPaulo-pm mailing list