はじめに
E869120さんがとてもいい記事を投稿されています。
厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】
それの、Perl 版です。
今回紹介する 25 個の(標準|非標準)関数
| 関数名 | 標準関数 | 例 | |
|---|---|---|---|
| 1. | 絶対値 abs | 〇 | abs |
| 2. | 三角関数 sin/cos/tan | 〇 | sin/cos |
| 3. | 文字列 string | 〇 | substr他 |
| 4. | 最大値・最小値 min/max | 〇 | List::Utilモジュール |
| 5. | 値の交換 swap | 〇 | リスト |
| 6. | 最大公約数 __gcd | × | 自作 |
| 7. | 乱数 rand | 〇 | rand |
| 8. | 時間計測 clock | 〇 | Time::HiResモジュール |
| 9. | 配列を逆順に並び替え reverse | 〇 | reverse |
| 10. | ソート sort | 〇 | sort |
| 11. | vector | 〇 | 配列 |
| 12. | stack | 〇 | 配列 |
| 13. | queue | 〇 | 配列 |
| 14. | priority_queue | × | 自作 |
| 15. | map | 〇 | ハッシュ |
| 16. | lower_bound | × | 自作 |
| 17. | set | 〇 | ハッシュ |
| 18. | pair | 〇 | List::Utilモジュール |
| 19. | tuple | × | 自作 |
| 20. | assert | 〇 | warn/die |
| 21. | count | 〇 | scalar/grep |
| 22. | find | 〇 | grep/map |
| 23. | next_permutation | × | 自作 |
| 24. | __builtin_popcount | × | grep |
| 25. | bitset | 〇 | vec |
1.絶対値 abs
abs.pl
print abs(-10); #=> 10
2.三角関数 sin/cos/tan
sin.pl
print sin(3.14159/6), "\n"; #=> 0.499
print cos(3.14159/6), "\n"; #=> 0.866
print sin(3.14159/6)/cos(3.14159/6), "\n"; # => 0.577
print 1/2, "\n"; #=> 0.5
print sqrt(3)/2, "\n"; #=> 0.866
print 1/sqrt(3), "\n"; # => 0.577
tan()は、sin()/cos()で代用
3.文字列 string
Perlの場合、スカラーと配列があって慣れが必要です。
スカラー
| プログラム | 説明 |
|---|---|
| my $s; | 変数 s を定義します |
| $s = S; | 文字列 S を入力します。 |
| print $s; | 文字列 S を出力します。 |
| substr(\$s, \$i, 1); | 文字列 S の i 文字目です。 |
| \$s .= T; | 文字列 S に文字列 T を連結します。 |
| \$s .= c; | 文字列 S に文字 c を連結します。 |
| length $s; | 文字列 S の長さを整数型で返す関数です。 |
| substr(\$s, \$l); | 文字列 S の l 文字目から最後の文字までの部分文字列を返す関数です。 |
| substr(\$s, \$l, \$r); | 文字列 S の l 文字目から l+r-1 文字目までの部分文字列を返す関数です。 |
配列
| プログラム | 説明 |
|---|---|
| my @s; | 配列 s を定義します |
| @s = split "", S; | 文字列 S を入力します。 |
| print @s; | 文字列 S を出力します。 |
| \$s[$i]; | 文字列 S の i 文字目です。 |
| join "", (@s, T); | 文字列 S に文字列 T を連結します。 |
| join "", (@s, c); | 文字列 S に文字 c を連結します。 |
| scalar @s; | 文字列 S の長さを整数型で返す関数です。 |
配列の i 文字目を取り出す場合、@s ではなく $s を使用します。
4.最大値・最小値 min/max
min.pl
use List::Util 'min';
use List::Util 'max';
print min(0, 3); #=> 0
print max(5, 9); #=> 9
@a = (0, 1, 2, 3, 4, 5);
print min(@a); #=> 0
print max(@a); #=> 5
5.値の交換 swap
swap.pl
my $a = "a";
my $b = "b";
print "$a $b\n"; # => a b
($a, $b) = ($b, $a);
print "$a $b\n"; # => b a
コメント欄で教えていただいた方法です。
置換用の変数で入れ替えるのが普通ですが、Perl はこんなことができるんですね。
6.最大公約数 __gcd
gcd.pl
sub gcd {
my ($x, $y) = @_;
while ($x>0 && $y>0) {
if ($y > $x) {
$y %= $x;
} else {
$x %= $y;
}
}
return $x if $x>0;
return $y if $y>0;
}
print gcd(6, 9); #=> 3
7.乱数 rand
rand.pl
print rand;
8.時間計測 clock
clock.pl
use Time::HiRes 'time';
sub func {
# 何かの処理
}
my $s = time;
func();
print time - $s, "\n"; #=> 経過時間
9. 配列を逆順に並び替え reverse
reverse.pl
@s = (0, 1, 3, 2, 4);
print reverse @s; #=> 42310
10.ソート sort
sort.pl
@s = (0, 3, 2, 11, 4);
print sort {$a <=> $b} @s; #=> 023411
print sort {$b <=> $a} @s; #=> 114320
print sort {$a cmp $b} @s; #=> 011234
print sort {$b cmp $a} @s; #=> 432110
数値の大小でソートする場合は <=>、辞書式にソートする場合は cmp を使用します。
11.vector
Perl の配列は動的な配列です。
| プログラム | 説明 |
|---|---|
| my @v; | 配列 v を定義します。 |
| push @v, x; | v の末尾に x を追加します。 |
| pop @v; | v の末尾の要素が取り除かれます。 |
| \$v[\$i] | v の先頭から数えて i 番目の要素にアクセスできます。 |
| scalar @v; | v に現在いくつ要素が入っているか、整数型で返します。 |
12.stack
Perl の配列は動的な配列で、vector としても stack としても使用可能です。
| プログラム | 説明 |
|---|---|
| my @s; | 配列 s を定義します。 |
| unshift @s, x; | 配列 s の一番上に要素 x を積みます。 |
| shift @s; | 配列 s の一番上の要素を取り除きます。 |
| \$s[0] | 配列 s の一番上の要素を返します。 |
| scalar @s; | 配列 s の要素数を整数で返す関数です。 |
| @s; | 空判定の関数は用意されていないようです。 |
empty.pl
unshift @s, 0;
print @s>0 ? "実" : "空", "\n"; #=>実
shift @s;
print @s>0 ? "実" : "空", "\n"; #=>空
13.queue
Perl の配列は動的な配列で、vector としても stack としても queue としても使用可能です。
| プログラム | 説明 |
|---|---|
| my @q; | 配列 q を定義します。 |
| push @q, x; | 配列 q の後尾に要素 x を追加します。 |
| shift @q; | 配列 q の先頭の要素を取り除きます。 |
| \$q[0] | 配列 q の先頭の要素を返します。 |
| scalar @q; | 配列 q の要素数を整数で返す関数です。 |
14.priority_queue
Perl に優先度付きキューは用意されていないようです。
- 配列に要素を追加
- 配列をソート
の手順で代用可能です。
15.map
Perl ではハッシュを使用します。
| プログラム | 説明 |
|---|---|
| my %h; | ハッシュ h を定義します。 |
| \$h{\$key} = x; | ハッシュ h に要素 x を代入します。 |
| \$h{\$key}; | ハッシュ h から要素 x を出力します。 |
| %h = (); | ハッシュ h を初期化します |
16.lower_bound
二分探索の例です。
bisearch.pl
use List::Util 'min';
use List::Util 'max';
sub bs {
my ($x, @t) = @_;
my $h = max(@t) + 1;
my $l = min(@t) - 1;
my $cnt = 1;
while ($h > $l) {
my $m = int(($h - $l)/2) + $l;
if ($x == $m) {
print "$x は $cnt 回目に見つかりました\n";
return;
} elsif ($x > $m) {
$l = $m;
} else {
$h = $m;
}
$cnt++;
}
}
my @s = (0..10000);
bs 321, @s;
# => 321 は 13 回目に見つかりました
17.set
Perl ではハッシュを使用します。
multisetへの対応は、プログラム例にて説明します。
| プログラム | 説明 |
|---|---|
| \$h{\$y} = x; | ハッシュ h に要素 x を代入します。 |
| delete \$h{\$y}; | ハッシュ h から要素 x を削除する。 |
| delete \$h{\$y}; | ハッシュ h からイテレーター y の要素を削除する。 |
| \%h = (); | ハッシュ h を空にする。 |
set.pl
my @list = ("a", "c", "b", "b", "a", "d", "b");
my %h;
$h{$_}++ for @list;
for my $key (sort keys %h) {
print "$key $h{$key}\n";
}
# => a 2
# => b 3
# => c 1
# => d 1
delete $h{"c"};
for my $key (sort keys %h) {
print "$key $h{$key}\n";
}
# => a 2
# => b 3
# => d 1
ハッシュのkeys側でユニークな set の集合とし、value側でその出現回数を記録することにより multiset に対応します。
Perl AtCoder ABC 159 D で嵌った話、うまくいった話 に実装例を投稿しました。
18.pair
pairs.pl
use List::Util 'pairs';
新しめの標準モジュール pairs を使用します。
使用例は、こちら をご覧ください。
使用例２は、こちら をご覧ください。
19.tuple
Perl ではリファレンスを使用し、複雑なデータ構造を構成します。
使用例は、こちら をご覧ください。
使用例２は、こちら をご覧ください。
20.assert
assert.pl
my $n = 3000;
warn "n over 2000" if $n > 2000; # => n over 2000 at assert.pl line 2.
print $n, "\n"; # => 3000
die "n over 2000" if $n > 2000; # => n over 2000 at assert.pl line 4.(終了コード: 255)
print $n, "\n"; # =>
指定した条件でコメントを出力します。
そのまま継続する場合は warn、警告終了する場合は die を使用します。
21.count
count.pl
my @list = (1, 2, 3, 4, 1, 2, 3, 1, 2, 1);
print scalar grep {$_ == 1} @list; # => 4 1の個数
print scalar grep {$_ == 2} @list; # => 3 2の個数
print scalar grep {$_ == 1} @list[1..5]; # => 1 配列1～5の間の1の個数
print scalar grep {$_ == 2} @list[1..5]; # => 2 配列1～5の間の2の個数
配列のスライスを使用して部分配列を取得し、条件に適合した要素数を出力します。
22.find
find.pl
my @list = (1, 2, 3, 4, 1, 2, 3, 1, 2, 1);
print index join("", @list), 3; # => 2 最初に3が現れるのは2番目
print index join("", @list), 5; # => -1 5は含まれないので-1
print index join("", @list[5..9]), 3; # => 1 配列5～9で最初に3が現れるのは1番目
print index join("", @list[5..9]), 4; # => -1 配列5～9に4は含まれないので-1
23.next_permutation
next_perm.pl
my @table;
my @perm;
my @nperm;
sub next_perm {
my $n = shift;
for (my $i = 1; $i <= $n; $i++) {
unless ($table[$i]) {
push @perm, $i;
if ($n == @perm) {
@nperm = (@nperm, @perm, "\n");
} else {
$table[$i] = 1;
next_perm($n);
$table[$i] = 0;
}
pop @perm;
}
}
}
next_perm(3);
print @nperm;
# => 123
# => 132
# => 213
# => 231
# => 312
# => 321
順列を生成し、それを利用して経路の確認を行います。
Perl による next_permutation の実装と AGC022 A に、next_permutation の実装例を投稿しました。
24.__builtin_popcount
bp.pl
sub builtin_popcount {
return scalar grep {$_ == 1} split ("", sprintf "%b", shift);
}
print builtin_popcount 42; # => 3
Ruby と Perl と Java で解く AtCoder ABC 128 C に、builtin_popcount の実装例を投稿しました。
25.bitset
| プログラム | 説明 |
|---|---|
| \$a = (\$a ^ \$b) など | int 型などと同じように、ビット演算（and, or, xor）をすることができます。 |
| vec(\$a, x, 1) = 1 | a の $x$ 桁目（$2^x$ の位）を 1 に変更します。 |
| vec(\$a, x, 1) = 0 | a の $x$ 桁目（$2^x$ の位）を 0 に変更します。 |
| vec(\$a, i, 1) | 配列と同様、a の $i$ 桁目（$2^i$ の位）にアクセスすることができます。a[i] は必ず 0 か 1 です。 |
bitset.pl
vec($b, 0, 8) = 2 ** 8 - 1;
for ($i = 7; $i >= 0; $i--) {
print vec($b, $i, 1); # 11111111
}
vec($b, 2, 1) = 0;
for ($i = 7; $i >= 0; $i--) {
print vec($b, $i, 1); # 11111011
}
vec($a, 0, 8) = 2 ** 5 - 2;
for ($i = 7; $i >= 0; $i--) {
print vec($a, $i, 1); # 00011110
}
for ($i = 7; $i >= 0; $i--) {
print vec($a | $b, $i, 1); # 11111111
}
for ($i = 7; $i >= 0; $i--) {
print vec($a & $b, $i, 1); # 00011010
}
for ($i = 7; $i >= 0; $i--) {
print vec($a ^ $b, $i, 1); # 11100101
}
まとめ
- E869120さんの情熱が凄い
- C++のチート具合が凄い
- Perlもそれなりに凄い
- 記事の後半グダグダ
- 後編はない
参照したサイト
厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】
perldoc -f 関数名
Yet Another Perl Problems 順列の生成
追記
bitset を修正しました
Perl には vec 関数がありました。