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 <[email protected]> > 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 <[email protected]> > >> 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: [email protected] >> 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: [email protected] > 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: [email protected] L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> =end disclaimer
