<div dir="ltr">Outra abordagem: o enunciado do problema evoca o conceito de Jaccard similarity coefficient - a statistic used for comparing the similarity and diversity of sample sets (<a href="https://en.wikipedia.org/wiki/Jaccard_index" target="_blank">https://en.wikipedia.org/wiki/Jaccard_index</a>). Que, por sua vez, evoca outros coeficientes de similaridade, como o cosine similarity (<a href="http://ijiet.com/wp-content/uploads/2013/09/27.pdf" target="_blank">http://ijiet.com/wp-content/uploads/2013/09/27.pdf</a>). Completando o rolé, esse coeficiente é muito bom para comparar bit vectors, até mesmo em Pure-Perl: <a href="https://coderwall.com/p/284hja">https://coderwall.com/p/284hja</a><div class="gmail_extra">
Assim, basta mapear os seus inteiros para uma faixa contínua de, digamos, 0 a 32767, o que resulta em bit vector de 4KB. É meio esdrúxulo reservar 4KB mesmo que as suas listas contenham apenas 50 elementos: isso significa que dos 32768 bits, apenas 50 estarão como "1". A notícia boa é que comparar a similaridade de bit vectors envolve operações bitwise, que são ridiculamente baratas.<br>
<br><div class="gmail_quote">2013/9/18 Bruno Buss <span dir="ltr"><<a href="mailto:bruno.buss@gmail.com" target="_blank">bruno.buss@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">Oi Blabos,<div><br></div><div>Você pode comparar duas listas em O(L) usando hashes. Sua complexidade ficaria em O(N^2 * L) e para a os limites que você deu (N <= 1000, L <= 50) isso deve demorar (bem) menos de 1 segundo para ser computado. Até N <= 10_000 você não teria problemas para executar esse processamento em um tempo bem pequeno (poucos segundos...). <br>
</div><div><br></div><div>Para casos maiores, ou se você realmente quiser atualizar o seu "índice de similaridade" a cada alteração... supondo que o seu índice seja calculado a partir dos tamanhos de cada lista e número de itens em comum, dependendo de onde/como você guarda a informação dos itens da sua lista acredito ser tranquilo recalcular os índices a cada inserção ou remoção de um item de alguma lista. (E.g. se você tiver uma tabela que contenha a tupla (id_lista, id_elemento) para cada item em uma lista, é possível fazer com uma query o ajuste da contagem dos itens em comum.)</div>
<div><br></div><div>[ ]'s</div><div class="gmail_extra"><br><div class="gmail_quote"><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><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><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></div></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br>Bruno C. Buss<br><a href="http://www.brunobuss.net" target="_blank">http://www.brunobuss.net</a>
</font></span></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></div></div>