更高效地处理Perl中AoA的笛卡尔积

Question

更高效地处理Perl中AoA的笛卡尔积

4

我正在计算一组中两个项目具有相同值的概率（类似于生日问题，http://en.wikipedia.org/wiki/Birthday_problem）。为此，我有24组三个值。该组中的每个项目将从24组中的每个组中选择一个值。我需要进行的计算是获取所有可能迭代这些值的乘积平方和。显然，这种迭代非常密集，因为必须进行迭代。在SE的帮助下，我现在已经得到：

#!perl;
use List::Util qw(reduce);
use Set::CrossProduct;

my @array = ( ## AoA containing values for caluculation, cut-down to allow benchmarking
#   [0.33, 0.33, 0.33],  x11 more in full set
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33],
    [0.33, 0.33, 0.33]
);

$val = 0;
my $iterator = Set::CrossProduct->new(\@array);
while (my $tuple = $iterator->get) {
    $freq = reduce { $a * $b } @$tuple;
    $val += ($freq*$freq);
}

$toprint=sprintf("%.50e", $val);
print $toprint;

基于上述代码中的13组子集的快速基准测试，我估计在我的个人电脑上完整运行这24组数据需要约45天。是否有任何建议可以提高性能？我不是寻求奇迹，只要它能在一周内完成，我就会很满意...

我对Perl没有情感投入，所以如果有明显的性能优势，可以尝试转向其他语言。

感谢您提前给出的任何建议。

编辑：添加了R标签，因为那可能是我能实现解决方案的第二佳选择。

- Reuben John Pengelly

4

使用“reduce”函数调用比仅使用“$tuple->[0] * $tuple->[1] * $tuple->[2] ...”要显著更加耗时。 - ysth

2

$freq =1; $freq *= $_ for @$tuple; 这行代码可以替代 $freq = reduce { $a * $b } @$tuple;。 - mpapec

@ysth 这将使其减少到42天，这是一个 显著的 改善，但仍然有一段路要走。 - Reuben John Pengelly

@mpapec：如果我能理解一个表达式珍珠，那我会感到惊讶的。然而，在这种情况下，我们可以简单地去掉[标签：pearl]标签，因为他只对[标签：performance]和[标签：cartesian-product]感兴趣，这可能是一个更客观的解决方案。 - Zeta

1

Perl 数值计算库 PDL 应该会有所帮助。 - ikegami

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zaid · Accepted Answer

这种类型的问题是我的强项。以下是我的想法：

先放一步

关键目标是减少评估结果所需的时间。你需要执行3^24 = 282+亿次计算，这是不可避免的。但是，可以采用一些技巧来轻松解决问题（注释也暗示了其中一些）：

并行化努力以减少所需时间
避免重复计算

并行计算

分而治之

解锁并行化的关键（如已经提到的）是将工作划分为更小的段。在此问题的背景下，元组需要被划分为更易处理的块。

如果我有一个四核处理器，我可能会将元组分成四个篮子：

my ( @baskets, $iter );
push @{ $baskets[ $iter++ % 4 ] }, $_ for $iterator->combinations;

这种功能很容易整合到一个子程序中：

sub segment {

  my $num_segments = shift;
  my ( @baskets, $iter );

  push @{ $baskets[ $iter++ % $num_segments ] }, $_ for @_;
  return @baskets;
}

my @jobs = segment( 4, $iterator->combinations );

并行启动

这里应该使用线程，因为对每个元组的计算很轻量级（请参阅perldoc perlthrtut了解如何在 Perl 中使用线程）：

use threads;                                            # imports threads module

sub work {                                              # What each thread will run

  my @tuples = @_;

  my $sum;
  for my $tuple ( @tuples ) {

    my $freq = 1;
    $freq *= $_ for @$tuple;
    $sum += $freq * $freq;
  }

  return $sum;
}

my @threads = map threads->new( \&work, @$_ ), @jobs;  # Create and launch threads
                                                       # with different tuple sets

my $grand_total;
$grand_total += $_->join for @threads;                 # Accumulate sub-totals

一箭双雕（乘以n）

免责声明：该解决方案的有效性随着不同概率数量的增加而提高。很难判断这个方案是否真的能缩短获得结果的时间。

假设计算保留两位小数，所有元组中只有100种可能的不同值（这就是生日悖论起作用的地方）。考虑到每个元组都包含24个概率，我认为两个元组产生相同频率的可能性很高（可以由统计学家证实这个假设）。下面我们通过一个简单的例子来说明，其中概率数量仅限于3个：

[ 0.33, 0.45, 0.22 ], # Tuple A
.
.
.
[ 0.45, 0.22, 0.33 ], # Tuple B

在这里，元组A和B将返回相同的$freq值。如果我们计算出这个$freq值会出现的次数，那么只需计算一次$freq并将其乘以“重复”元组的数量（从而一石多鸟）。

这将涉及检测重复的次数：

my %seen;
for my $tuple ( $iterator->combinations ) {

    my @sorted = sort @$tuple;
    my $tuple_as_string = "@sorted";

    $seen{$tuple_as_string}{count}++;

    next unless exists $seen{$tuple_as_string}{freq};

    my $freq = 1;
    $freq *= $_ for @$tuple;

    $seen{$tuple_as_string}{freq} = $freq;
}


my $grand_total;
for my $unique ( keys %seen ) {

    my $count = $seen{$unique}{count};
    my $freq = $seen{$unique}{freq};
    $grand_total += $count * $freq * $freq;
}

如果您希望将此想法与并行化相结合，我建议在并行化操作之前先识别“唯一”的元组。