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

7uhlpewt 于 2023-03-13 发布在 Perl

关注(0)|答案(2)|浏览(173)

我编写了下面的Perl代码，为任意两个输入列表返回一个类似交集的列表，条件是$returnintersection为真，否则，它将返回任意一个公共元素，如果没有，则返回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;
}

perl

来源：https://stackoverflow.com/questions/17393643/improve-performance-of-perl-code-that-finds-custom-intersection-of-two-lists

2条答案

按热度按时间

hyrbngr71#

在我读到这篇文章时，你的实现并没有从区分小集合和大集合中获益，即便如此，真正重要的是哪个集合有最多的星号元素，因为它们不能用线性复杂度来处理。
首先，看看不匹配的可能组合：

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来进行匹配。

赞(0）回复(0）举报 2023-03-13

g9icjywg2#

不知道这有多快，请用你的测试数据计时！
它的工作原理是将每个输入列表转换为regexp，如下所示

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

然后grep将regexp应用于另一个列表，另一个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*'], 
));

赞(0）回复(0）举报 2023-03-13

我来回答

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

2条答案

相关问题

热门标签

最新问答