3

我正在研究一个 collat​​z 序列。我目前有一个for循环。

for my $num (1..1000000) {
    my $count = 1;
    for (my $i = $num; $i != 1; $count++) {
        $i = $i % 2 ? 3 * $i + 1 : $i / 2;
    }
}

然后我有一个简单的方法来计算循环的计数（完成理论需要很多次）。

if ($count > $max_length) {
    $max = $num;
    $max_length = $count;
}

我发现使用简单的理论可以更快地编写代码。

如果 n = 3，它将有这个序列 {3,10,5,16,8,4,2,1} [8] 如果 n = 6，它将有这个序列 {6,3,10,5,16 ,8,4,2,1} [9] 如果 n = 12，它将有这个序列 {12,6,3,10,5,16,8,4,2,1} [10]

所以我想保存 3 的结果，以便能够通过将 1 添加到计数等来计算 6 的结果。

我试图解决这个问题，我认为可以解决这个问题，但它实际上使我的程序需要多花 1 分钟才能完成，我现在有一个需要 1.49 秒而不是我以前的 30 秒的程序。

这就是我添加缓存的方式（可能是错误的）

以下是在for循环之外

my $cache = 0;
my $lengthcache = 0;

然后我有这段代码位于 $i 行之后，for 循环中的第 4 行

    $cache = $i;
    $lengthcache = $count;
    if  ($cache = $num*2) {
            $lengthcache++;
    }

我不想给我完整的答案，我只需要了解如何正确缓存而不会使代码变慢。

4

3 回答 3

3

你只想要长度，对吧？缓存序列并没有太多节省，而且内存使用量会很大。

编写一个返回长度的递归函数。

sub seq_len {
   my ($n) = @_;
   return 1 if $n == 1;
   return 1 + seq_len( $n % 2 ? 3 * $n + 1 : $n / 2 );
}

缓存结果。

my %cache;

sub seq_len {
   my ($n) = @_;
   return $cache{$n} if $cache{$n};
   return $cache{$n} = 1 if $n == 1;
   return $cache{$n} = 1 + seq_len( $n % 2 ? 3 * $n + 1 : $n / 2 );
}

不妨将终止条件移动到缓存中。

my %cache = ( 1 => 1 );

sub seq_len {
   my ($n) = @_;
   return $cache{$n} ||= 1 + seq_len( $n % 2 ? 3 * $n + 1 : $n / 2 );
}

递归不是必需的。你可以通过扁平化来加速它。这有点棘手，但您可以使用通常的技术[1]来完成。

my %cache = ( 1 => 1 );

sub seq_len {
   my ($n) = @_;

   my @to_cache;
   while (1) {
      if (my $length = $cache{$n}) {
         $cache{pop(@to_cache)} = ++$length while @to_cache;
         return $length;
      }

      push @to_cache, $n;
      $n = $n % 2 ? 3 * $n + 1 : $n / 2;
   }
}

确保它有效：

use strict;
use warnings;
use feature qw( say );
use List::Util qw( sum );

my $calculations;

   my %cache = ( 1 => 1 );

   sub seq_len {
      my ($n) = @_;

      my @to_cache;
      while (1) {
         if (my $length = $cache{$n}) {
            $cache{pop(@to_cache)} = ++$length while @to_cache;
            return $length;
         }

         push @to_cache, $n;
++$calculations;
         $n = $n % 2 ? 3 * $n + 1 : $n / 2;
      }
   }

my @results = map { seq_len($_) } 3,6,12;
say for @results;
say "$calculations calculations instead of " . (sum(@results)-@results);


8
9
10
9 calculations instead of 24

笔记：

  1. 要删除递归，

    1. 通过重新排列代码或传递有关返回时要做什么的信息，使函数尾递归。（前者在这里是不可能的。）
    2. 用循环加堆栈替换递归。
    3. 如果可能，消除堆栈。（这里不可能。）
    4. 清理结果。
于 2014-05-21T20:57:23.590 回答
1

将您的算法更改为缓存结果，以便它可以及早爆发：

use strict;
use warnings;

my @steps = (0,0);
my $max_steps = 0;
my $max_num = 0;

for my $num (2..1_000_000) {
    my $count = 0;
    my $i = $num;
    while ($i >= $num) {
        $i = $i % 2 ? 3 * $i + 1 : $i / 2;
        $count++;
    }
    $count += $steps[$i];
    $steps[$num] = $count;

    if ($max_steps < $count) {
        $max_steps = $count;
        $max_num = $num;
    }
}

print "$max_num takes $max_steps steps\n";

将我的处理时间从 37 秒更改为 2.5 秒。

为什么 2.5 秒就足够改进了？

我选择在数组中缓存是@steps因为对 from 的所有整数的处理很1容易N匹配数组的索引。与在保存相同数据的哈希中使用33Mvs的哈希相比，这也提供了内存优势。96M

正如所ikegami指出的，这确实意味着我不能缓存超过 100 万个周期的所有值，因为这会很快耗尽所有内存。例如，数字704,511有一个上升到 的循环56,991,483,520。

最后，这意味着我的方法确实会重新计算某些周期的一部分，但总体而言，由于不必在每一步都检查缓存，因此速度仍然有所提高。当我将其更改为每个周期使用哈希和缓存时，速度会降低到9.2secs.

my %steps = (1 => 0);

for my $num (2..1_000_000) {
    my @i = $num;
    while (! defined $steps{$i[-1]}) {
        push @i, $i[-1] % 2 ? 3 * $i[-1] + 1 : $i[-1] / 2;
    }
    my $count = $steps{pop @i};
    $steps{pop @i} = ++$count while (@i);
    #...

而当我使用memoizelike演示的时候Oesor，速度是23secs。

于 2014-05-21T22:36:22.857 回答
0

如果您将实现更改为递归函数，则可以使用 Memoize ( https://metacpan.org/pod/Memoize ) 将其包装以加快已经计算的响应。

use strict;
use warnings;
use feature qw/say/;
use Data::Printer;

use Memoize;

memoize('collatz');

for my $num (qw/3 6 12 1/) {
    my @series = collatz($num);
    p(@series);
    say "$num : " . scalar @series;
}

sub collatz {
    my($i) = @_;

    return $i if $i == 1;
    return ($i, collatz( $i % 2 ? 3 * $i + 1 : $i / 2 ));
}

输出

[
    [0] 3,
    [1] 10,
    [2] 5,
    [3] 16,
    [4] 8,
    [5] 4,
    [6] 2,
    [7] 1
]
3 : 8
[
    [0] 6,
    [1] 3,
    [2] 10,
    [3] 5,
    [4] 16,
    [5] 8,
    [6] 4,
    [7] 2,
    [8] 1
]
6 : 9
[
    [0] 12,
    [1] 6,
    [2] 3,
    [3] 10,
    [4] 5,
    [5] 16,
    [6] 8,
    [7] 4,
    [8] 2,
    [9] 1
]
12 : 10
[
    [0] 1
]
1 : 1
于 2014-05-21T20:54:14.253 回答