比较两个哈希中的所有元素更有效

Question

我在perl中有两个哈希值,每个哈希值由大约250,000个元素组成.我必须将两个哈希值中的每个元素相互比较,并对彼此相等的元素执行另一个操作.我有以下代码,它进行了大约600亿次比较,因此需要很长时间才能完成:

foreach $key1 (keys %large_hash_1)
    {
    foreach $key2 (keys %large_hash_2)
        {
        if($some_other_var{$key1} == $some_other_var{$key2}) # so actually I compare another hash variable, using the keys from %large_hash_1 and %large_hash_2
             {
             # I print some stuff here to an output file using the $key1 and $key2 variables
             }
        }
    }

有没有办法更快地完成这项工作？

Answer 1

大概.看起来你可以将问题重新表述为

查找键的所有对K1和K2这样的:

• $some_other_hash{K1} == $some_other_hash{K2}
• K1存在于%hash1和K2存在于%hash2

所以让我们尝试一种方法,首先找到第一个条件的解,然后看看它们是否满足第二个条件.迭代所有键对是O(n ²)但是我们已经有了一种策略来查找快速映射到相同哈希值的键:使用另一个哈希值!

让我们构建一个"反向哈希",%some_other_hash以便$hash7{VAL}生成所有键的列表,%some_other_hash以便$some_other_hash{KEY} == VAL:

push @{$hash7{ $some_other_hash{$_} }, $_ for keys %some_other_hash;

这是O(n)操作.接下来,我们需要找到映射到多个键的值.

foreach my $v (keys %hash7) {
    @k = @{$hash7{$v}};
    next if @k < 2;
    ...
}

如果找到这样的值,请检查某些键是否在,%hash1以及是否存在某些键%hash2.

foreach my $v (keys %hash7) {
    @k = @{$hash7{$v}};
    next if @k < 2;
    @k1 = grep { exists $hash1{$_} } @k;
    @k2 = grep { exists $hash2{$_} } @k;
    if (@k1 && @k2) {
        foreach my $k1 (@k1) {
            foreach my $k2 (@k2) {
                print "$k1 from %hash1 and $k2 from %hash2 ",
                      "have the same value $v in %some_other_hash\n";
                ...
            }
        }
    }
}

最坏的情况是,通常会找到%some_other_hash由多个键映射的值,此循环为O(mn).根据您的数据,此搜索可能比在%hash1和中迭代所有键对快得多%hash2.