B木の Copy-Modify 方式での実験的コード - Tociyuki::Diary
id:naoya さんの Python 版B木に触発されて、Ruby 版の insert・delete だけを実装した B 木を書いてみました。 実装にあたり、標準的な教科書に良く掲載されている Overwrite 方式ではなく、現代的な Copy-Modify 方式、すなわち B 木の葉から根に向かって更新のおこなわれるノードを複製してから修正をおこなっていき、最後に根をすげ替える方式に挑戦してみました。こうすることにより、更新の途中でなんらかの例外が発生したとしても、直前の B 木を壊さずにすみ、安全にロール・バックすることができるようになります。また、更新の途中の元の B 木はいっさいがっさい元のままですから、根を変更バージョンごとに持つようにすれば、現代的なデータ・ベース・マネジメント・システムに採用されている Multi-Version Concurrency Control(M
継続でバックトラックを Ruby で - Tociyuki::Diary
年度末になると忙しくなる人種に巻き込まれてしまい、Ruby と Perl を使って遊ぶのは数週間ぶりのことです。中断していた作業をチェックアウトして眺めていたのですが、どうも気分が乗らないので、リハビリを兼ねて LispUser.net : 継続でバックトラック の scheme のバックトラックの例題を Ruby に直訳してみました。 if 文の条件式を満たす x、y、z の組み合わせを探す問題です。探索範囲は 0 から 100 の整数。それぞれの値で条件が成り立つかどうかをチェックし、成り立たないときは、fail 関数を呼ぶことでバックトラックを生じさせて、次の数値のチェックを続けます。 require 'trial' def solve x = Trial.in_range(0, 100) y = Trial.in_range(0, 100) z = Trial.in_range(0
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
