はじめに
Perl で学ぶ逆元の３ ABC 151 E が解けた！ にて BigInt が遅いことが分かりました。
そこで、色々とベンチマークを取ってみました。
AtCoder
お世話になっています AtCoder：競技プログラミングコンテストを開催する国内最大のサイト
| 現テスト環境 | 新テスト環境(予定) |
|---|---|
| Perl(v5.18.2) | Perl(v5.26.1) |
ループ比較
loop.pl
use strict;
use warnings;
use Benchmark qw(:all);
my $result = timethese(100, {
loop1 => sub {
my $a;
for (my $i=0; $i<1e5; $i++) {
$a++;
}
},
loop2 => sub {
my $a;
for my $i (1..1e5) {
$a++;
}
},
loop3 => sub {
my $i = 0;
my $a;
while ($i < 1e5) {
$a++;
$i++;
}
},
loop4 => sub {
my $i = 0;
my $a;
while (1) {
$a++;
$i++;
last unless $i < 1e5;
}
},
});
cmpthese $result;
Perl(v5.18.2)
Rate loop3 loop1 loop4 loop2
loop3 152/s -- -12% -14% -45%
loop1 172/s 14% -- -2% -38%
loop4 175/s 16% 2% -- -37%
loop2 278/s 83% 61% 58% --
Perl(v5.26.1)
Rate loop4 loop3 loop1 loop2
loop4 278/s -- -6% -22% -44%
loop3 294/s 6% -- -18% -41%
loop1 357/s 29% 21% -- -29%
loop2 500/s 80% 70% 40% --
loop2: for my $i (1..1e5)が一番速い結果となりました。
whileループは遅い傾向となりました。
また、AtCoderの新テスト環境(予定)は現テスト環境に比べ2倍程速くなっています。
問題のBigInt
bigint.pl
use strict;
use warnings;
use Benchmark qw(:all);
use Math::BigInt;
my $result = timethese(10, {
loop5 => sub {
my $a = Math::BigInt->new(0);
for my $i (1..1e5) {
$a++;
}
},
loop6 => sub {
my $a = Math::BigInt->new(0);
for my $i (1..1e5) {
$a = $a->binc();
}
},
loop2 => sub {
my $a;
for my $i (1..1e5) {
$a++;
}
},
});
cmpthese $result;
テスト回数10、あっ察し
Perl(v5.18.2)
Rate loop5 loop6 loop2
loop5 1.99/s -- -12% -99%
loop6 2.27/s 14% -- -99%
loop2 333/s 16667% 14600% --
Perl(v5.26.1)
Rate loop5 loop6 loop2
loop5 5.05/s -- -4% -99%
loop6 5.24/s 4% -- -99%
loop2 500/s 9800% 9450% --
BigInt を使用すると100倍遅い結果となりました。
また、AtCoderの新テスト環境(予定)は現テスト環境に比べ2倍程速くなっています。
まとめ
- AtCoder さんありがとう
- 新テスト環境(予定)に期待
- BigInt は100倍遅い
- for ループ推奨