regex - 提高查找两个列表的自定义交集的 perl 代码的性能

Question

我编写了以下 perl 代码来为任意两个输入列表返回一个类似交集的列表，前提是 $returnintersection 为真。否则返回任意一个公共(public)元素，没有则返回0。

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

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

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

我想知道我是否可以用一种性能更好的方式来编写它？我敢肯定这里的算法不是最好的。任何有助于降低其复杂性的东西都将受到赞赏!它的性能至关重要，因为它是一个非常普遍的例程。 (性能 => 速度，假设任一列表都可以包含 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;
}

Answer 1

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

首先，看看不匹配的可能组合:

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_1 与 @star_2 的匹配，但我不确定这是否有意。

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

如果您想进一步优化，可以使用 Tries对其中一个集合中的所有元素进行匹配。