<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">2013/9/18 Blabos de Blebe <span dir="ltr"><<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>></span><br>

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