У меня есть два массива. Мне нужно проверить и посмотреть, появляются ли элементы одного в другом.
Есть ли более эффективный способ сделать это, чем вложенные циклы? У меня есть несколько тысяч элементов в каждом, и вам нужно часто запускать программу.
Другой способ сделать это - использовать 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 );
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;
}
Вам нужно предоставить гораздо больше контекста. Есть более эффективные способы сделать это, начиная с:
Выйдите за пределы Perl и используйте shell (sort + comm)
map один массив в хеш файл Perl, а затем цикл над другим, проверяющим хэш-членство. Это имеет линейную сложность ( "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, и это заставляет его выглядеть красиво и просто, но это не делает никакой мощной магии на заднем конце. Здесь код 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 предполагает, что дубликатов нет.
И даже в FAQ 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
}
}
Вы выйдете из цикла 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
}
Вы можете использовать это для получения разницы между двумя массивами
#!/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 };
n + n log n, если все элементы уникальны в каждом массиве (как хэш-ключи)
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;
Попробуйте использовать 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__