やぐブロ

yag + programming + hateblo

開発合宿でのClojureを使ったBWT(Burrows-Wheeler Transform)の実装

先週末に千葉県銚子近くの温泉宿で行われた2泊3日開発合宿に参加してきた．参加者はiNut,syou6162,twittoru,wakuteka,y_benjoで，この合宿は今年で3回目になる．

やったコト

今回の開発合宿では，データ圧縮や全文検索などに用いられるBurrows-Wheeler Transform（以下BWT）をテーマにして，最近勉強しているプログラミング言語のClojureで実装してみることにした．
索引を使用した全文検索において特に有名なBWTだが，自分の研究分野であるBioinformaticsにおいても所謂「short read alignment」のアルゴリズムとして広く使われている技術である．日頃からこのアルゴリズムを使ったソフトウェアと接する機会が多く，一度自分で実装してみたいという思いが前々からあったので，今回フルスクラッチで書いてみることにした．今の自分のアルゴリズムの知識では実装しきれないだろうということは重々承知の上だった．しかしながら，折角の機会なのだから一歩でも踏み出しておきたい，開発合宿の短期間でどこまで出来るか試してみたい，という気持ちがあり，開発合宿直前になって急遽テーマを決めたという経緯がある．
プログラミング言語としてClojureを選んだ理由は，まあこのblogの過去記事を見れば明らかだろう．やっとのことで少しはまとまったスクリプトを書けるようになってきたので，この辺りで一つ大きなプログラムを作ってみたいと思っていたところだった．ただ，アルゴリズムの実装の面での不安がかなり強かったので，プログラミング言語の方はせめて書きなれたRubyを選択すべきといったあたりで結構悩んだ．最終的にはClojureで使っても大丈夫だろうと判断したのは，参加者にClojureが出来る人(syou6162)が居たからだった．

ソースコード

https://github.com/TrainingCamp2012/BWT-Clojure
この記事及びgithubのソースコードの実装には多分に誤りが含まれている恐れがあるので，決して参考にしないよう宜しくお願いします．

主に書いていた処理部分：https://github.com/TrainingCamp2012/BWT-Clojure/blob/master/src/BWT_Clojure/bwt.clj
処理部分は実質40行くらいしか書いていないが，改めて自分で見てみるとやはりClojureは短く簡潔に書けるのだと実感する（大したことやってないというのもあるが...）．syou6162に関数はもっと小さく分けてテスト書いたほうがいいと言われたので，今度から気をつけよう．

評価

先に結論から書いてしまうと，今回の開発では実用に耐えうるような実装が出来なかった．具体的に言えば，まずBWTアルゴリズムの実装方法が非常に効率の悪いもので，数万文字くらいの英文の索引を作るのに手元のマシンのメモリ（3GBくらい）では足りないような状態だった．それに索引から検索クエリに一致した箇所を持ってくるスクリプトもかなりプリミティブであり，一般的にBWTと合わせて使われるFM-IndexやCSAを実装するまでには至らなかった．といったように，今回の開発ではBWTのアルゴリズムを素人なりになぞっただけとなってしまい，結果として残ったのは残念なスクリプト片だけという感じになってしまった．
ただ，これを書くと言い訳がましくなるので良くないのだが，当初定めていた目標はきちんと超えることが出来たので個人的に満足している側面もある．効率が悪いにせよ，限られた時間内で曲がりなりにもBWTの体裁を取って全文検索のようなものが出来上がったのは非常に満足している．プログラムの面においても，今回はじめてClojureでテストを書きながら実装し，ClojureのビルドツールであるLeiningenを使ったコンパイルなどClojure開発周辺の知識も得ることができた．まあ出来なかったものは仕方がないので，この開発で出てきた問題点や疑問点をこれから徹底的に潰していって，これからプログラムを洗練させていくしかないという感じだろうか．今後もできれば開発を続けていきたいと思っているので，とにかく一つの区切りのようなところまで持っていけたのは素直に嬉しい．


開発の流れ

合宿前

さすがに準備なしで合宿に挑むのは無謀だと思って，事前に少し練習のようなものをすることに．Suffix Arrayの記事で取り上げている問題は，まさに準備運動にうってつけだった．あとはBWTに関する資料をいくつか読んだり，全文検索周りで転置インデックスの方を調べるなど脇道に逸れたり．

合宿前半

