simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

Ruby で赤黒木を実装してみた

この記事は Okinawa.rb Advent Calendar 2019 の 15日目の記事です。

結論

実装しました。

https://gist.github.com/siman-man/a8ed58effeaaf59855deac490574760c

二分探索木

前々から赤黒木を実装しようと思っていたのですがずっと放置していたので、今回実装してみました。

まず比較用に二分探索木から実装します。

https://gist.github.com/siman-man/dc79878e5a8d93c73299c1145458a820

二分探索木ではデータの検索、挿入、削除といった操作が O(log n) で可能となるデータ構造です。

探索木の各ノードは以下の条件を満たします。

あるノード x において、y が左側に存在するノードであるならば「x.value >= y.value」、右側であれば「x.value <= y.value」を満たす。

この条件が満たされていることで、値の検索が下記のようなコードで可能となり、その実行時間は O(log n) となります。

  def find(value)
    z = @root

    while z != NUL && z.value != value
      if value < z.value
        z = z.left
      else
        z = z.right
      end
    end

    z
  end

データの挿入時についても、値の挿入先を探すのに上記と似たような処理を実行するのですが、入力されるデータによっては実行時間が O(n) となってしまいます。

例として 1000 件のデータをランダムに入れるコードを書いてみます。

require 'benchmark'

nums = (1..1000).to_a.shuffle

time = Benchmark.measure { nums.each { |n| bst.insert(n) } }

puts time

結果

$ ruby binary_search_tree.rb
  0.006067   0.000049   0.006116 (  0.006128)

ここでランダムだった部分を取り除きます。

  require 'benchmark'

- nums = (1..1000).to_a.shuffle
+ nums = (1..1000).to_a

  time = Benchmark.measure { nums.each { |n| bst.insert(n) } }

  puts time

すると実行時間が遅くなることが確認出来ます。

$ ruby binary_search_tree.rb
  0.192344   0.000213   0.192557 (  0.192703)

このように特定の入力によって操作の速度が低下してしまうのを回避できるのが「平衡二分探索木」であり、その一つに赤黒木があります。

赤黒木

赤黒木では先程の二分探索木の各ノードに色情報が付与されます。ノードの色は「赤」か「黒」です。赤黒木では以下の制約によって木の高さの差が2倍を超えることが無いことが保証されています。

  1. 各ノードは赤または黒色
  2. ルートノードの色は黒色
  3. すべての葉は黒色
  4. あるノードが赤色であればその子ノードは黒色
  5. あるノードからその子孫に対する経路について、その経路に含まれる黒色のノードの数が同数である。

実際に実装してみたのがこちらになります。

https://gist.github.com/siman-man/a8ed58effeaaf59855deac490574760c

実際に速度を測ってみます。

require 'benchmark'

rbt = RedBlackTree.new

nums = (1..1000).to_a

puts Benchmark.measure { nums.shuffle.each { |n| rbt.insert(n) } }
puts Benchmark.measure { nums.each { |n| rbt.insert(n) } }

結果

$ ruby red-black-tree.rb
  0.005910   0.000016   0.005926 (  0.005923)
  0.005540   0.000009   0.005549 (  0.005549)

このように偏った入力についても実行時間が遅くならないことが確認出来ました。

おわりに

前々から実装しようと思っていたので実装できる良い機会でした。(思った以上に実装量が多かった)

本当は定数名に NUL じゃなくて NIL を使おうと思ったのですが ruby 側で定義されていたのでそれは避けました(deprecated みたいなので将来的に無くなるとは思いますが)

今後も色々とアルゴリズムの実装をしていきたいと思います。(競プロ用のライブラリ整備)

参考文献

実装と詳細については「アルゴリズムイントロダクション 第3版」を参考にしました。

RailsDM 2019 で登壇してきました

RailsDM 2019 で登壇

RailsDM 2019 で「Ruby のコード解析の「静」と「動」」というタイトルで発表してきました。

f:id:simanman:20190322183624j:plain:w800

去年の年末あたりに平野さんから登壇依頼が DM 経由で来て「せっかくの機会なのでやるか!」と思い引き受けることにしました。(CFP 形式だと登壇してなかったと思います)

