[SP-pm] Performance Comparando Listas

Wesley Seidel wesley.seidel at gmail.com
Wed Sep 18 07:48:48 PDT 2013


# Este nao é o melhor uso do MaxEntropy e está longe de diminuir o O(n^2),
mas já ajuda a ter uma ideia. ;)

use AI::MaxEntropy;

my $me = AI::MaxEntropy->new;

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 };

$me->see(\@a => 'a' );
$me->see(\@b => 'b' );
$me->see(\@c => 'c' );
$me->see(\@d => 'd' );


my $model = $me->learn;

my $BUSCA = \@c;   # comparar a lista BUSCA com TODOS q foram informados no
'see'...

print "$_:" . $model->score($BUSCA => $_) . " \n" for $model->all_labels



Em 18 de setembro de 2013 11:38, Renato Santos <renato.cron em gmail.com>escreveu:

> stan, mas que coisa linda!
>
> ficou bom!
>
>
> 2013/9/18 Stanislaw Pusep <creaktive em 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 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
>>>
>>>
>>
>> =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
>>
>>
>
>
> --
> Saravá,
> Renato CRON
> http://www.renatocron.com/blog/
> @renato_cron <http://twitter.com/#!/renato_cron>
>
> =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
>
> --
> Wesley Seidel Carvalho
> 11-8169-1163
> www.ime.usp.br/~wesleys
> www.ltasks.com <http://ltasks.com/>
> @wseidel
>
>
>
-------------- Pr?xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130918/19ef90c2/attachment-0001.html>


More information about the SaoPaulo-pm mailing list