0

我正在用 perl 解决这个微不足道的 spoj 问题。所以我想出了这个解决方案：

while ("0 0 0\n" ne ($string = <STDIN>)) {
  my @a = split ' ', $string;
  $a1 = $a[0];
  $a2 = $a[1];
  $a3 = $a[2];

  if($a2 - $a1 == $a3 - $a2) {
    $c  = $a2 - $a1;
    $a4 = $a3 + $c;
    print("AP ", $a4);
  }
  else {
    $c  = $a2 / $a1;
    $a4 = $a3 * $c;
    print("GP ", $a4);
  }

  print "\n";
}

令我惊讶的是，它超过了时间限制。当我在 C 中尝试同样的事情时，它以最短的运行时间成功运行。这是 C 版本：

#include <stdio.h>

int main()
{
  int a1, a2, a3, a4, c;
  while (1) {
    scanf("%d %d %d", &a1, &a2, &a3);
    if (a1 == 0 && a2 == 0 && a3 == 0) break;
    if (a2 - a1 == a3 - a2) {
      c  = a2 - a1;
      a4 = a3 + c;
      printf("AP %d\n", a4);
    }
    else {
      c  = a2 / a1;
      a4 = a3 * c;
      printf("GP %d\n", a4);
    }
  }
  return 0;
}

那么，请您告诉我：

当涉及到这个问题时，perl 真的比 C 慢那么多（至少 200 倍）吗？我怀疑这与输入和使用的数组等高级结构有关，或者我的代码中可能存在导致程序停止的错误。

4

1 回答 1

6

您的基准测试存在各种问题：

  • 这些程序不是绝对等价的。
  • 至少您的 Perl 代码是单一的（您甚至没有声明所有变量！）

但最重要的是：

  • 这个基准是基于 IO 的。
  • 如果输入不大，启动时间也很重要。

您所做的计算绝对便宜，最昂贵的部分是读取和扫描输入。毫不奇怪，这里的最小 C 将比更高级别的 PerlIO 系统更快。

您没有意识到的另一件事是 Perl 是一种解释语言，而 C 通常是编译的。在 Perl 的情况下，实际上有一个 C 程序查看某些数据结构（操作码）并根据某些标志进行加法、乘法、分支或比较。Perl 变量是标量，实际上是一个SV*- 指向 SV 结构的指针。这些结构比int. 每次执行 Perl 程序时，perl解释器都会将整个源代码解析并编译为操作码。

另一方面，C 编译为比操作码更有效的机器码。这是在执行之前完成的，因此编译时间不计入此基准。由于这个原因，启动会更快。C 可以优化为使用寄存器而不是堆上的位置，这使得像ints 这样的简单数据结构更快。C 标准库中的 IO 系统比 Perl 的复杂系统（解码层、缓冲）要简单得多。总而言之，C 的间接层级比 Perl 少。

因为 perl 是一个 C 程序，这些间接级别使 Perl 慢了大约 100 倍。数学密集型基准的差距扩大了（SV 比 int 更昂贵），但对于像index和正则表达式这样的字符串操作更接近。

作为记录，这是您的 Perl 代码的惯用版本。不，它不会跑得更快。

while (<>) {
  last if $_ eq "0 0 0\n";
  my ($a1, $a2, $a3) = split;

  if($a2 - $a1 == $a3 - $a2) {
    my $a4 = $a3 + $a2 - $a1;
    print "AP $a4\n";
  }
  else {
    my $a4 = $a3 * $a2 / $a1;
    print "GP $a4\n";
  }
}
于 2013-10-07T21:39:26.877 回答