funciones - Diferencia de dos matrices con Perl

perl split

Question

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

¿Hay una manera 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

Algoritmo n + n log n, si es seguro que los elementos son únicos en cada arreglo (como teclas 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 2

Debes proporcionar mucho más contexto. Hay formas más eficientes de hacerlo que van desde:

• Sal fuera de Perl y usa shell ( sort + comm )

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

  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

• Use un módulo Perl que haga el último punto por usted (List :: Compare fue mencionado en los comentarios)

• Hágalo en función de las marcas de tiempo de cuándo se agregaron elementos si el volumen es muy grande y necesita volver a comparar con frecuencia. Unos pocos miles de elementos no son lo suficientemente grandes, pero recientemente tuve que diferir las listas de 100 mil tamaños.

Answer 3

Desea comparar cada elemento de @x con 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[$_];
}

El tipo de elección que elijas depende de si estás más interesado en mantener una lista de índices con los elementos diferentes o si simplemente estás interesado en procesar los desajustes uno por uno. La versión grep es útil para obtener la lista de desajustes. ( publicación original )

Answer 4

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

Answer 5

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

Answer 6

Otra forma de hacerlo es usar 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 7

Puede usar esto para obtener la diferencia 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 8

Puedes probar Arrays::Utils , y se ve bien 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 ] };
}

Como Arrays::Utils no es un módulo estándar, debe 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 de las que debe cuidarse, y debe definir qué quiere 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);

¿Son estas matrices iguales? O, ¿son diferentes? Tienen los mismos valores, pero hay duplicados en @array1 y no @array2 .

¿Qué hay de esto?

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

Yo diría que estas matrices son iguales, pero Array::Utils::arrays_diff suplica diferir. Esto se debe a que Array::Utils asume que no hay entradas duplicadas.

Y, incluso las preguntas frecuentes de Perl señaladas por la mob también dicen que asume que cada elemento es único en una matriz dada . ¿Es esta una suposición que puedes hacer?

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

Aquí hay una solución sólida que asume que los 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 los duplicados sí importan, necesitará una forma de contarlos. Aquí está el uso del mapa no solo para crear un hash codificado por cada elemento de la matriz, sino también para contar los duplicados en la matriz:

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

Ahora, puede revisar cada hash y verificar que no solo existan las claves, sino que coincidan sus entradas

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

Solo saldrá del ciclo for si todas las entradas en %array1_hash coinciden con sus entradas correspondientes 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 9

perlfaq4 al rescate:

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

Use un hash Aquí hay un código para hacer ambas cosas y más. Asume que cada elemento es único en una matriz determinada:

 @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 declara adecuadamente 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 10

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