Diferença de duas matrizes usando Perl

Eu tenho dois arrays. Preciso verificar e ver se os elementos de um aparecem no outro.

Existe uma maneira mais eficiente de fazer isso do que loops nesteds? Eu tenho alguns milhares de elementos em cada um e preciso executar o programa com freqüência.

Outra maneira de fazer isso é usar Array :: Utils

 use Array::Utils qw(:all); my @a = qw( abcd ); my @b = qw( cdef ); # symmetric difference my @diff = array_diff(@a, @b); # intersection my @isect = intersect(@a, @b); # unique union my @unique = unique(@a, @b); # check if arrays contain same members if ( !array_diff(@a, @b) ) { # do something } # get items from array @a that are not in array @b my @minus = array_minus( @a, @b ); 

perlfaq4 para o resgate:

Como faço para calcular a diferença de dois arrays? Como faço para calcular a interseção de duas matrizes?

Use um hash. Aqui está o código para fazer as duas coisas e muito mais. Ele assume que cada elemento é único em um determinado array:

  @union = @intersection = @difference = (); %count = (); foreach $element (@array1, @array2) { $count{$element}++ } foreach $element (keys %count) { push @union, $element; push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element; } 

Se você declarar corretamente suas variables, o código será mais parecido com o seguinte:

 my %count; for my $element (@array1, @array2) { $count{$element}++ } my ( @union, @intersection, @difference ); for my $element (keys %count) { push @union, $element; push @{ $count{$element} > 1 ? \@intersection : \@difference }, $element; } 

Você precisa fornecer muito mais contexto. Existem maneiras mais eficientes de fazer isso, desde:

  • Saia do Perl e use shell ( sort + comm )

  • map uma matriz em um hash Perl e, em seguida, fazer um loop sobre a outra, verificando a associação de hash. Isto tem uma complexidade linear (“M + N” – basicamente faz um loop sobre cada array uma vez) ao contrário do loop nested que tem complexidade “M * N”)

    Exemplo:

     my %second = map {$_=>1} @second; my @only_in_first = grep { !$second{$_} } @first; # use a foreach loop with `last` instead of "grep" # if you only want yes/no answer instead of full list 
  • Use um módulo Perl que faça o último ponto para você (List :: Compare foi mencionado nos comentários)

  • Faça isso com base em registros de data e hora de quando os elementos foram adicionados se o volume for muito grande e você precisar comparar novamente com frequência. Alguns milhares de elementos não são grandes o suficiente, mas recentemente tive que diferenciar listas de tamanho de 100k.

Você pode tentar Arrays::Utils , e faz com que pareça agradável e simples, mas não está fazendo nenhuma mágica poderosa no back-end. Aqui está o código array_diffs :

 sub array_diff(\@\@) { my %e = map { $_ => undef } @{$_[1]}; return @{[ ( grep { (exists $e{$_}) ? ( delete $e{$_} ) : ( 1 ) } @{ $_[0] } ), keys %e ] }; } 

Como Arrays::Utils não é um módulo padrão, você precisa se perguntar se vale a pena o esforço para instalar e manter este módulo. Caso contrário, é bem próximo da resposta do DVK .

Há certas coisas que você deve observar, e você tem que definir o que você quer fazer nesse caso particular. Digamos:

 @array1 = qw(1 1 2 2 3 3 4 4 5 5); @array2 = qw(1 2 3 4 5); 

Essas matrizes são as mesmas? Ou eles são diferentes? Eles têm os mesmos valores, mas existem duplicatas em @array1 e não em @array2 .

O que sobre isso?

 @array1 = qw( 1 1 2 3 4 5 ); @array2 = qw( 1 1 2 3 4 5 ); 

Eu diria que esses arrays são os mesmos, mas Array::Utils::arrays_diff implora para diferir. Isso ocorre porque o Array::Utils assume que não há inputs duplicadas.

E, até mesmo o FAQ Perl apontado pela máfia também diz que ele assume que cada elemento é único em um determinado array . Isso é uma suposição que você pode fazer?

Não importa o que, hashes são a resposta. É fácil e rápido procurar um hash. O problema é o que você quer fazer com valores únicos.

