<div dir="ltr"><div># Este nao é o melhor uso do MaxEntropy e está longe de diminuir o O(n^2), mas já ajuda a ter uma ideia. ;)</div><div><br></div><div>use AI::MaxEntropy;</div><div><br></div><div>my $me = AI::MaxEntropy->new; </div>
<div><br></div><div>my @a = qw{ 5 4 3 2 1 };</div><div>my @b = qw{ 5 4 3 2 };</div><div>my @c = qw{ 9 8 7 6 5 };</div><div>my @d = qw{ 1 2 3 4 5 };</div><div><br></div><div>$me->see(\@a => 'a' );</div><div>
$me->see(\@b => 'b' );</div>
<div>$me->see(\@c => 'c' );</div><div>$me->see(\@d => 'd' );</div><div><br></div><div><br></div><div>my $model = $me->learn;</div><div><br></div><div>my $BUSCA = \@c; # comparar a lista BUSCA com TODOS q foram informados no 'see'...</div>
<div><br></div><div>print "$_:" . $model->score($BUSCA => $_) . " \n" for $model->all_labels </div><div><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">Em 18 de setembro de 2013 11:38, Renato Santos <span dir="ltr"><<a href="mailto:renato.cron@gmail.com" target="_blank">renato.cron@gmail.com</a>></span> escreveu:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">stan, mas que coisa linda! <div><br></div><div>ficou bom!</div></div><div class="gmail_extra"><div><div>
<br><br><div class="gmail_quote">2013/9/18 Stanislaw Pusep <span dir="ltr"><<a href="mailto:creaktive@gmail.com" target="_blank">creaktive@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hello, my name is Stanislaw and this is Jackass...<div><br></div><div><div><div>use common::sense;</div>
<div>use Text::Levenshtein::XS qw(distance);</div><div><br></div><div># Unicode planes de 3 a 13 são "unassigned", o que permite N < 720000</div>
<div>sub stringify ($) { join q===> map { chr 0x30000 + $_ } sort { $a <=> $b } @{shift()} }</div><div>sub delta ($;$) { distance stringify shift ,=> stringify shift }</div><div><br></div><div>my @a = qw{ 5 4 3 2 1 };</div>
<div>my @b = qw{ 5 4 3 2 };</div><div>my @c = qw{ 9 8 7 6 5 };</div><div>my @d = qw{ 1 2 3 4 5 };</div><div><br></div><div>say delta \@a => \@b; # 1</div><div>say delta \@a => \@c; # 5</div><div>say delta \@a => \@b; # 1</div>
<div>say delta \@d => \@b; # 1</div></div></div><div><br></div><div class="gmail_extra"><div class="gmail_quote"><div><div>2013/9/18 Blabos de Blebe <span dir="ltr"><<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>></span><br>
</div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div><div dir="ltr">Pessoal,<div>
<br></div><div>Um caso de performance:</div>
<div><br></div><div>Eu tenho um conjunto C contendo N listas de inteiros, possivelmente com repetições, onde o tamanho L de cada lista é variável.</div>
<div><br></div><div>N é esperado ser menor que 1000 e L esperado ser menor que 50, mas isso não é obrigatório, embora fortemente esperado.</div><div><br></div><div>Uma lista é considerada idêntica à outra se e somente se ambas tiverem os mesmos tamanhos e elementos. A ordem dos elementos é irrelevante. Ex.:<br>
</div><div><br></div><div>@a = qw{ 1 2 3 4 5 }</div><div>@b = qw{ 5 4 3 2 1 }</div><div>@c = qw{ 1 2 3 4 }</div><div><br></div><div>@a == @b != @c</div><div><br></div><div>
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.:</div>
<div><br></div><div><div>@a = qw{ 5 4 3 2 1 }</div><div>@b = qw{ 5 4 3 2 }</div><div>@c = qw{ 9 8 7 6 5 }</div><div>@d = qw{ 1 2 3 4 5 }</div><div><br></div><div>X( @a, @b ) > X( @a, @c )</div>
<div>
X( @a, @b ) == X( @d, @b )<br></div><div><br></div><div>É 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.</div>
<div><br></div><div>N pode aumentar com o tempo.</div><div><br></div><div>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.</div>
<div><br></div><div>Além disso, eu preciso ser capaz de implementar essa bagaça em menos de uma semana (duração, não prazo).</div><div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>Desde já agradeço pela ajuda.</div><div><br></div><div>[]'s</div></div><div><br></div><div><br></div><div><br></div><div><br></div></div>
<br></div></div>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br></div></div>
<br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br><br clear="all"><div><br></div></div></div><span><font color="#888888">-- <br><div><span style="color:rgb(51,51,51);font-size:x-small">Saravá,</span></div><div><span style="color:rgb(51,51,51);font-size:x-small">Renato CRON</span></div>
<div><div style="text-align:right"><font size="1" color="#333333"><a href="http://www.renatocron.com/blog/" target="_blank">http://www.renatocron.com/blog/</a></font></div></div><div style="text-align:right"><font size="1" color="#333333"><a href="http://twitter.com/#!/renato_cron" target="_blank">@renato_cron</a></font></div>
</font></span></div>
<br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br clear="all"><div><br></div>-- <br><div>Wesley Seidel Carvalho<div>11-8169-1163</div><div><a href="http://www.ime.usp.br/~wesleys" target="_blank">www.ime.usp.br/~wesleys</a></div><div><a href="http://ltasks.com/" target="_blank">www.ltasks.com</a><br>
@wseidel<br></div></div>
<br><br></blockquote></div></div>
</div>