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

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

それの、**Ruby** 版です。
# 今回紹介する 25 個のメソッド
||メソッド|標準モジュール|例|
|---:|:---:|:---:|:---:|
|1.|絶対値 abs|〇|abs|
|2.|三角関数 sin/cos/tan|〇|Mathモジュール|
|3.|文字列 string|〇|size他|
|4.|最大値・最小値 min/max|〇|min/max|
|5.|値の交換 swap|〇|リスト|
|6.|最大公約数 gcd|〇|gcd|
|7.|乱数 rand|〇|rand|
|8.|時間計測 clock|〇|Timeモジュール|
|9.|配列を逆順に並び替え reverse|〇|reverse|
|10.|ソート sort|〇|sort|
|11.|vector|〇|配列|
|12.|stack|〇|配列|
|13.|queue|〇|配列|
|14.|priority_queue|×|自作|
|15.|map|〇|ハッシュ|
|16.|lower_bound|〇|bsearch|
|17.|set|〇|ハッシュ|
|18.|pair|〇|リファレンス|
|19.|tuple|〇|リファレンス|
|20.|assert|〇|raise|
|21.|count|〇|count|
|22.|find|〇|index|
|23.|next_permutation|〇|permutation|
|24.|__builtin_popcount|〇|to_s(2).count("1")|
|25.|bitset|×|自作|

# 1.絶対値 abs
```abs.rb
puts -10.abs      #=> 10
puts (2 - 8).abs  # => 6
```
# 2.三角関数 sin/cos/tan
```sin.rb
puts Math.sin(Math::PI / 3) # => 0.866
puts Math.cos(Math::PI / 3) # => 0.500
puts Math.tan(Math::PI / 3) # => 1.732
```
## 追記
```include.rb
include Math
p sin(PI / 3) # => 0.866
p cos(PI / 3) # => 0.500
p tan(PI / 3) # => 1.732
```
`include`すると省略できて便利です