アルゴリズムを理解するところで一苦労．その後BWTの変換と逆変換をするところまでは一気に実装したのだが，その後ある程度大きなデータに適用できない事がわかって原因調査とリファクタリングを繰り返す．

合宿後半

syou6162にアルゴリズム部分の処理方法の変更を提案され，ペアプログラミングみたいな感じでscreen共有でプログラミングしたりした．あとは，小さなデータセットでメモリ使用量のベンチマークを取ったり，テストを追加したり，プロジェクト全体の調整をしたりという感じでタイムリミット．


生活

温泉宿は周りにコンビニすらないような立地だったので，お菓子やら飲み物を買い込んでひたすら部屋で開発という感じだった．温泉は1日目は浴衣が無くて入れなかったのだが，2日目には入れるようになった．1回しか入らなかったのだが，非常にリフレッシュ出来て良かった．
ネットに関しては，イーモバイルの電波も入ったし，部屋に設置してあった有線LANがかなり速度が出る感じだったので，全体的にかなり快適に作業出来た．
あと，畳の上で座って作業するのはやはり腰を痛める．例年そうなのだが...

「Joy of Clojure」を電子書籍で買ってみた

clojure

「The Joy of Clojure」を電子書籍で買ってみた．「プログラミングClojure」も電子書籍版を買ったので，未来に生きている感が強い．

The Joy of Clojure

The Joy of Clojure


プログラミングClojure

プログラミングClojure


詳細は別の機会に書くとして，以前とあるアルゴリズムを基にした実装をClojureでしたのだけれども，計算量やメモリ使用量周りの知識が全く無くて結構大変な思いをした．そもそもアルゴリズムの知識なぞこれっぽっちも無くて計算オーダー自体不慣れなのに加えて，Clojureの組み込み関数がどれくらいの計算量がかかってメモリに載せる必要があるか（線型探索で最悪O(n)かかるとか）といったことがイマイチよくわかっていない．前者は置いておいても，後者にかんしては遅延シーケンスなどのプログラミング的な基礎の知識が必要なことを強く感じた．取り敢えずは一通り本を読んで言語というものを理解するところから始めたい．
まあ，そもそもでかいデータを扱わない以上計算オーダーなんて気にする必要は無いのだけれども，やはり大きなデータで遊びたいしなぁ...．

参考

WEB+DB PRESS Vol.67の最長重複文字列問題をClojureで解いてみた

clojure

今月発売のWEB+DB PRESS Vol.67には関数プログラミングの特集があり，主にHaskellで解説された入門記事が載っています．その今月号を少し早く手に入れることができたので，早速記事の中で解説されているプログラムの中から「最長重複文字列問題」をClojureで解いてみました．珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造でも取り上げられている問題です．

WEB+DB PRESSに載っているコードの設計図通りに順序立てて並べています．実際に実行してみると，

user> (longest-duplicated-substring "mississippi")
(4 "issi") 

user> (longest-duplicated-substring "Ask not what your country can do for you, but what you can do for your country.")
(15 " can do for you")

といったように，ある文字列の中で重複している最も長い文字列が出力されます．

ただ，このスクリプトでは例で出されていた短い文字列を処理するだけの目的で実装したので，長い文字列の場合にはとたんに大量のメモリが必要になるため注意が必要です．今の自分のレベルでは遅延シーケンス周りが不勉強であまり理解できていないので，この実装では組み込めませんでした...．このあたりは関数プログラミングの腕の見せ所といったところだと思うので，もう少し理解を深めたら再度実装しなおしてみたいです．まあ，取り敢えず今のところはこれでいいかなという感じです．早く初心者を抜けて中級者くらいになりたいところですね．

参考

WEB+DB PRESS Vol.67

WEB+DB PRESS Vol.67


珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

Leiningenのzsh補完関数を利用する

clojure

Leiningenの調べ物をしていてgithubのリポジトリを見ていたらzshの補完関数があったので使ってみました．

導入方法

概要はzsh_completion.zshのコメント欄に書いてあります．
zshの$fpathの通ったディレクトリにzsh_completion.zshという名前のファイルをダウンロードして，そのファイルの名前を_leinに変更すれば利用できます．

$ cd /Users/yag_ays/.zsh/functions/Completion
$ curl -O https://raw.github.com/technomancy/leiningen/master/zsh_completion.zsh
$ mv zsh_completion.zsh _lein

使い方

lein [TAB]とすればコマンド一覧が表示されます．また，lein test [TAB]とすればテスト一覧が表示されます．
f:id:yag_ays:20120223001249p:plain
f:id:yag_ays:20120223001817p:plain

