Sự khác biệt của hai mảng sử dụng Perl

Question

Tôi có hai mảng. Tôi cần phải kiểm tra xem liệu các yếu tố của một xuất hiện trong một khác.

Có cách nào hiệu quả hơn để làm điều đó hơn vòng lặp lồng nhau không? Tôi có một vài nghìn yếu tố trong mỗi và cần phải chạy chương trình thường xuyên.

Answer 1

Một cách khác để làm điều đó là sử dụng 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 để giải cứu:

Làm thế nào để tính toán độ lệch của hai mảng? Làm cách nào để tính toán giao điểm của hai mảng?

Sử dụng hàm băm. Đây là mã để làm cả hai và nhiều hơn nữa. Nó giả định rằng mỗi phần tử là duy nhất trong một mảng:

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

Nếu bạn đúng cách khai báo các biến của bạn, mã trông giống như sau:

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

Bạn cần cung cấp nhiều hơn nữa bối cảnh. Có nhiều cách hiệu quả hơn để làm điều đó khác nhau, từ:

• Go ngoài Perl và sử dụng vỏ (sort + comm)

• map một mảng thành một băm Perl và sau đó lặp trên một trong những khác kiểm tra thành viên băm. Đây có tuyến tính phức tạp ("M + N" - về cơ bản lặp trên mỗi mảng một lần) như trái ngược với vòng lặp lồng nhau trong đó có "M * N" phức tạp)

  Ví dụ:

  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 
  

• Sử dụng một module Perl có điểm bullet cuối cùng cho bạn (Danh sách :: So sánh được đề cập trong phần bình luận)

• Làm dựa trên dấu thời gian khi phần tử được thêm vào nếu âm lượng rất lớn và bạn cần phải so sánh thường xuyên. Một vài nghìn yếu tố không thực sự đủ lớn, nhưng gần đây tôi đã có các danh sách có kích thước 100k khác nhau.

Answer 4

n + n log thuật toán n, nếu chắc chắn rằng yếu tố này là duy nhất trong mỗi mảng (như phím băm)

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; 

Vì vậy, nếu tôi không chắc chắn về sự đoàn kết và muốn kiểm tra sự hiện diện của các phần tử array1 bên trong mảng2,

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

Bạn có thể thử Arrays::Utils, và nó làm cho nó trông đẹp và đơn giản, nhưng nó không làm bất kỳ phép thuật mạnh mẽ nào ở mặt sau. Dưới đây là đoạn code array_diffs:

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

Kể từ Arrays::Utils không phải là một mô-đun tiêu chuẩn, bạn cần phải tự hỏi mình nếu nó có giá trị các nỗ lực để cài đặt và duy trì mô đun này.Nếu không, nó khá gần với câu trả lời của DVK.

Có một số điều bạn phải xem và bạn phải xác định những gì bạn muốn làm trong trường hợp cụ thể đó. Giả sử:

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

Các mảng này có giống nhau không? Hay chúng khác nhau? Chúng có cùng giá trị, nhưng có các bản sao trong @array1 và không phải là @array2.

Điều này thì sao?

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

Tôi sẽ nói rằng các mảng này giống nhau, nhưng Array::Utils::arrays_diff yêu cầu khác biệt. Điều này là do Array::Utils giả định rằng không có mục nhập trùng lặp nào.

Và, ngay cả Câu hỏi thường gặp Perl được chỉ ra bởi mob cũng nói rằng Giả định rằng mỗi phần tử là duy nhất trong một mảng nhất định. Đây có phải là một giả định bạn có thể thực hiện?

Không có vấn đề gì, băm là câu trả lời. Thật dễ dàng và nhanh chóng để tìm kiếm một băm. Vấn đề là bạn muốn làm gì với các giá trị duy nhất.

Dưới đây là một giải pháp vững chắc, cho rằng bản sao không quan trọng:

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

Nếu trùng lặp thành vấn đề, bạn sẽ cần một cách để đếm chúng. Dưới đây là sử dụng bản đồ không chỉ để tạo ra một băm keyed bởi mỗi phần tử trong mảng, nhưng cũng đếm các bản sao trong mảng:

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

Bây giờ, bạn có thể đi qua từng băm và xác minh rằng không chỉ các phím tồn tại , nhưng mà mục của họ phù hợp với

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

Bạn chỉ sẽ thoát khỏi vòng lặp for nếu tất cả các mục trong %array1_hash phù hợp với mục tương ứng của họ trong %array2_hash. Bây giờ, bạn phải cho thấy rằng tất cả các mục nhập trong %array2_hash cũng khớp với các mục nhập của chúng trong %array1_hash và rằng %array2_hash không có nhiều mục nhập hơn. May mắn thay, chúng tôi có thể làm những gì chúng tôi đã làm trước đây:

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

Hãy thử sử dụng Danh sách: So sánh. CNTT có các giải pháp cho tất cả các hoạt động có thể được thực hiện trên các mảng. 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

Bạn muốn so sánh từng phần tử của @x chống lại các yếu tố của chỉ số tương tự trong @y, phải không? Điều này sẽ làm điều đó.

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

... hoặc ...

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

mà bạn chọn loại phụ thuộc vào việc bạn đang quan tâm nhiều hơn trong việc giữ một danh sách các chỉ số với các yếu tố khác nhau, hoặc đơn giản là quan tâm đến việc xử lý sự không phù hợp từng cái một. Các phiên bản grep là tiện dụng để có được danh sách các sự không phù hợp.(original post)

Answer 9

Bạn có thể sử dụng để nhận diffrence giữa hai mảng

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

Không tao nhã, nhưng dễ hiểu:

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