Diferencia de dos matrices con Perl

Question

Tengo dos matrices. Necesito verificar y ver si los elementos de uno aparecen en el otro.

¿Hay una forma más eficiente de hacerlo que los bucles anidados? Tengo unos miles de elementos en cada uno y necesito ejecutar el programa con frecuencia.

Answer 1

Otra manera de hacerlo es utilizar Array::Utils

use Array::Utils qw(:all); 

my @a = qw(a b c d); 
my @b = qw(c d e f); 

# 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); 

Answer 2

perlfaq4 al rescate:

¿Cómo calculo la diferencia de dos matrices? ¿Cómo calculo la intersección de dos matrices?

Usa un hash. Aquí hay un código para hacer ambas cosas y más. Se supone que cada elemento es único en una matriz dada:

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

Si se declara correctamente sus variables, el código se parece más a lo siguiente:

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; 
} 

Answer 3

es necesario proporcionar mucho más contexto. Hay formas más eficientes de hacer que van desde:

• Go fuera de Perl y Shell uso (sort + comm)

• map una matriz en un hash Perl y luego bucle sobre la otra comprobación membresía hash. Esto tiene complejidad lineal ("M + N" - básicamente bucle sobre cada matriz una vez) a diferencia de bucle anidado que tiene "M N *" complejidad)

  Ejemplo:

  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 
  

• Utilice un módulo de Perl que hace el último punto para ti (List :: Compare se mencionó en los comentarios)

• Hazlo en función de las marcas de tiempo de cuando se agregaron los elementos si el volumen es muy grande y necesitas volver a comparar a menudo. Unos pocos miles de elementos no son lo suficientemente grandes, pero recientemente tuve que diferir las listas de 100 mil tamaños.

Answer 4

n + n log algoritmo n, si es seguro que los elementos son únicos en cada matriz (como claves 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; 

Entonces, si no estoy seguro de la unidad y quiero verificar la presencia de los 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 

Answer 5

Puede probar Arrays::Utils, y lo hace parecer agradable y simple, pero no está haciendo magia poderosa en el back-end. Aquí está el código array_diffs:

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

Desde Arrays::Utils no es un módulo estándar, es necesario preguntarse si vale la pena el esfuerzo de instalar y mantener este módulo.De lo contrario, está muy cerca de la respuesta de DVK.

Hay ciertas cosas que debe tener en cuenta, y debe definir lo que desea hacer en ese caso particular. Digamos:

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

¿Estas matrices son las mismas? O, ¿son diferentes? Tienen los mismos valores, pero hay duplicados en @array1 y no en @array2.

¿Qué tal esto?

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

diría que estas matrices son los mismos, pero Array::Utils::arrays_diff ve de otro modo. Esto se debe a que Array::Utils asume que no hay entradas duplicadas.

Y, aunque el Perl FAQ señalado por mob también dice que Se supone que cada elemento es único en una matriz dada. ¿Es esta una suposición que puedes hacer?

No importa qué, los hashes son la respuesta. Es fácil y rápido buscar un hash. El problema es qué quieres hacer con valores únicos.

Aquí es una solución sólida que asume duplicados no importan:

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 
    } 
} 

Si duplicados son importantes, necesitará una manera de contarlos. Aquí está el mapa no sólo para crear un hash introducido por cada elemento de la matriz, sino también contar los duplicados en la matriz:

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

Ahora, usted puede ir a través de cada hash y verificar que no sólo existen las claves , pero que sus entradas coinciden

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

Sólo se sale del bucle si todas las entradas en %array1_hash que coincida con sus correspondientes entradas en %array2_hash. Ahora, debe mostrar que todas las entradas en %array2_hash también coinciden con sus entradas en %array1_hash, y que %array2_hash no tiene más entradas. Afortunadamente, podemos hacer lo que hicimos 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 
} 

Answer 6

Intentar usar Lista: Comparar. TI tiene soluciones para todas las operaciones que se pueden realizar en arreglos. https://metacpan.org/pod/List::Compare

Answer 7

my @a = (1,2,3); 
my @b=(2,3,1); 
print "Equal" if grep { $_ ~~ @b } @a == @b; 

Answer 8

Usted desea comparar cada elemento de @x contra el elemento del mismo índice en @y, ¿verdad? Esto lo hará.

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

... o ...

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

que se pueden seleccionar tipo de depende de si usted está más interesado en mantener una lista de los índices de los elementos disímiles, o simplemente interesados ​​en el procesamiento los desajustes uno por uno. La versión grep es útil para obtener la lista de desajustes.(original post)

Answer 9

Usted puede utilizar esto para conseguir diffrence entre dos matrices

#!/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 }; 

Answer 10

No es elegante, pero 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__