0

私はこの些細なspoj問題をperlで解決していました。だから私はこの解決策を思いついた：

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 は通常コンパイルされているということも、あなたが気付いていないことの 1 つです。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 に答える