Aqui está uma solução sólida que pressupõe duplicatas não importa:

 sub array_diff { my @array1 = @{ shift() }; my @array2 = @{ shift() }; my %array1_hash; my %array2_hash; # Create a hash entry for each element in @array1 for my $element ( @array1 ) { $array1_hash{$element} = @array1; } # Same for @array2: This time, use map instead of a loop map { $array_2{$_} = 1 } @array2; for my $entry ( @array2 ) { if ( not $array1_hash{$entry} ) { return 1; #Entry in @array2 but not @array1: Differ } } if ( keys %array_hash1 != keys %array_hash2 ) { return 1; #Arrays differ } else { return 0; #Arrays contain the same elements } } 

Se as duplicatas forem importantes, você precisará de uma maneira de contá-las. Aqui está usando o mapa não apenas para criar um hash codificado por cada elemento na matriz, mas também para contar as duplicatas na matriz:

 my %array1_hash; my %array2_hash; map { $array1_hash{$_} += 1 } @array1; map { $array2_hash{$_} += 2 } @array2; 

Agora, você pode passar por cada hash e verificar se não apenas as chaves existem, mas também que as inputs coincidem

 for my $key ( keys %array1_hash ) { if ( not exists $array2_hash{$key} or $array1_hash{$key} != $array2_hash{$key} ) { return 1; #Arrays differ } } 

Você só sairá do loop for se todas as inputs em %array1_hash corresponderem às inputs correspondentes em %array2_hash . Agora, você precisa mostrar que todas as inputs em %array2_hash também correspondem às inputs em %array1_hash e que %array2_hash não possui mais inputs. Felizmente, podemos fazer o que fizemos antes:

 if ( keys %array2_hash != keys %array1_hash ) { return 1; #Arrays have a different number of keys: Don't match } else { return; #Arrays have the same keys: They do match } 

n + n log n algoritmo, se certeza de que os elementos são únicos em cada matriz (como chaves hash)

 my %count = (); foreach my $element (@array1, @array2) { $count{$element}++; } my @difference = grep { $count{$_} == 1 } keys %count; my @intersect = grep { $count{$_} == 2 } keys %count; my @union = keys %count; 

Então, se eu não tenho certeza da unidade e quero verificar a presença dos elementos de array1 dentro de array2,

 my %count = (); foreach (@array1) { $count{$_} = 1 ; }; foreach (@array2) { $count{$_} = 2 if $count{$_}; }; # N log N if (grep { $_ == 1 } values %count) { return 'Some element of array1 does not appears in array2' } else { return 'All elements of array1 are in array2'. } # N + N log N 
 my @a = (1,2,3); my @b=(2,3,1); print "Equal" if grep { $_ ~~ @b } @a == @b; 

Você pode usar isso para obter diffrence entre duas matrizes

 #!/usr/bin/perl -w use strict; my @list1 = (1, 2, 3, 4, 5); my @list2 = (2, 3, 4); my %diff; @diff{ @list1 } = undef; delete @diff{ @list2 }; 

Tente usar List: Compare. A TI tem soluções para todas as operações que podem ser realizadas em matrizes. https://metacpan.org/pod/List::Compare

Você quer comparar cada elemento de @x contra o elemento do mesmo índice em @y, certo? Isso vai fazer isso.

 print "Index: $_ => \@x: $x[$_], \@y: $y[$_]\n" for grep { $x[$_] != $y[$_] } 0 .. $#x; 

…ou…

 foreach( 0 .. $#x ) { print "Index: $_ => \@x: $x[$_], \@y: $y[$_]\n" if $x[$_] != $y[$_]; } 

O que você escolhe depende se você está mais interessado em manter uma lista de índices para os elementos dissimilares, ou simplesmente interessado em processar os descompassos um por um. A versão grep é útil para obter a lista de incompatibilidades. ( post original )

Não elegante, mas fácil de entender:

 #!/usr/local/bin/perl use strict; my $file1 = shift or die("need file1"); my $file2 = shift or die("need file2");; my @file1lines = split/\n/,`cat $file1`; my @file2lines = split/\n/,`cat $file2`; my %lines; foreach my $file1line(@file1lines){ $lines{$file1line}+=1; } foreach my $file2line(@file2lines){ $lines{$file2line}+=2; } while(my($key,$value)=each%lines){ if($value == 1){ print "$key is in only $file1\n"; }elsif($value == 2){ print "$key is in only $file2\n"; }elsif($value == 3){ print "$key is in both $file1 and $file2\n"; } } exit; __END__