RailsDM なので Rails に関する話が出来れば良かったですが、自分はあまり Rails をそこまで触ってなかったので 普段 Rails を使っている開発者が知らないことを発表するのは少し難しそうだなと思い、Rubyソースコード解析周りの話をしました。

静的解析、動的解析については過去にも色々発表があるのでそこまで新鮮味は無さそうな気もしましたが、2.6 の新機能の発表はまだ無さそうと思ったのでそのあたりを発表すればそのあたりは大丈夫かなという感じでした。

AbstractSyntaxTree とか TracePoint とか InstructionSequence の利用例を調べるためにローカルで https://github.com/akr/gem-codesearch の環境を整えて色々利用例を眺めてたのですが、結局時間の都合上あまり紹介することは出来ませんでした。(あとあまり調査が出来ていなかった)

発表に関しては正直 10人ぐらい来れば御の字だと考えていたので想像より多くの人に来ていただいて感謝です。ありがとうございました。

また、このような素敵なカンファレンスを開いていただいた RailsDM 運営スタッフの皆様ありがとうございました。

発表できなかった話題

以下は発表資料の中に入れてたけど時間を削るために省いた内容です。

RubyVM.resove_feature_path の不具合

RubyVM.resolve_feature_path ではパスを取得したいライブラリ名を読み込む前じゃないと動作しないという問題があります。(trunk では修正済み)

pp RubyVM.resolve_feature_path('prime')
require 'prime'
pp RubyVM.resolve_feature_path('prime')

実行結果

[:rb, "/Users/siman/.rbenv/versions/2.6.1/lib/ruby/2.6.0/prime.rb"]
[:rb, false]

なのでサンプルコードでさらっと 2.7 前提のコードを書いてましたが、そういう背景がありました。 あとこれはまだ確認はしてないのですが、 gem install 経由で入れたライブラリ名のパスについては取れない気がします。($LOAD_PATH で探して終わり)

iseq オブジェクトを自前で作成して差し替える

iseq を差し替える手法として別のファイルをコンパイルして差し替える方法を紹介しましたが、別の方法として iseq の命令列を作成してそれを Ruby の Cの関数を利用して読み込むという方法もあります。(こっちのほうが出来ることの柔軟性は高いと思います)

詳しくは下記の記事に乗っているので是非読んでみてください。

https://magazine.rubyist.net/articles/0053/0053-YarvManiacs.html

coverage

