[SP-pm] Performance Comparando Listas

Stanislaw Pusep creaktive at gmail.com
Thu Sep 19 00:58:04 PDT 2013


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 (https://en.wikipedia.org/wiki/Jaccard_index).
Que, por sua vez, evoca outros coeficientes de similaridade, como o cosine
similarity (http://ijiet.com/wp-content/uploads/2013/09/27.pdf).
Completando o rolé, esse coeficiente é muito bom para comparar bit vectors,
até mesmo em Pure-Perl: https://coderwall.com/p/284hja
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.

2013/9/18 Bruno Buss <bruno.buss em gmail.com>

> Oi Blabos,
>
> 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...).
>
> 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.)
>
> [ ]'s
>
> 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
>>
>>
>
>
> --
> Bruno C. Buss
> http://www.brunobuss.net
>
> =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
>
>
-------------- Pr�xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130919/f8e6ba10/attachment.html>


More information about the SaoPaulo-pm mailing list