三角関数の実装例は、*[こちら](https://qiita.com/superrino130/items/0889d314dd01f6a9a6ea)*を参照してください。

# 3.文字列 string
|プログラム|説明|
|:--|:--|
|s = ""|変数 s を定義します|
|s = S|文字列 S を入力します。|
|puts s|文字列 S を出力します。|
|s[i]|文字列 S の i 文字目です。|
|s << T|文字列 S に文字列 T を連結します。|
|s.size|文字列 S の長さを整数型で返す関数です。|
|s[l..-1]|文字列 S の l 文字目から最後の文字までの部分文字列を返す関数です。|
|s[l, r]|文字列 S の l 文字目から r 文字までの部分文字列を返す関数です。|
```String.rb
s = "abcde"
puts s            # => abcde
puts s[1]         # => b
puts s << "fg"     # => abcdefg
puts s.size       # => 5
puts s[1..-1]     # => bcde
puts s[1, 3]      # => bcd
```
# 4.最大値・最小値 min/max
```min.rb
puts [0, 3].min # => 0
puts [5, 9].max # => 9

a = [0, 1, 2, 3, 4, 5]
puts a.min # => 0
puts a.max # => 5
```
# 5.値の交換 swap
```swap.rb
a = "a"
b = "b"
puts "#{a} #{b}" # => a b
a, b = b, a
puts "#{a} #{b}" # => b a
```
# 6.最大公約数 __gcd
```gcd.rb
puts 6.gcd(9) #=> 3
```
# 7.乱数 rand
```rand.rb
puts rand       # => 1未満の乱数
puts rand(1..6) # => 1~6の整数の乱数（サイコロ）
```
# 8.時間計測 clock
```clock.rb
def func
  # 何かの処理
end
t = Time.now
func
puts Time.now - t # => 経過時間
```
# 9. 配列を逆順に並び替え reverse
```reverse.rb
s = [0, 1, 3, 2, 4];

puts "#{s.reverse}" #=> [4, 2, 3, 1, 0]
```
# 10.ソート sort
```sort.rb
s = [0, 3, 2, 11, 4]

p s.sort                          # => [0, 2, 3, 4, 11]
p s.sort {|a, b| b<=>a}           # => [11, 4, 3, 2, 0]
p s.sort {|a, b| a.to_s<=>b.to_s} # => [0, 11, 2, 3, 4] 辞書昇順
p s.sort {|a, b| b.to_s<=>a.to_s} # => [4, 3, 2, 11, 0] 辞書降順
```
sort に加え sort_by もあります
## 追記
```sort_by.rb
s = [0, 3, 2, 11, 4]

p s.sort_by { _1 }              # => [0, 2, 3, 4, 11]
p s.sort_by { -_1 }             # => [11, 4, 3, 2, 0]
p s.sort_by { _1.to_s }         # => [0, 11, 2, 3, 4] 辞書昇順
p s.sort_by { _1.to_s }.reverse # => [4, 3, 2, 11, 0] 辞書降順
```
AtCoder の現行バージョン`2.7.1`では番号指定パラメータを使用することも可能です。
sort_by は sort に比べ高速であることが知られています。
# 11.vector
Ruby の配列は動的な配列です。

|プログラム|説明|
|:--|:--|
|v = []|配列 v を定義します。|
|v.push(x)|v の末尾に x を追加します。|
|v.pop|v の末尾の要素が取り除かれます。|
|v[i]|v の先頭から数えて i 番目の要素にアクセスできます。|
|v.size|v に現在いくつ要素が入っているか、整数型で返します。|
# 12.stack
Ruby の配列は動的な配列で、vector としても stack としても使用可能です。

|プログラム|説明|
|:--|:--|
|s = []|配列 s を定義します。|
|s.unshift(x)|配列 s の一番上に要素 x を積みます。|
|s.shift|配列 s の一番上の要素を取り除きます。|
|s[0]|配列 s の一番上の要素を返します。|
|s.size|配列 s の要素数を整数で返す関数です。|
|s.empty?|スタック s の要素数が 0 である場合 true、1 以上である場合 false を返す関数です。|
# 13.queue
Ruby の配列は動的な配列で、vector としても stack としても queue としても使用可能です。

|プログラム|説明|
|:--|:--|
|q = []|配列 q を定義します。|
|q.push(x)|配列 q の後尾に要素 x を追加します。|
|q.shift|配列 q の先頭の要素を取り除きます。|
|q[0]|配列 q の先頭の要素を返します。|
|q.size|配列 q の要素数を整数で返す関数です。|
# 14.priority_queue
優先度付きキューの実装例は、*[こちら](https://qiita.com/superrino130/items/a4795aa0d03090f06d8d)*を参照してください。
優先度付きキューの実装例２は、*[こちら](https://qiita.com/superrino130/items/6c8d56203ff4379f5267)*を参照してください。
ac-library-rb の優先度付きキューの実装例３は、*[こちら](https://qiita.com/superrino130/items/1795c31e1567a7ecdbe5)*を参照してください。

# 15.map
Ruby ではハッシュを使用します。

|プログラム|説明|
|:--|:--|
|h = {}|ハッシュ h を定義します。|
|h[key] = x|ハッシュ h に要素 x を代入します。|
|h[key]|ハッシュ h から要素 x を出力します。|
|h.clear|ハッシュ h を初期化します|

# 16.lower_bound
ソート済みの配列 a に対し、計算量 *O(log N)* で検索を行います。

```bsearch.rb
a = [2, 3, 4, 6, 9, 10]
puts a.bsearch {|x| x > 7}                # => 9 要素
puts a.bsearch_index {|x| x > 7}          # => 4 インデックス
puts a[1..5].bsearch {|x| x > 7}          # => 9 要素
puts a[1..5].bsearch_index {|x| x > 7}    # => 3 インデックス
```
二分探索の実装例は、*[こちら](https://qiita.com/superrino130/items/e4f91cc08028137280c6)*を参照してください。
# 17.set
Ruby では Set クラスもありますがハッシュを使用します。
multiset への対応は、プログラム例にて説明します。

|プログラム|説明|
|:--|:--|
|h[y] = x|ハッシュ h に要素 x を代入します。|
|h.delete(y)|ハッシュ h から要素 x を削除する。|
|h.delete(y)|ハッシュ h からイテレーター y の要素を削除する。|
|h.clear|ハッシュ h を空にする。|
```set.rb
list = ["a", "c", "b", "b", "a", "d", "b"]

h = Hash.new(0)
list.each do |a|
  h[a] += 1
end
puts h # => {"a"=>2, "c"=>1, "b"=>3, "d"=>1}

h.delete("c")
puts h # => {"a"=>2, "b"=>3, "d"=>1}
```
ハッシュの keys 側でユニークな set の集合とし、values 側でその出現回数を記録することにより multiset に対応します。
## 追記
```tally.rb
list = ["a", "c", "b", "b", "a", "d", "b"]

h = list.tally
puts h # => {"a"=>2, "c"=>1, "b"=>3, "d"=>1}

h.delete("c")
puts h # => {"a"=>2, "b"=>3, "d"=>1}
```
`Ruby (2.7.1)`では`tally`で同様の処理が可能です。
# 18.pair
リファレンスの実装例は、*[こちら](https://qiita.com/superrino130/items/e01284f926f45be5427b)*を参照してください。
リファレンスの実装例２は、*[こちら](https://qiita.com/superrino130/items/21111248bb21a4dac0b2)*を参照してください。
# 19.tuple
リファレンスの実装例は、*[こちら](https://qiita.com/superrino130/items/e01284f926f45be5427b)*を参照してください。
リファレンスの実装例２は、*[こちら](https://qiita.com/superrino130/items/21111248bb21a4dac0b2)*を参照してください。
# 20.assert
```assert.rb
1.upto(100) do |i|
  raise "i over 9" if i > 9 # => i over 9 (RuntimeError)
end
```
指定した条件でコメントを出力し、警告終了します。
**【追記】**
assert もいいけど [warn もいいという話](https://qiita.com/superrino130/items/951ce53ada31f6dfe124)です。
# 21.count
```count.rb
list = [1, 2, 3, 4, 1, 2, 3, 1, 2, 1]

puts list.count(1)       # => 4 1の個数
puts list.count(2)       # => 3 2の個数
puts list[1..5].count(1) # => 1 配列1～5の間の1の個数
puts list[1..5].count(2) # => 2 配列1～5の間の2の個数
```
# 22.find
```find.rb
list = [1, 2, 3, 4, 1, 2, 3, 1, 2, 1]

puts list.index {|i| i == 3 }   # => 2
puts list.index {|i| i == 5 }   # => nil
```
# 23.next_permutation
```next_perm.rb
puts "#{[1, 2, 3].permutation(3).to_a}" # => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
```
permutation に加え、repeated_permutation combination 等もあります
# 24.__builtin_popcount
```bp.rb
puts 42.to_s(2).count("1") # => 3
```
to_s(2) で2進数表記とし、count で 1 の個数を数えます
popcountの実装例は、*[こちら](https://qiita.com/superrino130/items/273dc5f0a30caa7b009f#%E3%82%A8%E3%82%A4%E3%82%B7%E3%83%B3%E3%82%B0-%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88-2020)*を参照してください。
# 25.bitset
|プログラム|説明|
|:--:|:--:|
|a = (a ^ b) など|int 型ですので、ビット演算（and, or, xor）をすることができます。|
|a[i]|配列と同様、a の i 桁目にアクセスすることができます。a[i] は必ず 0 か 1 です。|
```bitset.rb
b = 2 ** 8 - 1
puts b.to_s(2)       # => 11111111
puts b[1]            # => 1
puts (b - 2).to_s(2) # => 11111101
puts (b - 2)[1]      # => 0
```
特定の bit 桁を変更する場合でも、Integer 全体へビット演算を行います。
# まとめ
+ @E869120 さんの情熱が凄い
+ ***C++*** のチート具合が凄い
+ ***Ruby*** もそれなりに凄い
+ 後編はない

参照したサイト
*[厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】](https://qiita.com/e869120/items/518297c6816adb67f9a5)*
*[厳選！Perl アルゴリズム実装に使える 25 の 標準ライブラリ【前編】](https://qiita.com/superrino130/items/ab266b53f85c181b369d)*
*[class Integer](https://docs.ruby-lang.org/ja/latest/class/Integer.html)*
*[ac-library-rb](https://github.com/universato/ac-library-rb)*
# 追記
Ruby競プロTips です。凄いっ！
[Ruby競プロTips(基本・罠・高速化108 2.7x2.7) - dev](https://zenn.dev/universato/articles/20201210-z-ruby)
# 追記の２
*[Rubyで競プロをするときに覚えておくと嬉しい機能](https://kona0001.hatenablog.com/entry/2021/02/23/025619)*