個人的に Ruby の coverage ライブラリは気になっていたので動的解析の部分で入れたかったのですが時間の都合上カットしました。2.5 で 分岐カバレッジ、 2.6 で oneshot カバレッジが利用できるので組み合わせたら色々出来そうな気がしますが、ネタが出てこなかったです。(なので動的解析部分が TracePoint だけになってしまいました。

標準ライブラリの使用例の調査方法

rubygems にあるような gem の場合は reverse_dependencies で調べることが出来るのですが、標準ライブラリはそれが出来ません。かといって GitHub の検索を使ってもあまりうまくいかないので、今回 gem-codesearch を利用しました。自分はセットアップに数日かかりました。

セットアップが終わったらあとは csearch [検索したい文字] で検索することが出来るようになります。

$ csearch RubyVM::InstructionSequence

今回作った gem

今回の発表準備の期間で作った gem です。

astree

自分は tree コマンドが好きなので色々 tree コマンド風に表示させることをしているのですが、今回はそれの AbstractSyntaxTree 版です。

ast2dot

AbstractSyntaxTree で得られた構文木を dot 言語で表現するやつ。発表資料の一部はこれで吐き出して少し編集したものを使いました。

ast_distance

2 つの構文木を受け取ってその編集距離を出すやつ。ただ AbstractSyntaxTree の場合は少しのコード変更でもかなり変わりやすいのでなかなか有効活用は難しいかもしれません。

load_tracer

ファイル間の依存を調べる gem。 2.7 でしか動かない。まだ実験的な実装なので得られる結果が正しくないこともあります。

懇親会

懇親会では色々な人と話すことが出来て楽しかったです。以下は覚え書き(抜けている人がいたら申し訳ないです

yasulab さん

来月の RubyKaigi の部屋の話やここ最近取り組んでいたプロジェクトの話を聞いてました。 Airbnb の宿自体はかなり前から予約していたらしく、かなり費用が安いとのこと。(住宅宿泊事業法が施行された後ではかなり料金が上がったらしいです

kyuden さん

今回実装していた llrbtree の実装にあたって参考にしたものを聞いてみたらスライドの中で紹介されてた この論文 だけとのこと。スゴイ。Ruby にも優先度付きキュー欲しいですねーという話をした。あと、自分も試しに赤黒木実装してみますと宣言してしまったので来月の RubyKaigi までには実装してみます。(一応前にやろうと思ったことがあったので)

yono さん

「お久しぶりですー」みたいな感じで話してた。Redmine 開発辛いトークを hanachin さんと楽しそうにやってました。

秒速さん

去年の RubyKaigi 以来で「お久しぶりですー」みたいな感じで話してました。「Okinawa.rb やばい」という話をしてましたが多分サンプリングが悪いと思っています。

koic さん

発表資料の中にあった LT の概要が気になったので聞きに行きました。 TracePoint の利用事例として面白かったです。自分の場合すぐ良くない方向で活用することを考えてしまうので、もっと役立つ方向で広めていきたいというお気持ち。

joker1007 さん

TracePoint トークをしてました。

このツイートの内容の詳細についてや、あと「AbstractSyntaxTree にパターンマッチほしいよねー」とか「TracePoint の b_call イベントで引数の値を取りたい」的な話など。

knu さん

SortedSet の話を聞きに行きました。実験的に実装したつもりがいつのまにか本体に取り込まれてしまったとのこと、自分は競技プログラミングをやっているので Ruby 本体で優先度付きキューが入ってくれると助かるのですが、厳しそうとのことでした(競技プログラミングでは 外部ライブラリを使うことが出来ないので本体に無いと使えない)

ujihisa さん

来月の RubyKaigi でローカル変数だけの話をする( Play with local vars )という話や今回発表していた内容について少し話しました。「Rubyフリップフロップを実装出来るか否か」みたいな話になって、その場では答えられなかったのですが、後々考えてみると rubinius の実装を見ればなんとかなるのではと思いました。(自分はまだ見てないです)フリップフロップ構文はもう deprecated な機能になってしまったのでそれがつらいみたいなことも話しました。

yui-knk さん

今回 AbstractSyntaxTree を触ってて色々気になったところを伺いに行きました。一通り疑問が解決出来たので良かったです。 Ruby の実行オプションである yydebug オプションをオススメされましたが、自分がこのオプションを有効活用出来るようになるのはまだ先な気がします。あと ドラゴン本 を紹介されました。

今年作った gem の紹介 (2017)

この記事は Okinawa.rb Advent Calendar 2017 4日目の記事です。

自分は思いついたアイデアをすぐ gem にするようにしているのですが、今年は結構作った気がしたのでそれを紹介したいと思います。

spellcheck

主に技術系の単語にフォーカスしたスペルチェッカー、スペルミス候補を全部 Hash データで管理していてそれを増やすのが面倒になって放置。

サンプル (aplication がタイポしている

hello world.
I create aplication now.
good bye
$ spellcheck example.md
+----------+--------------------------+------------+-------------+
| Location | Text                     | Pattern    | Expected    |
+----------+--------------------------+------------+-------------+
| 2        | I create aplication now. | aplication | application |
+----------+--------------------------+------------+-------------+

result: 1 typo found.

typogen

英語の typo を生成するコマンド。

前に qiita で紹介したことがあるので詳しくはこちら。

https://qiita.com/siman/items/e3c8dfb72e37142b0b86

spellcheck の辞書データを作っていた時に、typo したときの単語一覧を手入力するのが面倒になった作成した。

$ typogen install
nstall
istall
intall
insall
instll
instal
nistall
isntall
intsall
insatll
instlal
instale

ripper_tree

rubyRipper.sexp の表示を tree コマンド風で表示させる。

$ rtree -e "1+2*3"
:program
 └──── :binary
         ├──── :@int ["1"] 1:0
         ├──── :+
         └──── :binary
                 ├──── :@int ["2"] 1:2
                 ├──── :*
                 └──── :@int ["3"] 1:4

今年作った gem の中では一番使っている。

tspec

TracePoint を使って Ruby で型チェックが出来るようにした gem。

require 'tspec'

def echo(str)
  puts str
end.receive(str: String)

echo('hello world') #=> ok
echo(123)           #=> TSpec::ArgumentTypeError
require 'tspec'

def echo(val)
  puts val
end.receive(val: [String, Float])

echo('hello')  #=> ok
echo(3.14)     #=> ok
echo(123)      #=> TSpec::ArgumentTypeError

ただ、挙動がちょっと怪しいので自分でも使うのをためらっている。

jt

JSON を tree コマンドっぽく表示させる gem

https://qiita.com/siman/items/a59a7ac80fba3e71ed38

rrpn

逆ポーランド記法の計算機と変換器

https://qiita.com/siman/items/d72854c4c4aaaf452868

rpn名前空間ほしかったけど取られていた。(残念

hrm

ヒューマンリソースマシーンに出てくる命令を実装したもの。メモリの初期状態を設定するコードは実装していないかも。

ヒューマンリソースマシンは完全クリアした(ドヤァ

rodir

Ruby のオブジェクト継承ツリーをディレクトリっぽく扱うもの

$ rodir
Ruby@2.4.0 /BasicObject$ ls
<M>   #<Module:0x007fb11a911388>
<M>   Kernel
Ruby@2.4.0 /BasicObject$ cd Kernel
Ruby@2.4.0 /BasicObject/Kernel$ ls
<C>   Object
Ruby@2.4.0 /BasicObject/Kernel$ cd Object
Ruby@2.4.0 /BasicObject/Kernel/Object$ pwd
BasicObject/Kernel/Object

実際に触ってみて 5分で飽きた。

open_class_alarm

オープンクラスに警告を出す gem

https://qiita.com/siman/items/cbc7b85ff45eb5fc58d5

いらない

proc_source

Proc オブジェクトのソースを表示する。

https://qiita.com/siman/items/9ad676cbb4f8afbd15ac

a = -> { 'hi' }
puts a.proc_source
-> { 'hi' }

lier

? で終わるメソッドの返り値を全て逆にする

https://qiita.com/siman/items/475d355fe22e34659149

エイプリルフールネタで作った。テストするときに rspec が壊れてやばかった。(Refinements で影響範囲を限定させた

rtg

Ruby で作ったタイピングゲーム

f:id:simanman:20171204191426g:plain

自分のコンソールの画面に合わせた配色にしたので、場合によっては文字が見づらいかも。

keyevent

keyevent を取得する gem。(Windows では試していない)

require "keyevent"

while input = getkey
  break if input == "Q"

  p input
end

rtg を作っていた時に分離できそうだったので分離した。

まとめ

結構 gem を作ってた。(使ってるとは言ってない

北大日立マラソン参加記

参加してました。

https://hokudai-hitachi2017-1.contest.atcoder.jp/

やったこと

とりあえず submit (52935)

左上から丁寧に並べる

f:id:simanman:20171128215945p:plain:w300

焼きなましする (52935 -> 149624)

近傍は ランダムな2点の位置を交換する

温度管理を調整 (149624 -> 155183)

雑に設定していたパラメータをちょっと調整

遷移させるかどうかの閾値を設ける (155183 -> 156319)

確率的に遷移させるけど、あまりにもスコアが下がっていたら遷移を却下する。

近傍を変える (156319 -> 159568)

ランダムな2点の位置を交換する から ランダムな辺を選び終点の周辺マスを1つ選択する。既に点がある場合は交換、ない場合はそこに点を移動させる に変更。

これだと、必ずスコアに影響がある近傍になるので効率が良い。

f:id:simanman:20171128220004p:plain:w300

初期解を変える (159568 -> 160152)

最初から中央に配置しておくことで移動のバリエーションが増える (気がする)

f:id:simanman:20171128220015p:plain:w300

諸々高速化 (160152 -> 160950)

盤外判定を削除したりとか

if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

高速化 (160950 -> 161572)

辺の重みを int で管理してたのを char にしたら速くなった

細かく確認してないけど、この時点での試行回数は 2億5千万前後ぐらいだったと思う。(3億は目指したかった)

パラメータ調整 (161572 -> 163024)

ひたすらパラメータ調整。(このときはまだ、システムテストとか無かったから適当に submit しながら調整してた)

辺の一部のみを採用する (163024 -> 163653)

全部の辺を使ってたけど、各頂点から生えている辺を重さ順で並べて、その上位だけを使用するようにした。

コード

https://github.com/siman-man/hokudai-hitachi2017

PoisonedWine 参加録

問題

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16944&pm=14636

複数のワインの中から、毒に反応する試験紙を使って「毒入りのワイン」を見つけ出し「毒入りではないワイン」をいかに多く集めることが出来るかという問題でした。(試験紙は毒に反応すると、次回以降に利用できなくなります)

方針

今回の方針です。

1. ワインを一通り検査する

まずは、各ワインを1回ずつ検査していきます。1回のラウンドで検査する範囲についてですが、以下の計算式で出していました。

n * (残っている試験紙の数 / 残っている毒の数) * (未チェックのワインの数 / 残りラウンド数) # nは任意の係数

そして、計算した範囲を試験紙の枚数で分割して、それぞれ検査を行います。

検査中に「試験紙が反応した数 == 毒の数」になった場合は、そこで検査を止めて、未検査のワインを全て保持するようにします。

また、毒に反応した範囲は 毒入りワインリスト に追加します。(毒入りワインリスト は範囲の大きいサイズから取り出す優先度付きキューです)

struct PoisonBarrel {
    vector<int> wineList;

    bool operator>(const PoisonBarrel &pb) const {
        return wineList.size() < pb.wineList.size();
    }
};

2. 追加のチェック

手順1で出した検査範囲だと「試験紙の数 < 毒の数」の場合はそもそも全部検査しきれずに終わることが多いです。逆に「試験紙の数 > 毒の数」の場合は全てのワインの検査後にラウンドが余るケースが発生するので、その場合は追加の検査を行っていきます。

追加の検査は試験紙が反応した範囲のワインに対して行います。

2.1 試験紙が反応した数 == 毒の数の場合

このケースでは「試験紙で検査した範囲に必ず毒が1個ある」という状態が確定しているので 毒入りワインリスト から試験紙が反応した範囲を取り出して、それを分割して検査します。m枚の試験紙を使って検査する場合はその範囲を m + 1 で分割します。m + 1 で分割している理由は、m枚の検査の結果から残りのワインの状態を確定させることが出来るからです。(いずれかの試験紙に反応すれば残りはOK、試験紙が反応無しだとOUT)

f:id:simanman:20170724082122p:plain

そして、毒が入っている範囲のワインを再度 毒入りワインリスト に追加します。

これをラウンドか試験紙がなくなるまで続けます。

2.2 試験紙が反応した数 != 毒の数の場合

このケースでは「試験紙で検査した範囲に複数の毒がある」という可能性があります。なので、この場合は m + 1 で分割しても、試験紙の結果から残りの状態を確定出来ません。

(もしかしたら毒かもしれないので確定できない)

f:id:simanman:20170724083512p:plain

このため、確定できなかったワインリストについては とりあえず保存領域 に置いておきます。

f:id:simanman:20170724083935p:plain

とりあえず保存領域 は、後の試験結果で毒が存在する箇所が全て確定した時にキープするワインのリストを置く場所です。

例えば「試験紙が反応した数 = 9, 毒の数 = 10」だとして、毒入りワインリスト から取り出した範囲から2個以上の試験紙の反応が出た場合。全ての毒の存在箇所が確定するので とりあえず保存領域 にあるワインを保存します。

f:id:simanman:20170724084855p:plain

このケースの場合はなるべく早い段階で複数の毒を検出したいので、試験紙の割り振り方を「m > 1」になるように調整しています。(例: [1, 1, 1, 1, 1] とあったら [3, 2, 0, 0, 0] となるように調整)

Examples

Example scores:
0) 0.01323285993742249
1) 0.20518911960377745
2) 0.009050017313019389
3) 1.0
4) 0.05072227596728843
5) 0.00401218710446807
6) 0.04226661200602016
7) 0.07289292284542803
8) 0.001466688380179619
9) 0.6574141709276845

