Perl 合并数组的散列

Question

我有数字数组的散列，
我想将散列元素与普通数字合并。

例如。输入哈希

%HoA = (
A1 => [ "1", "2", "3", "4" ],
A2 => [ "5", "6", "7", "8" ],
A3 => [ "1", "9", "10", "11" ],
A4 => [ "12", "13", "14", "10" ],
);

输出哈希

%HoA_output = (
A1 => [ "1", "2", "3", "4", "9", "10", "11", "12", "13", "14" ],
A2 => [ "5", "6", "7", "8" ],
);

我需要一个解决方案，它可以快速评估一个散列，该散列具有近 50k 个键，每个数组中有 8 个数字。

问候

Answer 1

好的，从根本上讲 - 这不是一件容易的事，因为您确实需要相互检查每个元素以查看它们是否存在。我能想到的最好办法是通过合并列表来节省一些精力，并使用索引来跟踪欺骗。

我会这样处理：

use strict;
use warnings;
use Data::Dumper;


my %HoA = (
    A1 => [ "1",  "2",  "3",  "4" ],
    A2 => [ "5",  "6",  "7",  "8" ],
    A3 => [ "1",  "9",  "10", "11" ],
    A4 => [ "12", "13", "14", "10" ],
);

print Dumper \%HoA;

my %found;

sub merge_and_delete {
    my ( $first_key, $second_key ) = @_;
    print "Merging $first_key with $second_key\n";

    #use hash to remove dupes.
    my %elements;
    foreach my $element ( @{ $HoA{$first_key} }, @{ $HoA{$second_key} } )
    {
        $elements{$element}++;
        #update index - don't want to point it to an array we're deleting
        $found{$element} = $first_key;
    }
    #sorting for neatness - you might want to do a numeric sort instead, 
    #as by default %HoA contains text elements. 
    $HoA{$first_key} = [ sort keys %elements ];
    delete $HoA{$second_key};

}

foreach my $key ( sort keys %HoA ) {
    print "$key\n";
    foreach my $element ( sort @{ $HoA{$key} } ) {
        if ( $found{$element} ) {
            #this element is present in another list, we merge.
            print "$element found in $found{$element}\n";
            merge_and_delete( $found{$element}, $key );
            last;
        }
        else {
            #add this unique match to our index
            print "$element -> $key\n";
            $found{$element} = $key;
        }
    }
}

print Dumper \%HoA;

您迭代 %HoA 上的每个元素，并创建一个索引 table %found。这个索引 table 你用来检测一个元素是否已经被看到，然后触发一个 merge - 然后重建索引。不过，您可能需要注意大型数据集的内存消耗，因为您的索引可以增长到几乎与原始数据集一样大（如果存在足够的唯一元素）。

但是因为我们停止处理第一个匹配项，所以我们不再需要检查 every 个键，并且因为我们丢弃合并的数组并更新索引，所以我们不再需要进行全面比较。

Answer 2

这本质上是一个图形问题，您要在其中确定未连接分量的集合

此解决方案使用 Graph::Undirected::Components 模块，其唯一目的就是做到这一点。希望它对你的扩展数据集足够快，但你比我更容易确定

该程序创建一个图形，并将数据中每个键的边（连接）添加到其值的每个元素。然后，调用 connected_components returns 所有相互连接的不同节点集——包括键和值——

最终的 for 循环使用 List::MoreUtils 中的 part 再次从值中过滤键，基于节点值是否作为原始哈希数据中的键出现。（如果任何键值也可以出现在值中，您将不得不调整它。）然后第一个键和排序的值项一起用于在 %result 散列

use strict;
use warnings;

use Graph::Undirected::Components;
use List::Util 'minstr';
use List::MoreUtils 'part';

my %data = (
  A1 => [  1,  2,  3,  4 ],
  A2 => [  5,  6,  7,  8 ],
  A3 => [  1,  9, 10, 11 ],
  A4 => [ 12, 13, 14, 10 ],
);

my $graph =  Graph::Undirected::Components->new;

while ( my ($k, $v) = each %data ) {
  $graph->add_edge($k, $_) for @$v;
}

my %result;
for my $component ( $graph->connected_components ) {
  my @keys_vals = part { $data{$_} ? 0 : 1 } @$component;
  my $key       = minstr @{ $keys_vals[0] };
  my @values    = sort { $a <=> $b } @{ $keys_vals[1] };
  $result{$key} = \@values;
}

use Data::Dump;
dd \%result;

输出

{ A1 => [1 .. 4, 9 .. 14], A2 => [5 .. 8] }

Perl 合并数组的散列

Perl merge hash of array

arrays

perl

hash