Differenza di due matrici che utilizzano Perl

Question

Ho due matrici. 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.

Answer 1

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

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

Utilizzare un hash. Ecco il codice per fare entrambi e molto altro. Si presuppone che ogni elemento è unico in un dato 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 sembra 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; 
} 

Answer 3

è necessario fornire molto di più contesto. Ci sono modi più efficienti di fare quello che va da:

• andare al di fuori di Perl e l'uso della shell (sort + comm)

• map un array in un hash Perl e poi un ciclo su l'altra verifica appartenenza all'hash. Questo ha complessità lineare ("M + N" - fondamentalmente un ciclo su ogni matrice volta) rispetto al ciclo annidato che ha "M * N" complessità)

  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 
  

• Utilizzare un modulo Perl che fa l'ultimo punto elenco per te (List :: Compare è stato menzionato nei commenti)

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

Answer 4

n + n log algoritmo n, se assicurarsi che gli elementi sono unici in ogni matrice (come chiavi di 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 dell'array1 all'interno dell'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

Si può provare Arrays::Utils, e lo fa sembrare bello e semplice, ma non sta facendo alcuna magia potente 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 ] }; 
} 

Dal Arrays::Utils non è un modulo standard, è necessario chiedersi se vale la pena lo sforzo di installare e mantenere 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 gli stessi? 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 gli stessi, ma Array::Utils::arrays_diff permette di dissentire. Questo perché Array::Utils presuppone che non vi siano voci duplicate.

E, anche le FAQ Perl evidenziate da mob affermano anche che Si presuppone che ogni elemento sia univoco in un determinato array. È una supposizione che puoi fare?

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

Ecco una soluzione solida che si assume i duplicati non contano:

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 duplicati sono importanti, avrete bisogno di un modo di contarli. Ecco come usare la mappa non solo per creare un hash digitato da ciascun elemento della matrice, ma anche contare i duplicati nella matrice:

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

Ora, si può passare attraverso ogni hash e verificare che non solo esistono le chiavi , ma che le loro voci corrispondono

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

Si uscirà solo il ciclo for, se tutte le voci in %array1_hash corrispondono alle loro 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 quello 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 
} 

Answer 6

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

Answer 7

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

Answer 8

Si desidera confrontare ogni elemento della @x contro l'elemento dello stesso indice nel @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[$_]; 
} 

cui si sceglie tipo di dipende se siete più interessati a mantenere un elenco di indici agli elementi dissimili, o semplicemente interessati a trasformazione i disallineamenti uno per uno. La versione di grep è utile per ottenere l'elenco delle discrepanze.(original post)

Answer 9

È possibile utilizzare questo per ottenere diffrence tra due array

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

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__