MM92 Lighting 参加録

Marathon Match 92の「Lighting」に参加していました。

問題

SxS のセル状空間に光源の強さがDのL個のライトをいい感じに設置して、なるべくたくさんの空間を照らしましょう。

すごいシンプルでした。美術館問題に似た問題だなと思いました。

方針

大きく分けて次の3つを行いました。

  • フィールドの拡大率をいい感じに決める
  • 焼きなましで照明を設置する場所を決める
  • 焼きなまし後にフィールドの拡大率をさらに上げて照明の位置を微調整する

フィールドの拡大率をいい感じに決める

最初に与えられたフィールドをそのまま使うと照明のシミュレーションの精度が粗いので、フィールドをある程度引き伸ばして精度を高めました。テスターの実装では拡大率が f = 100 で定義されていましたが、これをそのまま使うと後の焼きなましパートで試行回数が全然稼げないので、フィールドサイズが「縦 x 横 == 10000」ぐらいになるように値を修正しました。

SCALE = ceil(sqrt(10000 / (S * S))); // 端数は切り上げ

焼きなましで照明を設置する場所を決める

遷移は「照明を1つ選び任意の場所に移動させる(※ただし壁は除く)」を採用し、温度管理は「差分スコア / (任意の定数) * (残り時間)」で管理してました。

