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

我们退一步吧

这里的关键目标是减少评估结果所花费的时间.您需要执行3 ^ 24 = 2820亿次评估,这是无法避免的.但是,有一些技巧可以用来解决问题的更轻松的工作(评论也提到其中一些)：

>平行努力以减少所需的时间
>避免重复计算

并行计算

分而治之

解锁并行化的关键(如已经提到的)是将工作分成更小的部分.在这个问题的上下文中,元组需要被分成更易于管理的块.

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

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 );

并行发射

由于每元组计算是轻量级的,因此线程的使用应该足够了(有关如何在Perl中使用线程的更多信息,请参阅perldoc perlthrtut)：

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

用1石头杀死n只鸟(乘以n)

免责声明：随着离散概率数量的增加,此解决方案的有效性也会增加.要判断这个提案是否会真正缩短获得结果的时间并不容易.

假设2 d.p.,所有元组中只能有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;
}

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