地味に便利...!!

参考

ホームディレクトリの配置

新しいMacBookAirを買ってからというもの，大幅に改心してホームディレクトリを綺麗に使うように心がけている．と言いつつも最近少しサボリ気味でファイルが散乱していたので，整頓をすると同時にもう一度気を引き締めるためにも自分のホームディレクトリの使い方を整理しておこうと思う．

環境

Mac OS X 10.7.3 Lion

ホームディレクトリ詳細

$ tree -d -L 1
.
├── Desktop
├── Documents
├── Downloads
├── Dropbox
├── Library
├── Movies
├── Music
├── Pictures
├── Public
├── Sites
├── VirtualBox\ VMs
├── dev
├── local
├── mnt
└── project

15 directories
  • Desktop
    • 雑多なファイル置き場
    • scpするときは大抵Desktopに保存する
    • スクリーンショットのファイルが散らばっている
  • Documents
    • 事務などの書類置き場
    • Scansnapのpdf出力先
  • Downloads
    • Chrome/Firefoxのダウンロードフォルダ
    • 大抵pdfが散乱している
  • Dropbox
  • Library
  • Movie
  • Music
  • Pictures
  • Public
  • Sites
  • VirtualBox\ VMs
    • VirtualBoxのディレクトリ
    • (ただし現在はHDD容量圧迫のため中身を退避させている)
  • dev
    • プログラミング全般
    • 雑多なスクリプトやgit cloneしたディレクトリが入っている
  • local
    • sudoで入れたくないスクリプト置き場
    • ./configure --prefix=$HOME/local; make; make install
    • ソースコードはlocal/srcにwgetで入れる
  • mnt
    • sshfsでリモートサーバをマウントする際に使うディレクトリ
    • 普段は空のディレクトリ
  • project
    • 仕事系全般のディレクトリ
    • "YYYYMMDD{project_name}"みたいなフォルダが大量に入っている

結構自分で適当に作ったり人のをパクったりしているので，統一感が無くヘンテコな感じなのかもしれない．Geek/Hacker/Linux userのスタンダードみたいなものがあれば知りたい．

Clojure閑話

clojure

最近全然プログラミング出来ていなくて書くこともないので，Clojureで気になるポイントや4Clojure.comの途中経過を書くことにする．
f:id:yag_ays:20120213234319p:plain
Easyでもちょっと大変になってきたが，あとは問題をこなしていくだけという感じもある．まだMediumに手を出していないが，頑張れば解けそう(だと思いたい)．


Clojureプログラミングに関して

  • アルゴリズムを当てはめる/再発明する/組み合わせる
    • 入力形式と出力形式は決まっている
    • 処理の部分を考えるのが問題なのだが，大抵は入力のデータ形式をどう変形していくかを考えるのと同義
    • データ形式にあった関数を適応することが大事
    • 特殊な例に特化した関数を使えば簡単なこともあるけれども，使わなくても処理を考えれば書ける(4Clojureでは関数を再実装する問題が多い)
    • 何も考えずに書くならloop&recurとかでゴリ押しする

このへんはLISPの哲学なりClojureの便利な機能を見ると納得する部分が多そうなので，あとでプログラミングClojureを読み返そうと思う．



4Clojureについて

  • 人の解答を見ると非常に勉強になる
    • ElementaryやEasyだと一つの関数で簡潔に書ける場合が多く，特殊な用途に用いる関数を知ってるかどうかみたいな問題もある
    • 泥臭く解いてから他人の解答を見ると関数1つであっさり解いている場合もあり，様々な関数を知る良い機会になる
    • 特殊な関数で簡潔に書いている解答を見て「それで書けるのね」で終わるのではなく，データ形式をどういう視点で観るかという裏の部分が大事
    • 実際にコードをステップごとに動かして見て，データがどう変わっていくかを確認すると面白い
    • 同じような泥臭いコード書いている人を見かけると親近感が湧く（良くない


Clojure歴がようやく1ヶ月になって，ちょっとはClojureのことが解ってきたかもしれない．関数型言語に慣れるのが精一杯で，最初のうちは問題を前にして全く手を付けられないということが多かったのだが，次第に取っ掛かりはつかめるようになってきた．最近では，ゴリ押しで書くか，それとも関数を組み合わせて綺麗に解くか...といった感じで色々と手札を眺めて考えるのが非常に楽しい．