1つのセルを16分割して細かく移動出来るようにしています。

f:id:simanman:20170119163941p:plain

   ↓

f:id:simanman:20170119163947p:plain

高速化

一度照明のシミュレーションをした座標については「照らすことが出来るセルの位置情報」をキャッシュして、次回以降はそれを取り出すようにしました。

照明の位置を微調整

焼きなましパートで照明の位置を決めた後に位置を微調整を行いました。処理的には任意の照明を1つ選んでちょっとだけ動かしてスコアが改善していたら採用という感じで山登り的に行いました。シミュレーションの精度を上げるために事前にフィールドを焼きなましパートのときより少し拡大しています。

f:id:simanman:20170119013248p:plain

それぞれのパートの時間の割り振りは

  • 焼きなまし(15秒)
  • 微調整(5秒)

としました。

感想

0.1%のスコア範囲で争ったのは初めてかもしれない。みんな大体同じ戦略になってそう。

Example scores:
0) 0.9987473684210526
1) 0.8922939051918736
2) 0.7014297413793104
3) 0.382128527607362
4) 0.15465865921787708
5) 0.13367932926829268
6) 0.98818025477707
7) 0.9328539007092198
8) 0.7149500729927007
9) 0.7206551724137931

ソースコード

RubyのEnglish.rbソース読み

