perl - 试图预测 future 的结果，collat​​z，Perl

Question

我正在研究一个 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;
}

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

If n = 3, it would have this sequence {3,10,5,16,8,4,2,1} [8] If n = 6, it would have this sequence {6,3,10,5,16,8,4,2,1} [9] If n = 12, it would have this sequence {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++;
    }

我不想要完整的答案，我只需要了解如何在不使代码变慢的情况下正确缓存。

Answer 1

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

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

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. 清理结果。