o(np)のdiffアルゴリズムを作りました。
元ネタはこの辺。
An O(NP) sequence comparison algorithm

なんで車輪の再発明したかというと、既存のライブラリだと挙動がわからない上に、使い勝手がいまいちだからです。
自分で全部書けば、自由自在（ぉ
とりあえずリファクタリングの余地は多々ある感じですが。

一般的な意味でのdiffと違うところと言えば、追加／削除のみしか考えておらず、「置換」がありません。
けど、アルゴリズム上「置換」に当たる場合は「追加→削除」または「削除→追加」のいずれかの順番でSESの中に現れるので、その場合を「置換」と処理すればよいかと思います。

使い方とかは暇があったら書く。

このあたりを参考にさせてもらいました。日本語の解説ではこれが一番わかりがよく正確だと思います。
diff(1)

JavaScriptで文字列型から整数型への変換速度比較
http://kur.jp/2009/10/06/stringtoint-by-javascript/
というのがあって、なんかコードを見てたらなんか思うところがあったので追試してみた。
結果から言うと、だいたい傾向は一緒だった。IE用の回避コードを入れてみて気づいたけど、実行順序によって速さが変わるかもしれない。(一度読み込んだ関数は二回目は若干速い？

結果はこちら

firefox
6
6
6
119
274 

IE
801
781
851
2003
1553 

chrome
311
292
299
135
234

screenには大変なじみがあるのではないかと思いますが、最近windowの縦分割（左右に分ける）をしたくなり、tscreenやscreenのパッチなど色々と考えた末に、tmuxにしてみました。

理由は特にない(^^;;んですが、使ってみた結果tmuxの方が若干見た目に奇麗であるように感じました。

現在最新版はバージョン0.9なのですが、ドキュメントがなくソースを読むしかない（？）ので、軽く使えるコマンドについて言及したいと思います。

とりあえずmacの人はmacportsにあるのでコマンド一発ではいります。

そして、次は設定ファイルをおきましょう。screenでいうところの.screenrcは、.tmux.confというファイルになります。
私の設定ファイルはこちらをごらんください。
基本的にソースに付属しているscreen-keys.confをもとにしています。
このファイルを.tmux.confにリネームしてホームフォルダに置くだけで、screen風なキーバインドになります。

さて、screen-keys.confだけだとwindowを左右に分割することができないので、以下の設定を書き足してあります。
(他にも書いたんですが、ど忘れ・・・・)

こうして、tmuxを立ち上げたあとC-a C-Sで画面を分割し、C-a C-hで分割を左右にすることができます。

さて問題はこの「select-layout even-horizontal」というコマンドをどこから見つけてくるかです。ドキュメントがないっぽいので、ソースを見ます。
ビビらなくても大丈夫。大変奇麗に作られてるのですぐに読めると思います。

ソースをここからダウンロードして展開してみてください。
そして、cmd-から始まるファイル名のファイルを探します。これが全部コマンドになっています。バージョン0.9だとこんな感じになっています。

ここから「cmd-」を除いた部分がコマンド名です。機能はだいたいコマンド名見ればわかりますね。
各々のコマンドは引数を取ったりします。それを調べる時はソースを見ます。
たとえばさっきの「select-layout」であれば「cmd-select-layout.c」を見ます。すると、こんな感じのコードが見えるはずです。（一部抜粋）

細かい説明ははしょりますが、というか理解してないのですが、ここからコマンド名が「select-layout」であり、エイリアスが「selectl」であることが読み取れます。
ちなみにこの書き方はxwindowの拡張であるglxの実装の一つであるcompizのプラグインもこういった書き方になっているので、見慣れておくといいような気もします。

次に、引数ですが次の部分に注目します。

はい。ここで「even-vertical」とか出てきましたね。細かい説明はまたしてもはしょりますが、ここが引数でありそうな事はぱっと見でわかると思います。わかってください。
これをもとにさっきの設定を見てみましょう。

今まで見てきた通りですね！

じつは、他のコマンドもだいたい似たような感じになっています。それぞれのコマンドは非常にコンパクトにわかりやすく書いてあるので山勘で何とかなるかと思います。

しかし、0.8系と0.9系でコマンドが変わったりしてるようなので、まだちょっと注意がいるかもしれません・・・・

というかんじで、みなさん楽しいtmuxライフをおくりましょう！

キーワード自動リンクの話を某勉強会でしました。その資料を公開します。

自動リンクのためのデータ構造としてTrieを採用し、今回は有名な実装であるsenna, Tx, dartsの比較をしました。
それぞれのライブラリの背景は次の様なデータ構造です。

• senna - パトリシア木
• Tx - LOUDS
• darts - Double Array

今回の実験はとりあえず実装しましたレベルなので、厳密な速度や容量にはなっていない可能生があります。
というのは、それぞれのライブラリを精査したわけではないからです。
またキーワード抽出した結果がそれぞれで若干異なっています。抽出できたキーワードの件数に大きなさや検索にかかる時間に相関が無さそうなので概ね正しいと考えることにしました。

というわけで、ご参考まで。

Txでdartsのようなtraverseをする関数を作ってみました。

使い方はdartsのtraverseと同じだと思います。たまたま作ったのでパッチをそのまま貼っておきます。動作は未保証。dartsよりも爆速でふきました。

はてなのようなキーワードリンクをRubyで付与する実例
と、いうのをつくってもらったので、これをもとにCでsennaのpatricia treeを試すプログラムを書いたよ。

機能的にはとりあえずキーワードの検出だけ。

Darts: Double-ARray Trie System

http://chasen.org/~taku/software/darts/

dartsというのは、Trie木をdouble arrayで実装したライブラリです。ヘッダファイル一つだけの配布なので大変使いやすい。

今回HAT-trieを実装してみるにあたって、Trie木の部分の実装としてこれを使ってみることにしました。

しかし、サンプルが動かない・・・・！どうやらよく見るとテンプレート周りとconstを付け加えた際に、もともとのサンプルが動かなくなった模様。
なので、これを修正しました。別に大したことはしていません。

activerecordの様なDBラッパーを作ろうと思って、 @ujm の協力の下module_evalを使って実装してみた。
必要最小限のことしか書いてないのでDBラッパーとしては貧弱だけど、module_evalの動きに注目してみてほしい。
本物のactiverecordも似たような実装をしていたと思う。（うろ覚え）

これを次のように使う。たとえばuserテーブルを扱うクラスはこんな感じ。

ModelBaseクラスを継承し、table_nameメソッドでテーブル名を指示しているわけです。

で、ポイントはModelBaseクラスの次の部分。

UserModelの冒頭でtable_nameとこのメソッドを呼んでいます。

module_evalは、そのメソッドが呼ばれたところをselfにして実行されるメソッドであるため、このtable_nameメソッドの中で定義されているget_table_nameは、UserModelのクラスメソッドとして定義されます。

つまり、UserModel内でtable_nameが呼ばれた時点では、次のコードと同じことをします。

こうすることによって、プログラム中でテーブル名をハードコードしなくてもすむようになるとともに、countなどの関数を親クラスで定義できるようになるわけです。

例えば、この方法で作ったクラスで全レコード数を数えるコードはこうなります。

大変すっきりしていますね。

蛇足：

これはtwitterのポストを扱うために書いているプログラムの一部です。
rails使おうかとも思ったのだけど、railsはまだ多機能すぎるためこの程度なら書いてしまった方が悩みが少ない（重いとかファイルの配置とか拡張性とか）かと思って自分で書いています。

しかし、自分でフレームワーク作るかというと・・・・たぶんないですね。
フレームワークは必要じゃない機能もたくさん足すことになります。
なんの目的もなしに機能追加を繰り返していくと、フレームワーク自身のメンテナンスに負荷がかかるようになってしまうし、コードの自由度がどんどん下がっていきます。

それよりは、構造化を心がけながらプログラミングをし、拡張性を担保しながら、必要十分なものを作っていく・・・と、いうのが賢いプログラミングである気がしました。

「テクノロジーが重要なんだ」

こういう人は少なくないです。工学部を今年卒業する自分としても、「テクノロジーが重要」というのはとても同意できることです。
しかし、これが一度サービスに関する議論になった時どうでしょう？
私はこういうときにいつもこういいます。

「技術的問題はほとんどの場合解決可能なので、ユーザが受けるべきメリットについてよく考えてください」

これがなかなか難しいらしいことに最近気づく。
技術者は「技術的面白さ」が「一般人の感覚から離れすぎている」ことで、ユーザのメリットを考えにくい傾向があるように感じられる。
これはよくよく指摘されていることです。
が、面白いことに「技術者じゃない人」も同じく、「技術ありきでサービスを考える」傾向がとても強いことに最近気づいた。
やっかいなのは技術に関する知識がない分、発想が貧弱だということだ。

よくgoogleが引き合いに出される。（一応特定個人のことを言ってるわけではなくて本当にそういう人が多いということです。）
だいたい理屈はこんな感じだ。
「googleにはpagerankというテクノロジーがあった。かならずイノベーションにはテクノロジーが必要なんだ」
「googleにはcloudを持つ技術があった。だからイノベーションにはテクノロジーが必要なんだ」
しかし、これをいってる人の何人がpagerankによる効用やcloudによる効用を説明できるのかはかなり疑問です。
「テクノロジーが必要」といいながら、その実「テクノロジーが本当に重要だったかどうか」については全く検討されていないように感じられる。
とくに「cloudを持つ技術がある」というあたりは、もはや末期的な発言に聞こえる。cloudに関する技術的な定義は大変あいまいで、技術がわかる人は少なくともこういう発言はしない（と、俺は少なくとも思う

私はここに「テクノロジーの神話」があるように思えてならない。

もうテクノロジーの時代は去ろうとしているということに気づかないといけない。
「サービスの時代」といわれ、先進国は三次産業にうつっているといわれて久しい昨今。「テクノロジーの発明」に固執することはおかしいのではないだろうか？

もはやほとんどの電化製品は技術の集大成であるということを認識しないといけない。webサービスはもっと多くの技術の上に成り立っている。
RDBひとつとってみたところで、技術の集大成だ。
もはやフィラメントを光らせたらそのまま製品にできるような時代はとっくの昔に終わっている。ひとつの技術がイノベーションを起こせるというのはすでに時代錯誤でしかない。

現代のテクノロジーにおいて必要なことは2つ。「市場をみること」と「多くのテクノロジーを知ること」だ。
市場を見ることで、どのようなテクノロジーが必要とされており、なにを開発するべきかを知らないといけない。
そして、市場の問題を解決するために、適切なテクノロジーを選択できなくてはいけない。

もし、現代にイノベーションが求められているというのであれば、「技術の発明」に固執してはいけない。
イノベーションは、テクノロジーの与えた経済的・社会的インパクトで計られ、しかも技術の発明がそのまま社会にインパクトを与える時代は終わってしまっているからだ。
今はむしろ、与えるべきインパクトから逆算することが求められている。与えるべきインパクトから、適切な技術を開発・選択することが求められている。

今一度真摯に「テクノロジー」「イノベーション」という言葉について考えてほしい。
本当に、あなたが考えている「pagerank」や「cloud」がイノベーションに必要だったんだろうか？むしろ、単純に「検索結果がよかったから」じゃないだろうか？
インターネットは本当にあなたの生活を変えたのだろうか？ニコニコ動画がなかったら？Amazonがなかったら？googleがなかったら？あなたはwebサービスがなくてもインターネットに感動しただろうか？

こういう言い方をしてもいいかもしれないです。あなたの「目で見たもの、耳で聞いたもの、肌で感じたもの」を信じてください。
本当にpagerankにあなたは感動したのでしょうか？メディアにだまされてそんな気がしてるだけじゃないですか？
本当にインターネットに感動したのでしょうか？今あなたの見ているものはインターネットなんですか？

重要なのは、事実がどうだとかではないです。あなたの目で見、頭で考え、そして納得したことなんでしょうか？

誰かが作った「テクノロジーの神話」に騙されてませんか？

今日の日経新聞朝刊に「科学研究　国の役割増大」という記事があって面白かったので転載。

ドイツでは、ある完了が大蔵大臣に銃を突きつけるようにして、科学研究費の獲得に勤めていた。その官僚の名前はフリートリヒ・アルトホーフという。

（中略）

彼は優れた科学上のアイディアを持ちながら、それを発展させる資金がないために困っている人物を見つけると、一存で研究費を投入して完成に導いた。あるいは優れた能力を持ちながら、なかなか教授になれないでいる人物を見つけると、大学側の反対を押し切り、教授に任命した。

そうした研究者が数年もすると、次々にノーベル賞を受賞して言った。そのため彼は後年「ノーベル賞受賞者のゴッドファーザーと呼ばれた」

（中略）

しかしその反面、アトホーフはいつまでも国家財政に頼っているのでは、限界があることを見抜いていた。彼は巨額な民間資金が科学研究に投入されている米国を横目で見ながら、それに強い危機感を抱いていた。そこでひそかに同様に仕組みをドイツに導入する計画を練り始めた。

しかし彼の企画はスムーズには進まなかった。

（中略）

アルトホーフの没後百周年にあたる2008年１０月彼の人物や功績を再検討しようと、八カ国の報告者が参加した国際シンポジウムが開かれた。シンポジウムでは、今後科学研究はいかなる資金によって支えられるべきかという点に議論が集中した。

「役に立つ知識か否かは、市場によって選別される。市場から求められない研究分野が消滅するのは、当然の結果である」「科学研究にかかるコストは、その成果から直接利益を得る企業が負担すればよい」「なんらの企業利益も生まないような科学研究は支援する価値がない。」・・・・こうした発想が現代では主流となっている。

しかし学問とか科学研究は、レンガを一つ一つ積み上げてゆく作業である。一つ一つのレンガは目に見える利益を生まなくても、それがなければ知識全体がつみあがっていかない。

（中略）

この現代では新たな研究成果は、出資者の私有財産となり、他者が自由には使えないケースが増えた。

（中略）

大学予算削減が連続する時代には、第二、第三のアルトホーフもまた欠かせない。

なるほど。研究成果と企業云々の部分に関して似たようなことをドラッカーも実は書いている。

テクノロジストの条件　ドラッカー

ｐ１３１

近代企業は、いわば技術の産物である。（中略）今日の大企業のルーツは、最初の大企業である１９世紀半ばの鉄道、つまり当時の技術的イノベーションだった。それ以降、今日のコンピュータメーカーや製薬会社に至る成長企業のほとんどが、それぞれの時代の新技術による産物だった。

それどころか、やがて企業が新技術を生み出すようになった。（中略）技術は、イノベーションとして社会的に有効なものとなる上で、ますます企業に頼るようになった。

今日たまたま素粒子物理の友人と話していたが、「加速器一回まわすのに一千万くらいかかる」という話である。一回の実験で一千万。ひとつの研究をなすのにも世界中の企業からお金を集めなければない世界がここにある。

素粒子物理はともかくとして、実際に企業活動をベースとして技術を捕らえる事に関して、ドラッカーは「技術を予期することが肝心だ」と説く。

テクノロジストの条件　ドラッカー

p132

第一に、技術は神秘的なものでも予期できないものでもない。合理的に予期することは可能であり、そうすることが必要である。

（中略）

第二に、技術は事業活動と別種の活動ではない。そもそも事業と別のものとしてしまったら、マネージメントできない。

（中略）

技術は把握できないとする考えは、もはや時代遅れである。まさにこの考えが技術に対する恐怖をもたらす。発明は予期したり計画したりできないとする考えも、また間違いである。

（中略）

特にイノベーションについては、予期すること、計画することが重要だって、かつ必須である。

「技術を予期することが容易だというのではない」と言ってはいるが、繰り返し繰り返し、技術やイノベーションを予期することの大切さを説いている。おもしろいのは、この続き。

マネジメントが関心を持つべきものは、発明ではなくイノベーションである。イノベーションとは社会用語であり、経済用語であって技術用語ではない。（中略）イノベーションは、たとえ発明から生まれることが多くとも、発明と同義ではない。

言われてみると当たり前のことなんだけど、実はこの視点、結構かけているように感じることが多い。
正直よく「こんなことできるなんてすごい！イノベーションだ！」とか「これが開発できたら今までになかった！イノベーションだ！」ときいたりするんだけど、その経済効果とかってあまり考えられていないなぁとよく感じることが多い。
結局売れなかったものは「イノベーション」と呼ばないにもかかわらず、なぜか開発段階やコンセプトの段階で、この「経済効果」という概念を欠いているものが多いように感じることが多い。
むしろ個人的な感想としては、開発やコンセプト段階で経済効果について言及することが悪とさえ思われてるんじゃないかと思うことすらある。

また一方で、「イノベーションなんか予期できない」と言っている人がいますが、実は割りと限定的に予想することは可能だったりします。それなりの業界知識と工学知識があると、「何があたるか」はわかんなくとも「何が可能そうか」はわかるし「何が売れそうか」もなんとなくわかる。俺的に問題は「可能そう」でかつ「売れそう」なものを考えるのが案外難しい。

こっからは持論ですが、結果的に工学や科学・ソフトウェア、なんでもいいんですが、そういったものに対するそれなりに深い知見と、ある程度のマーケットへの洞察が「イノベーション」を起こすためには重要であると思っています。「それなりに深い」っていうのは難しいところですが、工学が全くわからない人は論外だけど、それほどマニアックでもないといったところであるきがします。

現に工学部の研究室の研究というのは、現代の技術のちょっとした発展を扱っているというものが多いです。結局研究もほとんどのものは従来のものに自分なりに方向付けをして付け足していると考えてもそれほど間違ってはいないと思います。これからの企業は、現代のテクノロジーの把握と、マーケットを見据えた方向付け、そして資源の集中と開発という技術とともに発展していく形というのがいいのではないかなと思います。技術の発展には企業活動による資金の供給が必要であり、企業はマーケットを見据えその方向性をコントロールすることで技術をお金に変え発展する。こういう技術に対する先見性と経営が必要なんじゃないかなと思う今日この頃でした。