厳選！Perl アルゴリズム実装に使える 25 の 標準ライブラリ【前編】

# はじめに
E869120さんがとてもいい記事を投稿されています。
[厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】](https://qiita.com/e869120/items/518297c6816adb67f9a5)

それの、**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.](https://qiita.com/drafts/ab266b53f85c181b369d/edit#17set)|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 で嵌った話、うまくいった話](https://qiita.com/superrino130/items/22941979e42c548d655c)* に実装例を投稿しました。
# 18.pair
```pairs.pl
use List::Util 'pairs';
```
新しめの標準モジュール pairs を使用します。
使用例は、[こちら](https://qiita.com/superrino130/items/eeec1fe627e934262042) をご覧ください。
使用例２は、[こちら](https://qiita.com/superrino130/items/21111248bb21a4dac0b2) をご覧ください。
# 19.tuple
Perl ではリファレンスを使用し、複雑なデータ構造を構成します。
使用例は、[こちら](https://qiita.com/superrino130/items/eeec1fe627e934262042) をご覧ください。
使用例２は、[こちら](https://qiita.com/superrino130/items/21111248bb21a4dac0b2) をご覧ください。
# 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](https://qiita.com/superrino130/items/c05671c5f59a75d72460)* に、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](https://qiita.com/superrino130/items/398cf549b6e3384a24c5)* に、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 機能【前編】](https://qiita.com/e869120/items/518297c6816adb67f9a5)
[perldoc -f 関数名](http://perldoc.jp/index/function)
[Yet Another Perl Problems 順列の生成](http://www.nct9.ne.jp/m_hiroi/linux/yapp01.html)

# 追記
bitset を修正しました
Perl には vec 関数がありました。