アルゴリズム・データ構造とRubyの実装

比較してみた。随時更新する。

Rubyは 2.3.1、Railsは 4.2.6 を想定

データ構造

データ構造名	Ruby実装
構造体	Struct,OpenStruct1
シンボル	Symbol, :STRING, String#to_sym
文字列	String, "", %(), %Q(), '', %q()
配列	Array, [], %w(), %W(), %i(), %I()
スタック	Array
キュー	Array, Queue
ハッシュテーブル	Hash, {}
複素数	Complex
有理数(分数)	Rational, 1/2r, 0.5r
整数(31or62ビット幅)	Fixnum, 1
整数(倍精度)	Fixnum, 100000000000000000
浮動小数	Float, 0.5
集合	Set
線形リスト	acts_as_list(gem)
木構造	rubytree(gem), act_as_tree(gem), closure_tree(gem)
グラフ

正規表現

名	Ruby実装
パターン	%r{STRING} , Regexp , /String/
マッチ	Regexp#match , String#match , =~
キャプチャ	Regexp#capture
最後に成功した文字列	$&, Regexp.last_match[0]

文字列操作

名	Ruby実装	ActiveSupport
文字コード	String#bytes,String#ord,String#getbyte
16進→10進	String#hex
文字列長	String#length, String#size
反転	String#reverse
結合	Array#join, String#+, String#<<
走査	String#scan
文字置換	String#tr
文字列置換	String#sub, String#gsub
文字取得	String#[]	String#at
部分文字列	String#[],String#slice	String#from,String#to,String#first,String#last
バイト切り出し	String#byteslice
打ち切り	String#[0,size], String#slice(0,size)	String#truncate
置き換え	String#replace

日付

名	Ruby実装	ActiveSupport
現在日時	Time.now, Time.new, Time#to_date2	Time.zone.now
n秒後	Time#+	n.seconds.since
n秒前	Time#-	n.seconds.ago
現在日	Date.today, Date.new2
昨日	Date.new - 1	Date.new.yesterday
明日	Date.new + 1	Date.new.tomorrow
n日後	Date#+2	n.days.since, Date#since(n.days)
n日前	Date#-2	n.days.ago
n月後	Date#>>2	n.months.since
n月前	Date#<<2	n.months.ago

整数

アルゴリズム名	Ruby実装
最大公約数	Integer#gcd
最小公倍数	Integer#lcm
素因数分解	Integer#prime_division / Prime#prime_division
素数	Integer.each_prime / Prime.each
絶対値	Numeric#abs
丸め	Numeric#round
商	Numedic#div
余り	Numeric#modulo
自身より大きな整数で最小のもの	Numeric#ceil
自身より小さな整数で最大のもの	Numeric#floor

算術

アルゴリズム名	Ruby実装
対数	Math.log
指数関数	Math.exp
円周率	Math.PI
正弦(sin)	Math.sin
余弦(con)	Math.cos
xの正接(tan)	Math.tan
xの逆正接(atan)	Math.atan
対数	Math.log
常用対数	Math.log10
二進対数	Math.log2
ガンマ関数	Math.gamma
直行する2辺の斜辺(対角線)	Math.hypot

乱数

アルゴリズム名	Ruby実装
メルセンヌ・ツイスタ(MT19937)	Random
安全な乱数発生器3	SecureRandom

組み合わせ

アルゴリズム名	Ruby実装
順列	Array#permutation
重複順列	Array#repeated_permutation
組合せ	Array#combination
重複組合せ	Array#repeated_combination

ソート

アルゴリズム名	Ruby実装
ソート	Array#sort

探索

アルゴリズム名	Ruby実装
繰り返し	Enumerable
繰り返し(遅延評価)	Enumerable#lazy
二分探索	Array#bsearch
幅優先
深さ優先
反復進化深さ優先
深さ制限
双方向
均一コスト
ダイクストラ	dijkstraruby(gem)
クラスカル	kruskal(gem)
最近傍
プリム
トポロジカルソート	tsortライブラリ
最良優先探索
A*

敵対検索

アルゴリズム名	Ruby実装
ミニマックス法
アルファ・ベータ法
分枝限定法

集合

アルゴリズム名	Ruby実装
集合	set

暗号、ハッシュ関数

アルゴリズム名	Ruby実装
AES	OpenSSL::Cipher::AES
AES(128bit長)	OpenSSL::Cipher::AES128
AES(192bit長)	OpenSSL::Cipher::AES192
AES(256bit長)	OpenSSL::Cipher::AES256
BlowFish	OpenSSL::Cipher::BF
CAST5	OpenSSL::Cipher::CAST5
DES	OpenSSL::Cipher::DES
IDEA	OpenSSL::Cipher::IDEA
RC2	OpenSSL::Cipher::RC2
RC4	OpenSSL::Cipher::RC4
RC5	OpenSSL::Cipher::RC5
PKCS#7	OpenSSL::PKCS7
DSS	OpenSSL::Digest::DSS
DSS1	OpenSSL::Digest::DSS1
MD2	OpenSSL::Digest::MD2
MD4	OpenSSL::Digest::MD4
MD5	OpenSSL::Digest::MD5
SHA	OpenSSL::Digest::SHA
SHA1	OpenSSL::Digest::SHA1
SHA224	OpenSSL::Digest::SHA224
SHA256	OpenSSL::Digest::SHA256
SHA384	OpenSSL::Digest::SHA384
SHA512	OpenSSL::Digest::SHA512

1. require 'ostruct'が必要 ↩

2. require 'date' が必要 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. require 'securerandom' が必要 ↩