3

如果 $returnintersection 为真，我编写了以下 perl 代码来为任何两个输入列表返回一个类似交集的列表。否则，它将返回任何一个公共元素，如果没有，则返回 0。

通过类似交叉点，我指的是通配符匹配 - 一个列表中的 123* 将匹配另一个列表中的 12345。

这是输入和相应输出的示例。

getintersection (
 ['123*', '999', 'V890', '871'],
 ['10001', '8789', '999', '1234', 'V89*'], 
 1 
)
will return
('999', 'V890', '1234')

我想知道我是否可以以一种表现更好的方式编写它？我敢肯定，ere 算法并不是最好的。任何有助于降低其复杂性的东西都将不胜感激！它的性能至关重要，因为它是一个非常常见的例程。（性能 => 速度，假设任一列表都可以包含 1 到 3000 个元素）

代码 -

    sub getintersection {
        my ($l1, $l2, $returnintersection) = @_;
        if (!$l1 || !$l2) {
                return $returnintersection ? undef : 0;
        }
        my ($small, $large);
        if (scalar @$l1 > scalar @$l2 ) {
                ($small, $large) = ($l2, $l1);
        }
        else {
                ($small, $large) = ($l1, $l2);
        }

        my (%lhash, %l_starred, %s_starred, @intersection);
        foreach my $l (@$large) {
                $lhash{$l} = 1;
                if ($l =~ m/^(.+)\*$/) {
                        $l_starred{$1} = 1;
                }
        }
        foreach my $s (@$small) {
                if ($lhash{$s}) {
                        return $s if (!$returnintersection);
                        push @intersection, $s;
                }
                else {
                        foreach my $k (keys %l_starred) {
                                if ($s =~ /^$k/) {
                                        return $s if (!$returnintersection);
                                        push @intersection, $s;
                                }
                        }
                }
                if ($s =~ m/^(.+)\*$/) {
                        $s_starred{$s} = 1;
                }
        }
        foreach my $s (keys %s_starred) {
                foreach my $l (@$large) {
                        if ($l =~ /^$s/) {
                                return $l if (!$returnintersection);
                                push @intersection, $l;
                        }
                }
        }

        return $returnintersection ? @intersection : scalar @intersection;
}
4

2 回答 2

3

当我读到它时，您的实现并没有从区分小集和大集中受益。即便如此，真正重要的是哪个集合具有最多的星号元素，因为它们无法以线性复杂度处理。

首先，看一下不匹配的可能组合：

Set 1       | Set 2
Normal      | None
Starred     | None
None        | Normal
None        | Starred

那么可能的匹配组合：

Normal      | Normal
Starred     | Normal
Normal      | Starred
Starred     | Starred

很明显，任何可以使用哈希查找匹配的东西都应该首先完成，因为复杂度是线性的，所以算法的第一部分应该是：

for all elements in set1
    if element is normal, put in %normal_1_lookup
    otherwise put in @star_1
for all elements in set2
    if element is normal, put in %normal_2_lookup
    otherwise put in @star_2

for intersection of %normal_1_lookup, %normal_2_lookup
    put element in result
    delete element from %normal_1_lookup and %normal_2_lookup

您可以通过将计算交集的最后一个循环折叠到计算 的第二个循环中来优化这一点%normal_2_lookup，但我这样写是为了使其更具可读性。

现在所有的轻量级都已经完成，已经匹配的元素已被删除，您无需迭代任何内容即可知道哪些元素是星星，哪些不是。

for all elements is @star_1
    for all elements in %normal_2_lookup
        if star_1 element matches normal_2 element
            put normal_2 element in result set
            delete normal_2 element from %normal_2_lookup

现在重复切换两组。

最后，您可以添加匹配的@star_1against @star_2，但我不确定这是否是有意的。

这应该将复杂性降低到 o(s_1 * n_2 + s_2 * n_1) （如果要匹配两个集合中的星元素，请添加 s_1 * s_2），而不是看起来是 o(n_1 * n_2)。

如果您想进一步优化，您可以在其中一组中的所有元素上使用Tries来进行匹配。

于 2013-06-30T19:45:16.503 回答
1

不知道这速度有多快，请用你的测试数据来计时！

它通过将每个输入列表转换为这样的正则表达式来工作

^99$|^23$|^34$|^6$|^1$|^451$

然后 agrep将正则表达式应用于另一个列表。另一个 grep 删除重复项，然后将重复列表的键作为答案返回

use Data::Dumper;
sub fixedra {
    my $l=shift;
    my $retval = join("|",map { qq#^$_\$#; } @$l);
    $retval =~ s/\*/.*/g;  #convert regexp to work as requirements
    return $retval;
    }



sub getintersection {
    my $a=shift;
    my $b=shift;
    my $ra=fixedra($a);
    my $rb=fixedra($b);
    my %rethash=();
    grep($rethash{$_}++, grep(/$ra/, @$b), grep(/$rb/, @$a));
    return [keys %rethash];
}

print Dumper(getintersection (
 ['123*', '999', 'V890', '871'],
 ['10001', '8789', '999', '1234', 'V89*'], 
));
于 2013-06-30T20:12:38.427 回答