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

はじめに

@E869120 さんがとてもいい記事を投稿されています。
厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】

それの、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すると省略できて便利です

三角関数の実装例は、*こちら*を参照してください。

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

優先度付きキューの実装例は、*こちらを参照してください。
優先度付きキューの実装例２は、こちらを参照してください。
ac-library-rb の優先度付きキューの実装例３は、こちら*を参照してください。

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 インデックス

二分探索の実装例は、*こちら*を参照してください。

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

リファレンスの実装例は、*こちらを参照してください。
リファレンスの実装例２は、こちら*を参照してください。

19.tuple

リファレンスの実装例は、*こちらを参照してください。
リファレンスの実装例２は、こちら*を参照してください。

20.assert

assert.rb

1.upto(100) do |i|
  raise "i over 9" if i > 9 # => i over 9 (RuntimeError)
end

指定した条件でコメントを出力し、警告終了します。
【追記】
assert もいいけど warn もいいという話です。

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の実装例は、*こちら*を参照してください。

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 機能【前編】
厳選！Perl アルゴリズム実装に使える 25 の 標準ライブラリ【前編】
class Integer
ac-library-rb

追記

Ruby競プロTips です。凄いっ！
Ruby競プロTips(基本・罠・高速化108 2.7x2.7) - dev

追記の２

Rubyで競プロをするときに覚えておくと嬉しい機能