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
