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

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

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

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

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

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

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

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

  • Выйдите из Perl и используйте shell ( sort + comm )

  • map один массив с хешем Perl и затем перейдем к другому, проверяя hash-членство. Это имеет линейную сложность («M + 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 тыс.

Вы можете попробовать Arrays::Utils , и это заставляет его выглядеть красиво и просто, но на заднем 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, на которые указывает моб, также говорят, что он предполагает, что каждый элемент уникален в данном массиве . Это предположение, которое вы можете сделать?

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

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

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

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

 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 из цикла for, если все записи в %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 } 

n + n log n, если уверены, что элементы уникальны в каждом массиве (как 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; 

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

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

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

Попробуйте использовать List: Compare. У ИТ есть решения для всех операций, которые могут выполняться на массивах. https://metacpan.org/pod/List::Compare

Вы хотите сравнить каждый элемент @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 удобна для получения списка несоответствий. ( оригинальное сообщение )

Не изящно, но легко понять:

 #!/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__ в #!/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__ 
  • C ++ 11: Исправить инициализацию std :: array?
  • MongoDB - запрос последнего элемента массива?
  • Где задано свойство длины массива?
  • Есть ли что-нибудь вроде deal () для обычных массивов MATLAB?
  • mongodb найти несколько элементов массива
  • Реверсивный массив C ++
  • Как упрощенная инструкция оператора работает для массивов и как получить iterator для массива?
  • Изменение значений во время итерации в golang
  • Передача массивов в качестве параметров в bash
  • MongoDB: Как обновить один подэлемент в массиве, на который ссылается индекс внутри массива?
  • Можете ли вы resize массива C ++ после инициализации?
  • Давайте будем гением компьютера.