2009-03-01
■ [event] Tsukuba.R #4
40分間だけ参加したｗ
本当はもうちょっと前に筑波に行ける予定だったんだけど、経路検索の「新宿から12:24発の大江戸線光が丘行きに乗る」という指示に盲目的に従ったら、 降りるべき時刻に本当に光が丘に着いてしまったため遅れました。何を言ってるかわからねーと思うが、大江戸線はこういう形 をしているので逆方向も光が丘行きだったりする可能性があるらしい。うーむ。
というわけで@wakuteka先生の「Rで学ぶ遺伝子多型解析」だけ聞いて帰ってきたのだけれども、Tsukuba.Rは素晴らしいイベントですね。
何がって、「プログラマーが遺伝子研究の話を聞くイベント」というのが他に存在するだろうか(いやない)。 こうやって、違う分野の人が交流することで新しい発想が生まれたらいいですね。学際的っていうんだっけ。
次回は東京会場らしいので、近場の人は見に行ってみるといいと思うよ。
■ [juggling] ナランハ
日本唯一の(?)ジャグリング用具専門店。板橋にある。
- カタログに載ってるほとんどのアイテムについて、見本が陳列されてる。
- 見本は実際に投げてみることも可能。
- なので、それぞれのアイテムの「新品の状態」じゃなく、「しばらく使ったあとの状態」が分かる。
- バングーボール、使い込むとあまり綺麗じゃなくなるみたい…。残念。あと思ったより一回り小さかった。こういうのが分かるのも良い。
- エクサボール重すぎワロタｗｗｗｗなんという鈍器
- だけど若干変形するので、危険性は下げられている模様
- ジャグリングのDVDも、自由に試聴可能(!)
せっかくだからビーンバッグを3つ買った。 送料がかからない分通販するよりも安いんだけど、板橋までの交通費を考えるとあまり意味がないと思う。 あくまでも、実際に見たり投げたり触ったりできることに価値がある。
あ、あとShibuya.lispで佐野さんにボールを一つもらいました(これで4個)。4個あれば少なくとも一年は遊べる。
2009-03-03
■ [lisp] Lispjobs.jp : Lisp系専門の求人サイト
Lispプログラマを必要としてる企業や、Lispで仕事したい人のためのサイトができたそうだ。
英語版がオリジナルらしい。2月は4件の求人ありとか、結構なペースじゃん。
jokeカテゴリに「Arcプログラマ募集、ただし経験7年以上」とかあってワロタ。
2009-03-05
■ [scheme][mac] Ikarus Schemeを動かしてみよう
IkarusはR6RSにほぼ*1準拠した、Schemeのインクリメンタルコンパイラである。
最新リリースは一年前だけど、0.0.4がそろそろらしいし、MLもそこそこ投稿がある ので生きてはいるようだ。
まずはダウンロード。
普通にconfigureすると、gmp.hとlibgmp.soがないとか言われる。locateで探してみると、MacPortsのやつ(port install gmp)が あるらしい。こうか。
./configure --prefix=/Users/yhara/bin/scheme/ikarus-0.0.3/ CFLAGS=-I/opt/local/include LDFLAGS=-L/opt/local/lib
できたのでmake && make install。
~/binにもsymlinkを作っておく(ikarus[Enter]で起動できるように。僕の環境では~/binにパスが通してあるのだ)。
とりあえず --help。
/Users/yhara/research/r_6rs/ikarus-0.0.3 % ikarus --help Ikarus Scheme version 0.0.3 Copyright (c) 2006-2008 Abdulaziz Ghuloum Unhandled exception: Condition components: 1. &who: open-input-file 2. &message: "missing entities" 3. &i/o-filename: "--help"
そんなファイルはないって(笑)。
-hらしい。
つーか、「インクリメンタルコンパイラ」だけど、コンパイル結果をファイルに保存するみたいなオプションはないんだな。 使い方はインタプリタっぽい。
Ikarusには短いPDFのドキュメントがある。 第2章に「○分でわかるR6RS」みたいな説明があって、importの使い方、ライブラリの書き方、レコード型、例外について触れられている。
第3章はIkarus独自のライブラリについて。parameter、gemsym(!)、pretty print, trace, time(時間計測)など。 Gaucheのような「実用上便利なライブラリ」みたいな方向には思想が向いてない雰囲気を感じる。 まあ、コンパイラだし、「がりがり数値計算しようぜ！」という方向性なのかも。
aobenchを動かしてみよう
なんと、デフォルトではsrfiのライブラリが入ってないみたいなので、ドキュメントに従ってインストールする。
/Users/yhara/research/r_6rs % bzr checkout --lightweight http://bazaar.launchpad.net/~ikarus-srfi-team/ikarus-libraries/srfi srfi-ikarus bzr: ERROR: Not a branch: "https://launchpad.net".
ちょｗ
いろいろ試した結果、以下ならとりあえずうまく行く模様(正しいかは知らん)。
/Users/yhara/research/r_6rs % bzr checkout --lightweight https://code.launchpad.net/~ikarus-libraries-team/ikarus-libraries/srfi srfi-ikarus
なんかsrfi 27がうまく読み込めない (つづく？)
*1 94%らしい
2009-03-06
■ [scheme] (Petite) Chez Schemeを動かしてみよう
Chez Schemeはscheme.com(!)で配布されている、商用/フリーのSchemeインタプリタである。
余談だが、「Chez」は「シェ」と読む。フランス産なので、末尾のzは読まない。「○○の家で」といった意味の前置詞らしい。
メインプログラマは3imp.pdfのKent Dyvbig(ディビッグ)である。「プログラミング言語Scheme」の英語版も、同ドメインで公開されている。
Chez Schemeは商用なので、フリー版のPetite Chez Schemeをダウンロードしよう。 沢山あって迷うが、pcsv7.4-i3osx.tar.gz でいいはず。OS 10.4とか書いてるけど、大丈夫かな。
解凍したら、custom/ReadMe(変わったファイル名だ)に従ってインストールを行う。
./configure --installprefix=/Users/yhara/bin/scheme/chez/ sudo make install
homeに入れてるのに、sudo付けないとなんか怒られる。
終わったら、環境変数を定義するらしい。おい、めんどくさいぞ。
例の通りやってもうまく動かなかったので、適当にシェルスクリプトを書いた。
~/bin/chez-scheme:
SCHEMEHEAPDIRS="/Users/yhara/bin/scheme/chez/lib/csv7.4/i3osx" /Users/yhara/bin/scheme/chez/bin/petite
-hも-helpも--helpも効かないが、^Hには対応している。印象+1。
Petite専用のリファレンスはないが、きっとChez Schemeのドキュメントを見ればいいはず。
■ [softs] Dropboxを始めてみませんか
容量アフィリエイトと聞いて！
以下のリンクからDropboxに登録すると、僕とあなたに250MBのディスク領域がボーナスとして加算されるらしいです。まだDropboxに 登録していない人はぜひ。
Dropboxは、一言で言うと「全自動オンラインバックアップソフト」です。 Windows/Mac/Linuxに対応していて、それぞれのOS用の専用クライアントを入れると、 ディスク内の特定ディレクトリがDropboxのサーバに同期されるようになります。
同期はCPUが空いたときに随時行われるので、バックアップについて何も意識する必要がありません。まさに全自動。 また、各ファイルは更新時に上書きされるのではなく、Subversionのように各バージョンが保存されるため、間違った編集をしてしまっても安心。
それって容量とか大丈夫なの？と思われそうですが、僕は昨年の秋から使ってて、2GB中の4分の1(500MB)しかまだ使っていないようです (Dropboxに置いてるのはソースコード関連なので、テキストが主です)。足りなくなったら、適当に古いファイルを消せばいいかな、と思っていたり。
あと複数台のマシンでデータを共有したり、別のユーザとデータを共有したりもできるそうです(僕は使ってないですが)。
まあ、とりあえず、登録して使ってみるといいとおもうよ…！
余談
似たようなものとして、ZumoDriveというサービスもあります。 Dropboxがシンクロするファイルを全てローカルにも置いておくのに対し、ZumoDriveは基本的にサーバ側にしかデータを置かず、 ローカルではファイルの一覧だけが見えていて、使いたくなったときにシームレスにダウンロードされるようです(自前でファイルシステムを書いてるんだと思う)。 「大量のデータを」「多数のマシンで」共有したい場合は、ZumoDriveもいいかも知れませんね。
■ [ruby] 「gemのインストールを10倍高速化する方法」
from http://buddingrubyist.com/2009/02/14/how-to-speed-up-gem-installs-10x/
~/.gemrcの末尾に
gem: --no-ri --no-rdoc
という行を追加すると、riやrdocのリファレンスがインストールされないので速いよ！とのこと。
コメント欄見ると「rdocはともかくriは要るだろjk」とか書いてあって面白い。
■ [scheme] Ikarus Schemeを動かしてみよう(2)
前回のあらすじ：コンパイルは通ったしすげー速いけどSRFIの一部がロードエラー
毒を食らわば皿まで、ということでMLで聞いてみた。
> Ikarusのバージョンいくつ？古いの使ってるだろ？(意訳)
いや、確かに1年前のやつ使ってたけれども、それ最新のリリース版だから…！
さっさと0.0.4リリースしろよ(あと完成度に比べてバージョン番号が小さすぎるだろjk)と思いつつ(とても親切だったのでそんなことは言わない)、trunkをダウンロード。
教わったとおりにconfigure (port install libffiが必要だった)。
./configure --prefix=/Users/yhara/bin/scheme/ikarus --enable-libffi CFLAGS=-I/opt/local/include LDFLAGS=-L/opt/local/lib
あとはmake, make installでおｋ。やったーIkarus 0.0.4-rc1+できたよー
→SRFI動いた！きた！これで勝つる！
2009-03-09
■ [ruby] Hash#+, Hash#-
という記事でHash#+, Hash-を定義しているのを見かけたのですが、
>> hoge = {:fuga => "bar" }
=> {:fuga=>"bar"}
>> hoge += {:hige => "baz"}
=> {:fuga=>"bar", :hige=>"baz"}
>> hoge -= :fuga
=> {:hige=>"baz"}
これなかなか良くないですか？
まあmergeも、「.merge」と書いてあったらレシーバがハッシュだと確実に分かるというメリットがあるんだけど。 型が分かるような変数名を付けていれば混乱しないはず。
2009-03-10
■ [ramaze] 新しいRamazeのWikiを翻訳する方法
Ramazeの公式サイトが新しくなって、Wikiも多言語化されたんだけど、 あいにく日本語ページは真っ白のまま。
翻訳するにはどうしたらいい？とメールで尋ねたら、githubのプロジェクトをforkしろと。なんと。
とりあえずforkしてみた。
みんなもとりあえずforkするといいよ！
そういえば旧Wikiを翻訳されてた方がいたと思うんだけど…、どうなったんだろ。 Wikiの内容は旧Wikiとそんなに変わってないので結構使えると思われ。
■ [scheme] R6RSのsyntax-caseが抱える？問題点
まだちゃんと分かってないけどメモ程度に書く。
Scheme知らない人向けにいうと、syntax-caseというevalみたいなもんがあって、それを使うと 別モジュールの名前空間の変数を参照したり変更したりできてしまってまずいんじゃない？という話。
まあRubyとか触ってると、別クラスの定数を動的に参照・追加とか普通にできるしそんなもんじゃねと思うけど、 R6RSの件は「それを分かった上でこういう仕様になってるのか」が不明確だからどっちなの？ということらしい。
という話をShibuya.lisp TT#2のときにfujita-yさんから聞いた。
こっからはScheme知ってる人向け。
R5RSにはsyntax-rulesというマクロシステムがあって、これはパターンにマッチした部分を置き換えていく感じで動的なコード生成を行う。 このパターン言語はそれ自信でチューリング完全なんだそうで、理論的にはマクロ展開時にどんな計算もできるんだけど、 Schemeのコードがそのまま書けるわけではないので、複雑なことをしようとするとマクロを書くのが大変になる。 あと、symbol-appendみたいなものがないので動的に新しい名前の関数とかを定義できなかった。
そこでR6RSにはsyntax-caseという、より強力なマクロシステムが入っている。こいつはマクロ展開時に普通の Schemeのコードを書けるので、マクロ定義にmapとか使い放題。あと、datum->syntaxってやつがあって、これを使うと 「マクロ展開時のシンボル」を、「実行時されるコード」に変換できるらしい。だからマクロ展開時にシンボルを連結して、 それをdatum->syntaxで埋め込んでやれば、関数名の動的生成とかも可能なわけだ。
だけど、datum->syntaxで作った名前はそのライブラリ内の名前空間を参照するから、 下手なマクロを作ると、ライブラリの外側からライブラリ内をいじくれてしまうということらしい。
2009-03-11
■ [scheme] Ikarus Schemeを動かしてみよう(3)
MLに動いたよありがとうメールを書いた。
んでAOBenchですが。インタプリタで30分から45分かかってたコードが、7分ちょっとで終わりました。 コンパイラすげー。
まあGaucheでも匠の技でチューニングすれば26秒になるわけなんですが、 「何もしなくてもそれなりに速く動く」っていうのは結構なメリットではないかと思いました。
あとmjtさんのYpsilon版が、全く変更せずにIkarusでも動くんだよね。 R6RSえらい。
Ikarusのダメなところは、間違いなくドキュメントが古いことです(笑)。ドキュメントの質は悪くないんですが、ドキュメント担当の人が 燃え尽きてしまったのでしょうか…。0.0.4のリリースが待ち望まれます。
■ [scheme] Ikarus Schemeの動かし方まとめ('09春)
R6RS準拠のSchemeコンパイラ、Ikarus Schemeのインストール方法です。
ソースはML。
0.0.4が出たら、以下のような面倒な手順は不要になるはずなので、公式サイトをチェックしてください。
1. 準備
まずbazaarというバージョン管理システムをインストールする。MacPortsならport install bzr。
2. チェックアウト
Ikarusの最新版を取ってくる。
$ bzr checkout --lightweight http://www.cs.indiana.edu/~aghuloum/ikarus.dev ikarus $ cd ikarus
3. コンパイル
$ ./configure --prefix=/home/どこか --enable-libffi $ make install
MacPortsだと以下のようにしないといけないかも。
$ ./configure --prefix=/home/どこか --enable-libffi CFLAGS=-I/opt/local/include LDFLAGS=-L/opt/local/lib $ sudo make install
インストールしたbin/ikarus にパスを通しておく。
$ ikarus
で起動すればOK。(Ctrl-Dで抜ける)
4. SRFIライブラリの準備
適当な場所で
$ bzr checkout --lightweight http://bazaar.launchpad.net/~ikarus-libraries-team/ikarus-libraries/srfi srfi
とする。
環境変数IKARUS_LIBRARY_PATHを設定する。例えば /Users/yhara/research/r_6rs/ikarus/srfi にチェックアウトしたなら、
$ export IKARUS_LIBRARY_PATH=/Users/yhara/research/r_6rs/ikarus
5. テスト
以下のようなスクリプトを用意して(27.scm)、
(import (rnrs) (srfi :27)) (display "27") (newline)
コマンドラインで
$ ikarus --r6rs-script 27.scm 27
となればOK。
■ [git] learn.githubのGitチュートリアルがすごい
githubがGitチュートリアルを始めたようです。
まだ書きかけのところもあるけれど、既にある分だけでも スナップショットベースのモデルだとか、 statingって何だとか、 変更を取り消すにはどうしたらいいかとか、 「そこが知りたかったんだよ！」という説明が丁寧に書いてある。
英語だけど、Git初心者にとっては十分読む価値があると思うよ。
(3/17追記：日本語なら http://www8.atwiki.jp/git_jp/ がおすすめ、というコメントを頂いた。ありがとうございます。
それで気づいたんだけど、learn.githubの良いところは図を多用してるところだな。)
2009-03-12
2009-03-16
■ [biwascheme][javascript] 'new'をメタプログラミングするにはeval使うしかないのだろうか
BiwaSchemeで、
(js-new "Date" 2008 0 0)
とすると JavaScriptの
new Date(2008, 0, 0);
相当になるという機能があるんですが、実装が嫌な感じで、 "new Date(2008,0,0)" という文字列を作ってからそれをevalするようになっている。 (だから、 (js-new "Date" year) とか、schemeの変数をnewに渡したりするのがめんどい)
普通の関数なら func.apply(args) とかやればいいわけだけど、newはなんとかならないんですかね？
2009-03-18
■ [ruby] Ruby用PEGパーザ、Treetopを使ってみる
TreetopはRuby用のPEG(解析表現文法)のpackrat parserである。 よく分かってないけど、そういうものらしい。
PEGの特徴については適宜google検索してもらうとして(ひどい)、ここではTreetopを使って簡単な文法をパーズしてみた。
1. インストール
gem install treetop
Vim使いはvim用の色付けもインストールしておくと良いかも。
2. 文法を書く
パーザといったら(異論もあろうが)四則演算である。リファレンスを参考に、とりあえず足し算だけの文法を定義してみよう。
dentaku.treetop:
grammar Dentaku
rule additive
(number "+" number)
/
number
end
rule number
[0-9]+
end
end
使う側はこんな感じ。
den.rb:
require 'treetop'
require 'dentaku'
p DentakuParser.new.parse("1+2+3")
(環境によってはrequire 'rubygems'が必要だろう。)
dentaku.rbというファイルは存在しないが、treetopには*.treetopを直接ロードし、コンパイルして使うという機能がある(気持ち悪いw) のでこれで良い。
ちなみに
$ tt dentaku.treetop
とすることで、文法のプリコンパイルを行うこともできる(dentaku.rbというファイルが生成される。ファイル名は-oで変更可)。
3. 動かしてみる。
$ ruby den.rb
SyntaxNode+Additive0 offset=0, "1+2+3" (number,additive):
SyntaxNode offset=0, "1":
SyntaxNode offset=0, "1"
SyntaxNode offset=1, "+"
SyntaxNode+Additive0 offset=2, "2+3" (number,additive):
SyntaxNode offset=2, "2":
SyntaxNode offset=2, "2"
SyntaxNode offset=3, "+"
SyntaxNode offset=4, "3":
SyntaxNode offset=4, "3"
よく分からないが、とりあえずパーズできているみたいだ。
4. アクションを定義する
パーズができたので、yaccでいうところのアクションを定義しよう。
Treetopでは、非終端記号(上で言うSyntaxNode)にメソッドを定義することでアクションの実装を行う。
(いろいろ試した結果)以下のようなdentaku.treetopになった。
grammar Dentaku
rule additive
number "+" additive {
def value
number.value + additive.value
end
}
/
number
end
rule number
[0-9]+ {
def value
text_value.to_i
end
}
end
end
使う側は以下。
require 'treetop'
require 'dentaku'
result = DentakuParser.new.parse("1+2+3")
p result
p result.value
実行結果。
$ ruby den.rb
SyntaxNode+Additive1+Additive0 offset=0, "1+2+3" (number,value,additive):
SyntaxNode+Number0 offset=0, "1" (value):
SyntaxNode offset=0, "1"
SyntaxNode offset=1, "+"
SyntaxNode+Additive1+Additive0 offset=2, "2+3" (number,value,additive):
SyntaxNode+Number0 offset=2, "2" (value):
SyntaxNode offset=2, "2"
SyntaxNode offset=3, "+"
SyntaxNode+Number0 offset=4, "3" (value):
SyntaxNode offset=4, "3"
6
動いているようだ。
あとは公式サイトなど見て頑張ってください。
2009-03-19
■ [biwascheme] ライセンスを決めよう
メールでBiwaSchemeのライセンスについて質問をいただいたので、ライセンスを決めようと思う(遅いって？)。
とりあえず緩めで広く使われているライセンスということで、MITかBSDにしようと思うのだけど。
Scheme処理系を適当に調べてみる。
- Gauche: BSD
- Mosh: MIT
- ikarus: GPL
と思ったが「バイナリ配布は...」とか書いてあるな。JSでバイナリって何だ。
JSのライブラリも調べてみる。
- prototype.js: MIT
- scriptaculous: MIT
- jQuery: MITとGPLのデュアル
- mootools: MIT
MITが多いなぁ。
MITライセンスとBSDライセンスの違い
MIT/BSDともに、GPLとは矛盾しないらしい。
「MITとBSDはほぼ同等」ってよく言われるけど、文面は結構違うじゃないか。
- BSDにはバイナリ配布に関する記載がある。
- BSDには、派生物の宣伝に原作者の名前を(許可無く)使ってはならない、という制限がある。
- 責任を持たないことと、再配布時にライセンスもコピーしなければならないところは同じ。
つまりMITの方がBSDよりさらに緩いようだ。
というわけで
MITライセンスってことで、今後ともよろしくお願いします。
2009-03-22
■ [ruby] 「超戦略的ブロガー」をリリースしました (powered by はてな)
この記事 に感銘を受けて、任意の文章を超戦略的に変換するサービスを作りました。 (本体 / ソース)
このサービスは任意の文章を知的かつストラテジックに変換します。 ↓ この戦略的なサービスは任意の戦略的文章を知的かつストラテジックに変換します。
どうぞご利用ください。 (このサービスははてなオフィス の電源(power supply)と無線LAN環境を利用してリリースされました)
■ [event][perl] Kansai.pm#11の参加メモ
Kansai.pm #11 の適当なメモを取ったので適当に公開します。
あんまり人に読ませることを想定していません。他のレポート を補完する感じで読むといいと思います。
13:30〜 いつもと違う形式 id:naoyaのリクエスト 若い人に
飲み物は冷蔵庫からご自由に(!!)
Cell Challenge 2009 参戦記 : PFI 吉田(oxy)さん
Perlではない(特別講演ｗ)
Cellのコンテスト コンピュータ全体の知識がないと勝てない
京大情報学研究科M2->D1 理論計算機科学 P != NPを証明したい的な分野 P: 計算機で解ける NP: 計算機で多項式時間できっとできないだろう
エンジニア＠PFI
Anthy ICPC 「関連エントリ機能」
=== Cell Challenge
マルチコアを効率的に利用したい
08秋: 参加しないか Cell=めんどくさそう
08 12月: 問題発表（編集距離） PFIの同僚(chun)に誘われたので、参加
チーム名はPFI社長のSkype名から (>ω <)
09 1月：Cell the Hack 別のコンテスト MT(メルセンヌ・ツイスター)を高速化
09 2月：予選トップ通過
09 3月：昨日本戦終了 勝てるといいなぁ
=== なぜここでCell Challenge
高度なプログラム: アルゴリズムとアーキテクチャに関する深い知識が必要 Perl知らないので Webフレームワークは習得しないようにしている
=== 既定課題
編集距離 A = weight ; B = write weight -> weighte -> wrighte -> wrihte -> write A,Bの距離は4(以下)である 総当たりすると、3以下ではできないことがわかる
AとBの間の編集距離を、Cellを使ってできるだけ速く求めよ A,Bの長さは一定以下 A,Bの長さは128で割り切れる 1文字は1〜255
=== Cell
SPE SPU * 8 SXU LS MFC
PPE PPU
SPEとPPE、全然違う2種類のCPU SPEは8個(Core2Duoどころではない) # PS3は8つ中7つしか使えない
3.2GHz PPE: L1 32KB, L2 512KB SPE: LS 256KB, 128bitのレジスタが128個も(!!) SIMD(複数の演算を同時に行える, SSE/MMXみたいな) 重たい計算に
=== DPによる解法
O(nm)で解けることが知られている(n = |A|, m = |B|)
- w e i g h t - 0 1 2 3 4 5 6 w 1 0 1 2 3 4 5 r i t e
左上から順に表を埋めると、右下が答え (上と左と左上の値から計算できる)
サンプルプログラム：DPを7並列 n,m=2^17 で43秒くらい (10万×10万) (並列なしならもっと) これを 予選0.2秒、 本戦0.14秒まで縮めました 300倍くらい
=== 手法
1. アルゴリズム的に 2. SPE一個単位で 3. SPE複数個単位で
=== 1. アルゴリズム的に
SPEが7個でも7倍にしかならない アルゴリズムを改善すれば100倍くらいに 128bitのレジスタを使えば、128要素を同時にもてる
ビット並列化[H03]
ベクトルの「横に1減っているか」「縦に1増えているか」みたいな情報(D0 HP HN VP VN)を考えると j列目のやつは、j-1列目のやつから計算できる これらを使うと編集距離が簡単に計算できる
これらを128bitレジスタで計算しよう 128並列
DPの表は並列化しにくい が、依存関係が「足し算の繰り上がり」になってるのでハードウェアでできる
残り7倍
=== 2. SPE一個単位で
パイプライン 1命令＝数クロック 複数の命令が同時に走る (-> スループット、クロック数の向上 / レイテンシの悪化)
データハザード (ストール) 命令の利用するデータに依存関係があると、後ろの命令が前の命令を待つ(遅い) ループアンローリング forを一部展開する -> 計算順序を調整する(コンパイラ/手) -> ハザードを減らせる これだけで2,3倍になったりする デモ おおー # なんで
ハザード対策: 投機実行 128bitの加算がないので、32bitの加算*4(SIMD)を使う 繰り上がりでハザードが起こる じゃあ繰り上がりあり/なしを同時に実行して、後から選ぶようにするとハザードが減る (依存関係の遅延評価)
足し算の高速化 こうすると速くなりそう(実装できず) xxxx xxxx xxx xx x
スーパースカラ Cellにはパイプラインが2つある (Even/Odd) EvenとOddを効率よく使うように等価変換
=== 3. SPE複数個単位で
SPEは7個だけど、普通にやると7倍速も出ない
テーブルを128c*128のブロックに分割(cは適当な数) ブロック間は、端っこ以外依存がない ブロックの計算が終わったら、次の計算を担当するSPEにその情報を渡す PPEをマネージャとして
cをいくつにするか？ cが少ないと：SPE間のやりとりが増える cが大きいと：レジスタ不足、コンパイル時間(ループアンローリングしすぎ) 16くらいが良さげだった が、常に16ではダメ 単語の長さによって、最後の計算がSPE1つだけになったり
最後までSPE7つ使うようにしたい (x+i)/nを足していくとsumになる (5,6,6,6,6とか) これを使ってcを決める |A|が128xだとすると、nは7の倍数かつceil(x/n)が16以下になってほしい
ページング プログラムから見えるのは仮想アドレス ページング＝仮想アドレスと実際のアドレスとの対応 SPE側でページングされてないメモリにアクセスすると、100~1000万クロックもかかってしまう でもPPE側なら速い PPEで事前にメモリ初期化→ページフォールトをわざと起こす デモ(1<<24バイト)
=== まとめ
アルゴリズム的な改善が一番大事(bit並列化) 有名問題なら、本や論文でいくらでも その他の最適化＝*コンピュータに合わせた計算*をする ので、コンピュータの知識がないとだめ(パイプライン、ページング、キャッシュ、SIMD)
その後の最適化＝問題に依存したパズル ゴルフとかっぽい
流行もいいけど、基礎知識の方にも面白いものがいっぱいあるよ
=== Q/A
* C言語？ C。アセンブラはつかわず
* bit並列化の手法は？ 論文から。 研究者は何百万
* レジスタに割り付けるようなコードの確認は？ printfで確かめる
* アセンブラだとコード作るだけで大変だよね 暇だったらやってたと思う(コンパイラの生成コードを参考にしたりとか)
HTMLからの本文抽出 : id:tarao(伊奈)さん
院生 専門はλ計算、型理論、証明支援・自動証明とか Javaに動的型を入れる研究
C++, OCaml, Ruby, Perl(半年くらい), JavaScript, TeX JSで定理照明器を書いた Greasemonkeyで、問題ページを開くと自動的にsubmitするように
=== Perl
01年：掲示板CGIの改造 Perl嫌い病
08年：はてなインターン オブジェクト指向 CPAN 完治→CPAN Authorになった
=== 背景
RubyのExtractContent -> Perl移植(HTML::ExtractContent) バグを直したり、精度を向上したり サイボウズラボでも使われてるとか
なぜ本文抽出？ 例えばブクマページ 単純にHTMLからタグを省くだけだと、メニューとかまで入ってしまう 例えば検索エンジン 「この記事へのトラックバック」みたいな文字列まで引っかかると困るよね
既存のアプローチ * HTML::ContentExtractor * HTML::TreeBuilderベースで遅い、ごみが残る * HTML::Content::ContentExtractor * トークンに分解、日本語には不向き * Webstemmer(Python) * 2つのページのdiffを取る感じで本文抽出 * サンプルを与えて学習する * 一般のサイトで十分な性能が出ない
今回の手法 正規表現(高速） 本文らしさをヒューリスティックに
=== 実演
useしてnewしてextract(str)して、as_text(テキスト)とかas_html(HTML断片)を取るだけ HTMLは断片なのでvalidとは限らない(閉じタグだけがあったり)
デモ lifehacker.jp youtubeとかは無理(文章が少なすぎて「ようこそ〜」以下が引っかかる) ニュースサイトには強い 2chまとめブログは苦手(1: 以下、名無しさんが〜だけが取れたり) レスはブログだと「コメント欄」に構造が近い
=== アルゴリズム解説
1. 明らかに要らないものを落とす - headタグ - display: none - <!-- --> - など 2. HTMLを適当なブロックに分割 - div - p - 開始タグのところで切る 3. 各ブロックにスコアを - 本文っぽさ 4. つながっているブロックをまとめる(クラスタ化) - クラスタのスコア＝ブロックのスコアの合計 5. スコアの一番高いクラスタが本文
本文っぽさ - 句読点がいっぱいある - テキストノードの文字列が長い - リンクばかりが並んでいるとこは本文っぽくない
クラスタ化 高スコアのブロックが連続しているところをつなげる 低スコアのブロックは、クラスタの切れ目っぽい
閾値の設定は職人技ｗ
傾斜配点 スコアは下にいくほど減点(コメント欄のため)
=== 発展
駄目なサイトもある もっと確実にしたい
フレームワーク化 複数の抽出エンジンを試す Chain on Responsibilityパターン サイトに特化した抽出エンジンを用意(ニコニコ、youtube、amazon, ...)
GoogleAdsenseのタグを使う RSSフィードを使う
複数試して、一番良い結果を選択する 取ってきた文字列が一番長いものを選ぶ
# はてブではこれくらいやってるらしい
日々のチューニング
=== Q/A
* 日本語以外もいけそうだよね 英語はOK 文字の長さ
* 複数の本文セクションがあったときは？(ブログのトップページとか) 傾斜配点によって、一番最初のものが選ばれるはず そういう用途にチューニングされている
* GoogleAdsenseは決めうち？ 他のものも使うようになっている。 前のより2倍長かったら採用とか、選び方もヒューリスティック
* HTML5対応 まだ対応してない nanto_viさんパッチお願いしますｗ
はてな本棚
異常にPerl力の高い本棚(見たことないPerlの洋書とか)
Perlで学ぶコルーチン : id:hakobe932さん
M1 ソフトウェア開発支援みたいな研究 はてなアルバイト
=== Perl
05年：スクリプト言語に出会う Python -> Ruby -> Perl
08年：はてなインターン CPAN Authorに
=== コルーチン
1/31 関西Ruby勉強会-11 Ruby 1.9.1リリース -> Fiberについての発表が それPerlでも
コルーチンとは サブルーチンはコルーチンのspecial caseだ! (Knuth)
サブルーチンとは
メイン サブ
---------------------------------
foo
bar() --呼び出し-> sub bar {
...
<-リターン-- }
baz
コルーチン
処理を中断したり再開したり
coは協調のco
A B
---------------------------------
resume --呼び出し-> ...
...
... <------中断 yield
...
...
resume -----再開-> ...
...
...
処理の実行状態を簡単に扱うことが出来る
=== 使ってみよう
Perl(5)では提供されてない が、それCPANで search.cpan.org -> coroutine-> 38件
use Coro; XSで3000行 Coro::State(継続オブジェクト) PerlのスレッドとCのスレッドを駆使 スレッドをwaitさせとけば状態を扱えるよね、みたいな call/ccも実装できる、らしい
Coroはコルーチンだけじゃない 並行処理ライブラリ群 scheduler, async, semaphore, channel, event driven ...
Coro::Stateを使うと純粋なコルーチンが使える けどあまり使いやすくない CoroをベースにFiber.pmというのを作った(Ruby1.9のFiberみたいなインターフェイス) yieldで、中断時に値が返せるよ github
例
use Fiber;
my $f = Fiber->new(
sub{
..
Fiber->yield;
..
}
);
$f->resume; // subからyieldのところまでが実行される $f->resume; // yieldの次から最後までが実行される
=== 実用コルーチン
実行状態を簡単に扱う
宇宙船の例(上・右・下・左)
do { $s->move_up; Fiber->yield } for (1..100);
「いま何回目のループか」みたいな状態変数を用意する必要がない(Fiber内に内包されている)
複数の宇宙船を平行動作させるのが簡単
# 終わったFiberをresumeすると例外
ジェネレータ
値の列を生成する手続き(イテレータの兄弟)
列を事前に全部生成できない・したくないときに有用
Python, C#, JS1.7では言語の機能
これコルーチンで
無限factorial
..
while(1){
$val = $val * $n++;
Fiber->yield($val);
}
..
resumeする度に次の値がもらえる
無限ループだけど無限実行にならない！
ステートマシン
(1) -> (2)
^ v
(4) -> (3) -> (5)
状態＝コルーチン、状態遷移＝コルーチンの切り替え
Fiber->yield($state2)みたいに、中断するときに「次の状態」を返してやる
# 状態どうしが相互参照しているとGCできないかも...？ # 最後のステートで参照を切ってやればいいはず
並行処理 コルーチン＝「明示的な切り替えが必要なスレッド」 # これを「ノンプリエンプティブ」という(スレッドが勝手に切り替わる方はプリエンプティブ) 勝手に切り替わらないので、同期処理がスレッドほど複雑にならない Coro::Semaphore, Coro::Channel, Coro::Event
=== 利点と欠点
Pros - 状態管理がシンプル(ゲーム(Luaとか)) - 並行処理がクリーンに
Cons - それほど使われてない - 既存のクラス・クロージャ・メソッドで同じことができてしまう
=== Q/A
* resume(1)みたいに、再開時に値を渡すことは可能？ できる
* RubyのFiber.yieldは、なぜFiberがレシーバ？(インスタンスでなく) Coroだと メイン->yield みたいに、レシーバを指定する(これはちょっとめんどい) 呼び出し時にスタックに積み、resume時にスタックトップを再開
* RubyのFiberもスレッドで？ VMレベルだと思う # 僕もスレッドじゃないと思うけど、確信がないなぁ
Coroには「こうするとcall/cc」みたいなサンプルが載っている (call/ccができるということは、コルーチンくらいできるよね)
# C#だとプログレスバーを出すのにジェネレータを使うらしい
スペルミス修正プログラムを作ろう : id:naoyaさん
「もしかして：○○」 正しい答えを推定 いろいろな手法 - 辞書との比較 (今回紹介する) - 字面が似ているものしか訂正できない - 検索ログなどから推測
今回の手法 はてなキーワードを辞書として使う (間違った)単語を与えると、訂正候補を表示
考え方 辞書に正解がある 入力と正解を比較して、「誤り度」をスコア化
編集距離(本日2回目)を使う 文字の挿入・削除・置換を何回使えば正しくできるかの値 動的計画法 # これをビット並列化すると超高速になるｗ CPANではText::Levenshtein, Text::LevenshteinXS * Unicode非対応 * パッチを書くか、自前で
20万単語との編集距離を計算するわけにはいかない
対象をNグラムで絞る
例：bi-gram(2文字)
bo -> aboard, about, border, ...
入力が"bord"なら bo + or + rd -> それぞれをbi-gramインデックスで引く
2回以上ヒットするものを対象に編集距離を計算
編集距離が同じだった場合どうするか Web上でよく使われる語を採用 (DF, Document Frequency) はてブのデータ(これは非公開)を使った
編集距離を改善 Levenshtein距離は、何文字目が間違ってても同じスコア Jaro-Winkler距離: 前の文字ほど重要とみなす (伊藤xxを佐藤xxと間違う人は少ないだろう) CPANのはUnicode非対応 http://github.com/naoya/perl-text-jarowinkler/ Luceneからの移植、Unicode対応
計算方法
「雑音のある通信路モデル」
W Y
情報源->符号化->通信->復号->出力
^
雑音
音声認識とか、仮名漢字変換とか
YからWを推定したい。
argmax_W P(W|Y) Yを観測したとき、正解がWである確率(事後確率)
ベイズ推定
P(Y|W): 尤度、今回は編集距離
P(W): 今回はDF
参考文献：IIR (Introduction to Information Retreival) など
注意
このへんから集中力がなくなったので適当になります、ごめんなさい(´・ω・｀)
PerlMolの紹介 : 樋口さん
www.perlmol.org 化学構造情報 フォーマット変換とかSDFのパースなど
CPANで入る
いろいろなフォーマット MOL形式 - 原子の結合情報 PDB形式 - 巨大分子の各原子の立体座標 SDF形式 - 原子の結合情報とか SMILES
例：アラニン MOLファイル：NとかCとかOとかHが書かれている
use Chemistry::Mol;
「オープンソースで始める ゲノム・プロテオーム・メタボローム解析」 CPAN, BioPerl, PerlMol, DBD/DBI, Plagger(ちょｗ)
名札メーカー : 橋本さん
名札PDFを作成する ユーザアイコンを自動取得
Perl + PDFJ + CGI::Application
ベイズ理論と POPFile における実装例 : いいむらさん
POPFile ベイズの定理 P(Bi|E) = P(E|Bi) x P(Bi) / P(E) 1 2 3 4
1: メールの分類がバケツBiで合っている確率(これを知りたい)
3: 分類Biのメールが届く確率
= 受信メールのうち、分類Biのメールの割合
学習するほど高くなる
4: メールEが届く確率
= ってそんなもの計算できない
知りたいのは「どのP(Bi|E)が一番大きくなるか」なので、無視する
2: 分類Biの中からメールEが取り出される確率
= これも大変
メールを単語ごとにちぎって、その分類から推定する
各単語の分類があまり相関しないなら(?)わりとうまく行く
実装
Classifier::Bayesのclassify関数
2008年Kansai.pm活動報告＆Strawberry Perlの紹介 : lapis25さん
Kansai.pm = Kansai Perl Mongers 技術・学術・飲み会ｗのバランス
2008年 - フレームワーク勉強会 Perlばっかりでした - Kansai.pm #9 - OSC 2008 - Kansai.pm #10 - KOF 2008
2009年(予定) - JPAセミナやりたい - ミーティング、あと1回は - OSC, KOF出展 - 募集中 - どんなイベントがしたい？
アンケート 普段の言語 内容はよくわかった？
混乱している人は: WindowsでPerlするならStrawberry Perlおすすめ
WindowsでPerl - Active Perl - cygwin - VMWareでLinux - XAMPP + Perlアドオン - Strawberry Perl [new!] - WindowsだけどPerlつかってない - Active Perlつかってる - Perlつかってみたい
おすすめポイント - gccやmakeが入ってる - CPAN Shellが普通に動く - Active Perlだと専用ツール経由になる - 最初からモジュールがいくつか追加されてる(Bundle::CPAN, Bundle::LWPとか) - 5.10と5.8.8が選べる - リリースは年4回くらい(比較的緩やか) - 通常版のインストールはc:\strawberry固定 - 空白問題とかを回避 - 上級者には指定ディレクトリに入れるためのパッケージも。 - ポータブル版(beta) - USBメモリとかでPerl環境を持ち歩く
XSのはなし改めSocial SKK : antipopさん
Perler, Emacser, アイドル はてなエンジニア(はてなボトル、Myはてなとか)
前回の発表以降： Vimmer転向を宣言したが、断念 Lux::IO Term::ANSIColor::Markup フォントタグみたいな形式で色指定
軽い話 ソーシャルが流行り Social IMEが話題 - MS IMEの「単語登録」みたいなのをWeb経由で自動的に共有 - Web APIがあるので、クライアントを自由に作れる
が、SKK使いだし... AquaSKK これをSocical化したら？ -> id:shunirrさんがRubyでやってた(SocicalIME特化) せっかくなのでPerlでもやってみた
SKKとは IMEの一種 連文節変換ではなく、送りがな単位で変換(「oku R igana」とか) 文節の区切り間違いがない(当たり前ｗ) いろいろな辞書ファイル
skkserv 変換候補の返却サーバ、たくさん実装がある プロトコルさえ守れば、何を返してもいい→Social IMEで検索
App::SocialSKK socialskk.plをSKKサーバとして使うと、変換時にSocialIMEを使うようになる プラグイン方式なので、Wikipediaとか英辞郎にも対応 はてブにも対応(おまけ) - 「ほってんとり」で変換→最新のエントリを次々に表示
実装 POE::Component::Server::TCP
shipit!!(この場で公開)
2009-03-23
■ [biwascheme] 正規表現のバックスラッシュ
最近、BiwaSchemeで簡単なアプリを書こうとしている。やはり使ってみるといろいろ不便な点が見えてくるものだ。
例えば正規表現で文字列から数値部分を抜き出すとき、
(regexp-exec (string->regexp "(\\\\d+)") str)
と、バックスラッシュを4つ書かなくてはならない(elispか)。
が、(load "util.scm")のようにしてこのコードを外に出すと、バックスラッシュが2つでいい(でなければならない)ことに気づいた。 scriptタグの中でなくなるからだな。
さらに、regexp-execの第一引数が文字列だった場合はRegExpに変換するようにしたので、
(regexp-exec "(\\d+)" str)
と書けるようになった。
正規表現リテラルを導入すれば
(regexp-exec #/(\d+)/ str)
までシンプルにできそうだけど、これは後回しで。
2009-03-24
■ [scheme][memo] R6RS処理系
インストール状況：
- (petite) chez scheme
- 済
- Ypsilon Scheme System
- 済
- Ikarus Scheme
- 済
- Mosh
- 済
- PLT Scheme
- まだ http://download.plt-scheme.org/
- Larceny
- 途中
- IronScheme
- まだ。mono使えばMacでも動かせるようだ。
■ [link] 認証と認可
twitterのパスワードを要求するマッシュアップはいっぱいありますが、OAuthに対応してくれればパスワードを個々のサービスに渡さなくても済むようになりますね
[秋元@男子産前休暇ブログ » twitterのOAuthが一般利用可能により引用]
OAuthってなんだろう。
OpenIDになんとなく似てるけど、OpenIDがログイン情報を扱うのに対し、OAuthはアクセス制御を行うらしい。
OAuthを解説したページに、こんな文章が。
分かりやすく「認証」と「アクセス制御」って書いたけど、一般的には「認証 (Authentication)」と「認可 (Authorization)」と呼ぶみたい。
[WebAPI のアクセス制御に使える OAuth という仕様 - まちゅダイアリー(2007-09-25)より引用]
ほうほう。
認証（Authentication）
そのユーザーが自分の物であると主張するIDに対して、そのIDが確かにそのユーザーの物であるということを保証すること
認可（Authorize）
認証されたIDを受け入れ、サービスに対して適切な権限を与えること
[仕様から学ぶOpenIDのキホン − ＠ITより引用]
■ [prog] 並行・並列・分散
ついでに、並行・並列・分散の違いも思い出す。
- 分散処理(distributed processing)
- 複数のマシンで実行。
- 並列処理(parallel processing)
- マシンは一台だが、複数のCPUコアで実行。
- 並行処理(concurrent processing)
- 複数のタスクを並行して実行。マシンの台数やCPUコアの数は関係ない。
ということは迷ったら「並行処理」って言っとけばいいわけだね(おい)。
(3/28追記：字が間違ってた(´・ω・｀) 平行→並行)
■ [ruby][prog] Fiber(とコルーチンとcall/cc)についていろいろ考えた
Kansai.pmのはこべさんの発表とか、その後の話からいろいろ考えた。
FiberとWebアプリ
- Fiberを使って、ステートフルなWebフレームワークが作れるはず。
- リクエストが来るたびに、少しずつFiber内の処理を進めていく。いわゆる「継続ベース」のWebフレームワークのように。
- ただし同じポイントから再度繰り返すことはできない(call/ccベースではないので)。まぁ繰り返したいことってそんなにないと思う…アンドゥの実装には便利かもしれない？
- Fiberの利用例だとNeverBlockが有名だけど
- NeverBlockって何だっけ？
- MySQLのクエリをブロックしないようにするらしい
- findとか読んだときに結果が返るまでじっと待つんじゃなくて、Fiber.yieldで中断して、待ち時間に別のことをする
- 別のことって…？
- うーん、もうちょっと調査が必要そうだ(^^; → steps to phantasien(2008-09-20)
- 1つのページをレンダリングするときも、並列できる箇所はあるよね
- たとえばはてブトップなら、ヘッダ部分と「人気エントリー」と広告の部分で必要なデータは独立だが、上から順にレンダリングするとSQLの呼び出しごとにブロックしてしまう
- これFiberでなんとかならない？
- 各ブロックを独立したFiberにする。フレームワーク側がそれらを管理していて、SQLの呼び出しが発生するとFiberを中断させ、SQLの結果が取得できるまで別のFiberの計算を実行しておく。
- 理想をいえば、Fiberに切り分ける部分も自動でやってほしい(テラ未来ｗｗｗ)
- 変数の使用範囲とかを解析したらいけるんじゃないかなぁ
- evalってこういうのとすげー相性悪いよね
- というか動的さはコードの解析を難しくする
- ということはいずれコードが解析しやすい言語が有利になる？コードを解析することで、性能を上げる。メタプログラミング。
- と言ってみたものの変数の生存解析とかはぜんぜん詳しくないのでよく分からん
Fiberの使い道
- ゲームしかないのか？
- そもそも複数の処理を平行して走らせたい場面って限定されるよねぇ…。
- C#のジェネレータはプログレスバーとか出すのに便利らしい。
- ということは、「ディレクトリを再帰的に辿りながら総サイズを計算するような関数」をFiberで中断してプログレスバーを更新するようなデモを書くと格好いいと思われ。
- Coro自体は単なるコルーチンよりも(強力|用途が広い)ようだ。
ジェネレータとかcall/ccとか
先にまとめておくと、
- Fiber相当(コルーチン)：
- Ruby 1.9のFiber
- C#/Python/JS1.7のジェネレータ(あのyield使うやつ。Rubyのyieldとは意味が異なる)
- Luaのcoroutine
- はこべさんのCoro::Fiber
- call/cc相当(再入ができる)：
- Schemeのcall/cc
- Rubyのcallcc (1.9からはrequire 'continuation'が必要)
- RhinoのContinuationクラス
- PerlのCoro::State(のclone関数)
- Cyanのreturn
- Fiberとcall/ccの違いは、停止したFiberは「一度しか」再開しかできないのに対し、call/ccはある地点から「二度以上」実行されることがある点。
- だからcall/ccはある時点の処理系の状態を「コピー」しなければならない(2回目に実行されるときのために)。なので普通はコルーチンよりも重い。
- というか「call/cc」という表現は適当じゃないかも。
- call/ccは、(A) 継続をオブジェクトとして取り出せる機能 と (B) 継続オブジェクトを指定した関数に渡す機能 に分解できる。重要なのは(A)の方であって、(B)の方は単にAPIのインターフェイスの問題に過ぎない。
- RhinoのContinuationクラスはSchemeのcall/ccとインターフェイス((B)の部分)が異なるけれど、(A)の部分の機能は同じ。だからやれることは変わらない(はず)。
- call/ccは、(理論面はともかく) 「処理系の状態をまるごと保存するんでしょ？」と思うとあんまりマジカルでなくなる。
- それでもよくわからん！っていう人は： Greenbear Diary - Ruby勉強会＠関西-16「30分でわかるcallccの使い方」
- これいつか文章に起こしたいと思ってるんだけど、機会がないままだなぁ
2009-03-26
■ [event] ICFP2011は日本でやるらしい
関数型言語の学会、ICFPが日本に来るらしい。
おお、それは見に行かねば…。(って再来年だが)
ついでに、凝った問題で知られるICFP Programming Contestは今年はちょっと日程が早いそうな。
(公式サイトシンプルすぎるｗ) (追記：元に戻ってる？)
今年はどんな問題になるんだろう。
2009-03-27
■ [biwascheme][javascript] イベントハンドラ内で自分を削除するようなコードが動かない
説明が難しいのだけど、こういうボタンがあって、
押したらこうなる↓
というコードを書きたいのですよ。BiwaSchemeで書いてるんだけど、JSでいうと「$("the_div").update()」みたいな処理が動きます。
だけど、実際には
のように、divではなく内側のinputの中身だけが変更されてしまう。
どういう時にこうなるんでしょう？？
■ [biwascheme] パッチいろいろ
yamatoさんからBiwaSchemeのパッチをいろいろもらいました。
- named let対応
- find_free,find_setsのバグ修正
- SRFI-30の複数行コメント (#| ... |#) 対応
- SRFI-62のS式単位コメント #;(a b c) 対応
リポジトリの最新版で取り込まれています。
mohekekeさんの可変長引数パッチと合わせて、いろいろ便利になってきました。有り難いことです。
2009-03-28
■ [misc] ケータイの絵文字がどのように変換されるかを巨大な図にまとめてみた
ケータイの絵文字は他社の端末に送信する際に、「似ている絵文字」に変換されるため、例えば au端末で「熱がある」という表情の絵文字を含んだメールを作り、それをSoftBank→Docomoと順に転送していくと、 「熱がある」だったはずの絵文字が巡り巡って「ほっとした顔」になってしまうらしい。
上記の例は「適当に拾った例」とのことだけれど、せっかくなら全部まとめて見てみたいと思わないだろうか？
よろしい、ならばGraphvizだ。
注意点としては：
- 枠の色は、赤がDocomo、グレーがSoftBank、オレンジがau、緑がE-MOBILE、青がWILLCOM。
- 画像もこちらのページのものをそのままお借りした。ありがとうございます。
- pngなのでアニメーションgifは動かない。
- Graphvizで日本語(というかUTF-8の一部の文字)が通らなかったので、「[ペン]」など文字列に落ちるものは数値に変換してある。
Graphvizは「AからB, BからC」みたいな辺の情報を書いたファイル(*.dot)を読み込み、そのグラフ構造を描いた画像を出力するソフトウェアだ。 dotファイルはただのテキストなので、今回はこちらのページの変換表をRubyでスクレイピングし、 dotファイルを作った。
ふつう、Graphvizでこういうノードが切れ切れになっているものを変換しようとすると、小さなグラフの全てを横に並べようとして ものすごい横長になり、「width too big」というエラーで落ちてしまう。 だが調べたところ、-Kでレイアウトエンジンを切り替えられるらしい。 今回は「neato」というエンジンを使ってみると上図のようにうまく行った。
一応、ソース。
extract.rbでhtmlをdata/*.csvに→render.rbでdotファイル出力→ dot -Kneato -Tpng x.dot -o x.png という感じ。
(4/16追記：たんぶられてるのを見て、縮小したものを載せてみた。その発想がなかった自分に反省。 こうして見ると色といい形といい、なんとなく遊園地っぽい。)
2009-03-31
■ [scheme] MITがSchemeをやめてPythonを採用した理由
という記事をPlanet Scheme経由で見た。
が、読んでみるとタイトルに偽りありで、「なぜMITはSICPを止めたか」(Schemeをではなく)という話だった。
詳細はlequeさんによる日本語訳を読んでもらいたいのだけど(もちろん原文でもいい)、 簡単に言うと、「研究の補助手段としてプログラミングする際のやり方が、80年代と現在ですっかり変わってしまったから」ということのようだ。
もともとSICPは情報系ではない学生のためのプログラミング入門講義(6.001)で使われていたテキストで、 自分が把握できる小さなパーツをいくつも組み合わせて目的のものを作り出すやり方を説明するのが目的だった。 だけど現在では既存のライブラリを動かして試しながら目的のものに近づけていくのが主だから、SICPのような内容よりも ロボットを制御するプログラムを書くほうが合っている…のだとか。
んで、Pythonが採用されたのは、たまたまそのロボットを制御するためのライブラリがあったから、らしい。
□ naoya_t [Lispjobs.jp担当のnaoya_tです。jokeカテゴリがありませんでした。すみません。いますぐ作ります。]
□ ujihisa [naoya_t++]
□ yhara [naoya_t++]