Differenza di due matrici che usano Perl

Ho due array. Devo controllare e vedere se gli elementi di uno appaiono nell’altro.

C’è un modo più efficiente per farlo rispetto ai cicli annidati? Ho qualche migliaio di elementi in ognuno e ho bisogno di eseguire il programma frequentemente.

Un altro modo per farlo è usare 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 in soccorso:

Come faccio a calcolare la differenza di due array? Come si calcola l’intersezione di due array?

Usa un hash. Ecco il codice per fare entrambi e molto altro. Presuppone che ciascun elemento sia unico in un determinato 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 si dichiarano correttamente le variabili, il codice ha un aspetto più simile al seguente:

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

È necessario fornire molto più contesto. Ci sono modi più efficienti per farlo che vanno da:

  • Vai fuori da Perl e usa shell ( sort + comm )

  • map un array in un hash Perl e quindi eseguire il loop sull’altro controllando l’appartenenza all’hash. Questo ha una complessità lineare (“M + N” – fondamentalmente loop su ogni array una volta) rispetto al loop annidato che ha complessità “M * N”)

    Esempio:

     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 
  • Usa un modulo Perl che fa l’ultimo punto elenco per te (List :: Compare è stato menzionato nei commenti)

  • Fatelo basandosi sui timestamp del momento in cui gli elementi sono stati aggiunti se il volume è molto grande e dovete ricontestarlo spesso. Alcune migliaia di elementi non sono abbastanza grandi, ma di recente ho dovuto diffare elenchi di dimensioni 100k.

Puoi provare Arrays::Utils , e lo fa sembrare bello e semplice, ma non sta facendo alcuna potente magia sul back-end. Ecco il codice array_diffs :

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

Poiché Arrays::Utils non è un modulo standard, è necessario chiedersi se vale la pena di installare e gestire questo modulo. Altrimenti, è abbastanza vicino alla risposta di DVK .

Ci sono alcune cose che devi fare attenzione e devi definire cosa vuoi fare in quel caso particolare. Diciamo:

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

Questi array sono uguali? O sono diversi? Hanno gli stessi valori, ma ci sono duplicati in @array1 e non @array2 .

Che dire di questo?

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

Direi che questi array sono uguali, ma Array::Utils::arrays_diff chiede di dissentire. Questo perché Array::Utils presuppone che non ci siano voci duplicate.

E, anche le FAQ Perl indicate da mob dicono anche che Suppone che ogni elemento sia unico in un dato array . È una supposizione che puoi fare?

Non importa cosa, gli hash sono la risposta. È facile e veloce cercare un hash. Il problema è cosa vuoi fare con valori unici.

Ecco una soluzione solida che presuppone che i duplicati non contengano:

 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 i duplicati contano, avrai bisogno di un modo per contarli. Qui viene utilizzata la mappa non solo per creare un hash digitato da ogni elemento dell’array, ma anche contare i duplicati nell’array:

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

Ora puoi esaminare ciascun hash e verificare che non solo le chiavi esistano, ma che le loro voci corrispondano

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

%array1_hash dal ciclo for solo se tutte le voci in %array1_hash corrispondono alle voci corrispondenti in %array2_hash . Ora, devi mostrare che tutte le voci in %array2_hash corrispondono anche alle loro voci in %array1_hash e che %array2_hash non ha più voci. Fortunatamente, possiamo fare ciò che abbiamo fatto prima:

 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 } 

algoritmo n + n log n, se certi che gli elementi siano univoci in ogni array (come chiavi 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; 

Quindi se non sono sicuro dell’unità e voglio controllare la presenza degli elementi di array1 all’interno di 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; 

È ansible utilizzare questo per ottenere la diffrenza tra due matrici

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

Prova ad usare Elenco: Confronta. L’IT ha soluzioni per tutte le operazioni che possono essere eseguite sugli array. https://metacpan.org/pod/List::Compare

Vuoi confrontare ogni elemento di @x con l’elemento dello stesso indice in @y, giusto? Questo lo farà.

 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[$_]; } 

La scelta dipende dal fatto che sia più interessato a mantenere un elenco di indici agli elementi dissimili o semplicemente interessato a elaborare i disallineamenti uno per uno. La versione di grep è utile per ottenere l’elenco delle discrepanze. ( post originale )

Non elegante, ma facile da capire:

 #!/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__