はじめに

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 関数がありました。