「棒を切る」をErlangで
最強最速アルゴリズマー養成講座：トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター に出てきた 棒を切る問題 が自力で解けたので、記念にアップします。
毎日お風呂に入りながら考えて2週間くらいかかりました (遅すぎ (^^;))
自分で後で見てコードの意味がわかるように解説:
- 与えられた最大切断数以下の回数で棒を切る関数cutと、cutを呼び出しながら最適な切断長さを探す関数findでできています。
- findは長さの上限(H)と下限(L)を持ち、その中央の値(M)でcutを呼び出します。
- cutの結果、中央の値(M)以上の長さを持つ棒がK本以上あったら、もっと長く取れると判断して下限(L)を中央の値(M)に引き上げます。
- 反対にK本以上なかったら、もっと短くする必要があると判断して上限(H)を中央の値(M)に引き下げます。
今回の問題で、上限と下限の範囲を狭めて探索していく方法を学びました。あと、Erlangでは変数名を1文字にするとすっきり書けることがわかりました。頭がだいぶ関数型に慣れてきたようです。
分散バージョン管理システムにバイナリファイルを格納した時のリポジトリ増加量
バイナリファイルを格納・修正した時の分散バージョン管理システム(DVCS)のリポジトリ増加量について調べてみました。
使ったDVCSのバージョンは次の通りです。すべてWindows 32bit版です。
- Bazaar … TortoiseBazaar 0.6.6 (Bazaar 2.5.1)
- Git … Git 1.7.11-preview20120710
- Mercurial … TortoiseHG 2.7.1 (Mercurial 2.5.2)
これらのDVCSを使って以下の操作を実行しました。
バイナリファイルとしてExcelのドキュメント(.xls)を使用しています。ファイルの初期容量は7,806,976バイトです。
それぞれの操作をしたときのDVCSの管理ディレクトリの容量は次のようになりました。(単位は Bytes)
| 操作 | Bazaar (.bzr) | Git (.git) | Mercurial (.hg) |
|---|---|---|---|
| 1 リポジトリの作成 | 36,864 | 61,440 | 8,192 |
| 2 バイナリファイルの追加 | 7,151,616 | 7,217,152 | 7,143,424 |
| 3 バイナリファイルを修正 | 14,262,272 | 14,352,384 | 7,262,208 |
| 4 バイナリファイルを修正 | 21,375,488 | 21,490,176 | 7,378,766 |
| 5 git gc | 21,375,488 | 7,297,536 | 7,378,766 |
この結果から、バイナリファイルの場合の動作は次のようになっていると推察されます。
- Bazaar … 各コミットの差分を取らずに丸々格納します。
- Git … 通常は各コミットの差分を取らずに丸々格納し、git gcを実行することで差分に変換します。参考: Git - パックファイル
- Mercurial … 各コミットの差分を格納します。
「ビットあみだくじ」をErlangで
趣味と勉強を兼ねて「ビットあみだくじ」(http://nabetani.sakura.ne.jp/hena/ord11bitamida/)をErlangでやってみました。
以下のソースをba.erlというファイルに保存し、Erlangのコンソールから「c(ba).」「ba:tests().」で実行できます。
1> c(ba). {ok,ba} 2> ba:tests(). d6-7b-e1-9e -> 740631825, true 6f-dd-ff-ff -> 230685147, true ok
