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


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

Rubyは 2.3.1、Railsは 4.2.6 を想定

## データ構造

|データ構造名|Ruby実装|
|---|---|
|構造体|Struct,OpenStruct[^**]|
|シンボル|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)|
|グラフ||

[^**]: require 'ostruct'が必要

## 正規表現

|名|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_date[^*]|Time.zone.now|
|n秒後|Time#+|n.seconds.since|
|n秒前|Time#-|n.seconds.ago|
|現在日|Date.today, Date.new[^*]||
|昨日|Date.new - 1|Date.new.yesterday|
|明日|Date.new + 1|Date.new.tomorrow|
|n日後|Date#+[^*]|n.days.since, Date#since(n.days)|
|n日前|Date#-[^*]|n.days.ago|
|n月後|Date#>>[^*]|n.months.since|
|n月前|Date#<<[^*]|n.months.ago|

[^*]: require 'date' が必要
## 整数

|アルゴリズム名|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|
|安全な乱数発生器[^***]|SecureRandom|

[^***]: require '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|