Rubyの標準ライブラリを読んでいく、前回は3年前に ostruct を読んだ

今回は English.rb を読んでいく。

English.rbとは何か

English.rbはRubyの特殊変数に対してわかりやすい別の名前を付与するライブラリである。Rubyの特殊変数は通常 $ + 記号 の形で与えられており大変読みにくい。そこでこの English.rb を取り込むことで読みやすい別名を使用することが出来るようになる。

require 'English'

"hogefugapiyo" =~ /fuga/

p $PREMATCH   #=> "hoge"
p $MATCH      #=> "fuga"
p $POSTMATCH  #=> "piyo"

中身を見てみる

基本的に alias を使って別名を割り当てているだけ

# The exception object passed to +raise+.
alias $ERROR_INFO              $!

# The stack backtrace generated by the last
# exception. <tt>See Kernel.caller</tt> for details. Thread local.
alias $ERROR_POSITION          $@

# The default separator pattern used by <tt>String.split</tt>.  May be
# set from the command line using the <tt>-F</tt> flag.
alias $FS                      $;

1つ気になるところ

読んでいて1個所気になったのはこの部分

module English end if false

絶対に実行されない謎のコードが入っていたので「なんだこれは」と思っていたのだがどうやらRDocのparseのために追加しているらしい。

参考URL