[SP-pm] Performance Comparando Listas

[Renato Santos]

stan, mas que coisa linda!

ficou bom!


2013/9/18 Stanislaw Pusep <creaktive at gmail.com>

> 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 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
>>
>>
>
> =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
>
>


-- 
Saravá,
Renato CRON
http://www.renatocron.com/blog/
@renato_cron <http://twitter.com/#!/renato_cron>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130918/af2b6b11/attachment.html>