Разница двух массивов с использованием Perl

Question

У меня есть два массива. Мне нужно проверить и посмотреть, появляются ли элементы одного в другом.

Есть ли более эффективный способ сделать это, чем вложенные циклы? У меня есть несколько тысяч элементов в каждом, и вам нужно часто запускать программу.

Answer 1

Другой способ сделать это состоит в использовании 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 на помощь:

Как вычислить разность двух массивов? Как вычислить пересечение двух массивов?

Использование хэш. Вот код для обоим и более. Предполагается, что каждый элемент является уникальным в данном массиве:

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

Если вы правильно объявлять переменные, код выглядит так:

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

Вы должны предоставить гораздо больше контекст. Есть более эффективные способы сделать это, начиная от:

• Go вне Perl и использования оболочки (sort + comm)

• map одного массива в хэш Perl, а затем цикл по другой проверки хэш-членство. Это имеет линейную сложность ("М + N" - в основном цикл над каждым массивом один раз), в отличие от вложенного цикла, который имеет "M * N" сложности)

  Пример:

  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 
  

• использовать модуль Perl который делает последний пункт для вас (List: Compare был упомянут в комментариях)

• Сделайте это на основе временных меток, когда элементы были добавлены, если объем очень большой, и вам нужно повторно сравнить его часто. Несколько тысяч элементов на самом деле не достаточно большие, но мне недавно пришлось сопоставлять списки размером 100 тыс.

Answer 4

п + п войти п алгоритм, если уверен, что элементы являются уникальными для каждого массива (как хэш-ключей)

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; 

Итак, если я не уверен в единстве и хочу проверить наличие элементов массива1 внутри 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

Вы можете попробовать Arrays::Utils, и это заставляет его выглядеть красиво и просто, но на заднем конце он не обладает мощной магией. Вот array_diffs код:

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

Поскольку Arrays::Utils не является стандартным модулем, вы должны спросить себя, если это стоит усилий, чтобы установить и поддерживать этот модуль.В противном случае это довольно близко к ответу DVK.

Есть определенные вещи, за которыми вы должны следить, и вы должны определить, что вы хотите сделать в этом конкретном случае. Скажем:

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

Являются ли эти массивы одинаковыми? Или они разные? Они имеют одинаковые значения, но есть дубликаты в @array1, а не @array2.

Что относительно этого?

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

Я бы сказал, что эти массивы являются одинаковыми, но Array::Utils::arrays_diff просит отличаться. Это связано с тем, что Array::Utils предполагает, что дубликатов нет.

И даже в Perl часто задаваемые вопросы mob также говорит, что Предполагается, что каждый элемент уникален в заданном массиве. Это предположение, которое вы можете сделать?

Независимо от того, хеши являются ответом. Легко и быстро найти хэш. Проблема в том, что вы хотите делать с уникальными значениями.

Вот твердое решение, которое принимает на себя дубликаты не имеют значения:

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

Если дубликаты имеют значение, вам нужен способ, чтобы сосчитать их. Вот с помощью карты не только для создания хэша заклиненного каждого элемента в массиве, но и сосчитать дубликаты в массиве:

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

Теперь вы можете пройти через каждый хэш и убедитесь, что не только существуют ключи , но их данные соответствуют

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 соответствуют их соответствующие записи в %array2_hash. Теперь вы должны показать, что все записи в %array2_hash также соответствуют их записям в %array1_hash и что %array2_hash не имеет других записей. К счастью, мы можем сделать то, что мы сделали до этого:

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

Попробуйте использовать Список: Сравнить. У ИТ есть решения для всех операций, которые могут выполняться на массивах. 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

Вы хотите сравнить каждый элемент @x против элемента одного и того же показателя в @y, верно? Это сделает это.

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

... или ...

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

который вы выбираете вид зависит от того, больше заинтересованы в сохранении список индексов для других элементов, или просто заинтересованы в обработке вы несоответствия друг за другом. Версия grep удобна для получения списка несоответствий.(original post)

Answer 9

Вы можете использовать это для получения разностного между двумя массивами

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

Не шикарно, но легко понять:

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