performance - 在 Perl 中高效处理所有可能的二维数组组合

Question

我有一个包含数字的二维数组。我正在尝试计算将每个子数组中的一个数字与其他每个子数组中的一个数字相乘的乘积；然后我需要对所有可能的组合执行此操作。

目的是我输入单个事件的频率文件，并获得这些事件的特定系列发生概率的输出，每组有一个事件。

我在上一个问题的帮助下拼凑了一些代码:

for my $aref ( getCartesian(@freq) ) {
    my $p = 1;
    foreach my $n (@$aref) {
        $p = $p * $n;
    }
    print "$p\n";
}


sub getCartesian {
    my @input = @_;
    my @ret = map [$_], @{ shift @input };

    for my $a2 (@input) {
        @ret = map {
            my $v = $_;
            map [@$v, $_], @$a2;
        }
        @ret;
    }
    return @ret;
}

其中@freq是数组的数组，例如:

@freq = [0.1, 0.2, 0.3,]
        [0.4, 0.5, 0.6,]
        [0.7, 0.8, 0.9,]; `and ~ 20 more sub arrays`

这对于一个小的测试文件来说效果很好，但是当我给它我所需的 24 个子数组输入，每个子数组有 3 个项目时，组合的生成显然过于密集，有 3^24 种可能性。我在一台有 22 GB RAM 的机器上运行它，它在任何输出前 4 分钟后达到最大值。

我的问题是，我如何修改代码，以便我可以为每个组合打印出 $p，而不必在内存中保存整组组合，这会杀死它。我认为时间将是计算的唯一限制因素，而不是资源。

编辑:没有包的基本 Perl 方法会很棒。遗憾的是，我没有 HPC 设施的管理员，

Answer 1

Set::CrossProduct让您遍历笛卡尔积，这样您就不必将所有内容都存储在内存中:

use List::Util qw(reduce);
use Set::CrossProduct;

my @array = (
    [0.1, 0.2, 0.3],
    [0.4, 0.5, 0.6],
    [0.7, 0.8, 0.9]
);

my $iterator = Set::CrossProduct->new(\@array);
while (my $tuple = $iterator->get) {
    say '(', join(', ', @$tuple), '): ', reduce { $a * $b } @$tuple;
}

输出:

(0.1, 0.4, 0.7): 0.028
(0.1, 0.4, 0.8): 0.032
(0.1, 0.4, 0.9): 0.036
(0.1, 0.5, 0.7): 0.035
(0.1, 0.5, 0.8): 0.04
(0.1, 0.5, 0.9): 0.045
(0.1, 0.6, 0.7): 0.042
(0.1, 0.6, 0.8): 0.048
(0.1, 0.6, 0.9): 0.054
(0.2, 0.4, 0.7): 0.056
(0.2, 0.4, 0.8): 0.064
(0.2, 0.4, 0.9): 0.072
(0.2, 0.5, 0.7): 0.07
(0.2, 0.5, 0.8): 0.08
(0.2, 0.5, 0.9): 0.09
(0.2, 0.6, 0.7): 0.084
(0.2, 0.6, 0.8): 0.096
(0.2, 0.6, 0.9): 0.108
(0.3, 0.4, 0.7): 0.084
(0.3, 0.4, 0.8): 0.096
(0.3, 0.4, 0.9): 0.108
(0.3, 0.5, 0.7): 0.105
(0.3, 0.5, 0.8): 0.12
(0.3, 0.5, 0.9): 0.135
(0.3, 0.6, 0.7): 0.126
(0.3, 0.6, 0.8): 0.144
(0.3, 0.6, 0.9): 0.162