« 2006年04月 | メイン | 2006年06月 »
帰りの電車の中での思いつき。 反発力の計算は二乗のオーダーだけど、空間分割を入れると軽くなるよね。 空間分割を入れるのもいいけど、xの値でソートしておいてその順で一定範囲いないかどうかのチェックを行えば、xの差が限界半径を超えたらもうその先には半径以内の点は存在しないのでbreakできる。頂点数が少ないとき＆密度が高いときにはメリットが薄いけど、そもそも反発力の計算が二乗のオーダーであるせいで重たくなるのは頂点数が多いとき。頂点数が少ないときにはソートもさほど時間がかからないし、入れてみる価値はあるかも知れない。また、この「順序」は基本的に直前の結果とあまり変わらないので、「ほぼソートされているデータのソート」になりますね。挿入ソートがいいのかな。
せっかくだからパフォーマンスの比較をきちんとやってみよう。1万頂点くらいで。
MinGWを入れて、EclipseのCDTで開発できるようにして、とりあえず20番目までのフィボナッチ数列を表示させたところで15時半。Dancing Linksを実装するどころじゃないですね。まぁ、初日はこんなものかなぁ。
あと、さすがにGoogleだけを教科書にしてC++を勉強したりすると、変な癖がついてしまうかも知れないですね。いい教科書を探さなきゃ…。
せっかくCを使うのでstructでも使おうかと思ったけど、やっぱりクラスにしとこう。でもクラスの構文ってどんなのだったかなぁ…。
帰宅。 クラスを使ってみたらエラーだらけになって何が悪いのかと思ったら、C++ではメソッドの前にpublicって書くんじゃなくてpublic:ってのが上の方に入るんだった(ぉぃぉぃ)
赤坂のラボにC++の本はあんまりなかったのでやっぱり教科書を探すのが重要。
Amazon.co.jp： C++の設計と進化: 本: ビョーン ストラウストラップ,Bjarne Stroustrup,岩谷 宏,エピステーメ
「ビョーン」？！
ビャーネ・ストロヴストルップ - Wikipedia。ふむふむ。
アマゾンアソシエイトのリンク作成機能を試してみる。
(やっぱりウザイので消しました)。空間がだいぶ無駄になりますね…。っていうか著者じゃなくて訳者の一番最後の人が表示されるのはよくないのでは…。
あと独習C++とかはどうなのかなぁ。こういう本が置いてあるような本屋に行ってどれがいいか眺めてくるのもいいなぁ。
とりあえず積ん読本の中からC++の話題が書いてありそうな本をチョイス。 オブジェクト指向言語のはなし あなたはなにを選ぶのか―Java、Eiffel、C++? プログラミング作法アスキー アジソンウェスレイシリーズ 珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造 とりあえずこの3冊で勉強しようかな。
あとこれ。STL samplesも参考になりそう。
ねむ。
寝る前に帰りの電車で思いついたのを実装して見たら期待通りにうまく行って、実際に使ってみると(少なくとも自分には)他の同様のものより圧倒的に使いやすかったです。Pythonで箇条書きをHTMLに変換。後はこれをPerlで実装してMovableTypeのプラグインにしたらかなり楽ちん。
べた文章が書けて、箇条書きが直感的に書けたら、あとはグラフィックとマインドマップですな。それがそろえば僕の頭の中のものを吐き出すツールとして申し分ない。
さぁ、明日はGRINEditだ。曜日ごとに作業を分けるってのは想像以上にいい効果をもたらしています。明日はGRINEditの日だから箇条書きプログラムは今日のうちにやってしまおうと思えるし、やる気のでないこともずるずる先延ばしにならずに進んでいくので。やはり僕のようなタスク管理が苦手な人間には、主観を挟まずに何から実行するかを決めてくれるタスクスケジューラがあると便利ですね。緊急度で順位付けするなんてのは、緊急でないプロジェクトが複数できた時点で「あー、どっちからやろうー」となるわけで。あと、その日のうちにやらないと一週間後に繰り延べになると思うと終末効果が強く起きて生産性もアップ。ビバ締め切りドリブン開発。問題点は睡眠時間を削ってしまうことか… それは帰ってきた後作業するときには電源ケーブルを繋がない、という原始的な方法で一応解決したつもり。あと6%！
今週の木・金曜はこれかな。
> (digitize (mul two three)) 6 > two ((())) > three (((()))) > (mul two three) ((((((()))))))
数字化して見やすくするdigitize関数で1と0を使っている以外は一切数字を使いません。ソースコードは以下のような感じ。まぁ、正の整数しか扱えないので今度暇なときには有理数くらいに拡張してみることにします。
(define zero ())
(define (inc x)
(cons x ()))
(define (dec x)
(car x))
(define one (inc zero))
(define two (inc one))
(define three (inc two))
(define (add x y)
(if (null? y)
x
(add (inc x) (dec y))))
(define (sub x y)
(if (null? y)
x
(sub (dec x) (dec y))))
(define (mul x y)
(if (null? y)
zero
(add x (mul x (dec y)))))
(define (digitize x)
(define (foo x d)
(if (null? x)
d
(foo (dec x) (+ d 1))))
(foo x 0))
とりあえずHidden Markov model - Wikipedia, the free encyclopediaに載っていたPythonコードをきちんと動くようにしてみました。
def choise(dic):
"choise key from dictionary using value(probability)"
from random import random
rest_prob = 1.0
for k in dic:
p = dic[k]
if random() * rest_prob < p:
return k
rest_prob -= p
class StateMachine:
states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
}
emission_probability = {
'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
def __init__(self):
sp = self.start_probability
self.currentState = choise(sp)
def emit(self):
ep = self.emission_probability
s = self.currentState
return choise(ep[s])
def transit(self):
tp = self.transition_probability
s = self.currentState
self.currentState = choise(tp[s])
でもRainyとかが何度も出てくるし、「states = ('Rainy', 'Sunny')」や「observations = ('walk', 'shop', 'clean')」が全く無意味で面白くないですね。
def generate_dict(keys, values):
d = {}
for (i, k) in enumerate(keys):
d[k] = values[i]
return d
start_probability = generate_dict(states, (0.6, 0.4))
transition_probability = generate_dict(
states, [generate_dict(states, x) for x in
((0.7, 0.3),
(0.4, 0.6))])
emission_probability = generate_dict(
states, [generate_dict(observations, x) for x in
((0.1, 0.4, 0.5),
(0.6, 0.3, 0.1))])
うわー。
def build_prob_table(keysList, valueTable):
if len(keysList) == 1:
d = {}
for (i, k) in enumerate(keysList[0]):
d[k] = valueTable[i]
return d
result = build_prob_table(
[keysList[0]],
[build_prob_table(keysList[1:], x) for x in valueTable])
return result
start_probability = build_prob_table([states], (0.6, 0.4))
transition_probability = build_prob_table(
[states, states],
((0.7, 0.3),
(0.4, 0.6)))
emission_probability = build_prob_table(
[states, observations],
((0.1, 0.4, 0.5),
(0.6, 0.3, 0.1)))
これで2次元に限らず何次元でも行けますよ！(でも仕様上2次元までしかないのだけど。過度の抽象化。)
とりあえずViterbiアルゴリズムを実装してみました。'walk', 'walk', 'shop', 'walk', 'walk', 'clean', 'clean', 'clean', 'clean', 'clean'を入力すると'Sunny', 'Sunny', 'Sunny', 'Sunny', 'Sunny', 'Rainy', 'Rainy', 'Rainy', 'Rainy', 'Rainy'が帰ってきます。つまり、shop単体ではその日がRainyであった尤度が高いのだけども、前後をSunnyである尤度の高いwalkで挟まれているので全体としては「shopの日もSunnyであろう」という推定がもっとも尤度が高くなるわけですね。一方、walkとcleanの間にshopを挟んで 'walk', 'walk', 'shop', 'walk', 'shop', 'clean', 'clean', 'clean', 'clean', 'clean'にした場合は、'Sunny', 'Sunny', 'Sunny', 'Sunny', 'Rainy', 'Rainy', 'Rainy', 'Rainy', 'Rainy', 'Rainy'となり、shopの日はRainyだと判定されるわけですね。
いわゆる「いかさまサイコロ推定問題」も実装してみました。といっても確率分布をいじるだけ。
class Casino(StateMachine):
states = "FL"
observations = "123456"
start_probability = build_prob_table([states], (0.5, 0.5))
transition_probability = build_prob_table(
[states, states],
((0.9, 0.1),
(0.2, 0.8)))
emission_probability = build_prob_table(
[states, observations],
((0.16, 0.16, 0.17, 0.17, 0.17, 0.17),
(0.1, 0.1 , 0.1, 0.1, 0.1, 0.5)))
c = Casino()
rolls = ""
hidden = ""
for i in range(60):
hidden += c.transit()
rolls += c.emit()
print hidden
print rolls
print "".join(c.viterbi(rolls)[0])
LLFFFFFFFFLLLLFFFFFFFFLFFFFFFFFFFFFFFFFFFLLLLLLLLLLLLLLLLLLL
661225134463466546136164411511233413411161362663654346666623
LLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFLLLLLLLLLLLLLLLLL
短い範囲のいかさまはかなり取りこぼしますね。でもたぶんこれで正しい挙動のはず。
def choise(dic):
"choise key from dictionary using value(probability)"
from random import random
rest_prob = 1.0
for k in dic:
p = dic[k]
if random() * rest_prob < p:
return k
rest_prob -= p
print "err"
return k
def build_prob_table(keysList, valueTable):
if len(keysList) == 1:
d = {}
for (i, k) in enumerate(keysList[0]):
d[k] = valueTable[i]
return d
result = build_prob_table(
[keysList[0]],
[build_prob_table(keysList[1:], x) for x in valueTable])
return result
def findMax(iterable):
maxV = -1.7976931348623158e308 # minimum value
for (k, v) in iterable:
if v > maxV:
maxV = v
maxK = k
return (maxK, maxV)
class StateMachine:
def __init__(self):
sp = self.start_probability
self.currentState = choise(sp)
def emit(self):
ep = self.emission_probability
s = self.currentState
return choise(ep[s])
def transit(self):
tp = self.transition_probability
s = self.currentState
s = choise(tp[s])
self.currentState = s
return s
def viterbi(self, inputData):
from math import log, exp
states = self.states
ep = self.emission_probability
sp = self.start_probability
tp = self.transition_probability
# initialisation
prob_at_state = {}
for k in states:
prob_at_state[k] = log(sp[k])
pointerList = []
# recursion
for c in inputData:
new_prob_at_state = {}
pointers = {}
for l in states:
(maxK, maxP) = findMax(
((k, prob_at_state[k] + log(tp[k][l])) for k in states))
new_prob_at_state[l] = log(ep[l][c]) + maxP
pointers[l] = maxK
pointerList.append(pointers)
prob_at_state = new_prob_at_state
# termination
(lastState, totalProb) = findMax((k, prob_at_state[k]) for k in states)
# traceback
L = len(inputData)
path = [None] * L
path[L - 1] = lastState
i = L - 1
while i > 0:
path[i - 1] = pointerList[i][path[i]]
i -= 1
return path, exp(totalProb)
class RainySunny(StateMachine):
states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = build_prob_table([states], (0.6, 0.4))
transition_probability = build_prob_table(
[states, states],
((0.7, 0.3),
(0.4, 0.6)))
emission_probability = build_prob_table(
[states, observations],
((0.1, 0.4, 0.5),
(0.6, 0.3, 0.1)))
class Casino(StateMachine):
states = "FL"
observations = "123456"
start_probability = build_prob_table([states], (0.5, 0.5))
transition_probability = build_prob_table(
[states, states],
((0.9, 0.1),
(0.2, 0.8)))
emission_probability = build_prob_table(
[states, observations],
((0.16, 0.16, 0.17, 0.17, 0.17, 0.17),
(0.1, 0.1 , 0.1, 0.1, 0.1, 0.5)))
c = Casino()
rolls = ""
hidden = ""
for i in range(60):
hidden += c.transit()
rolls += c.emit()
print hidden
print rolls
print "".join(c.viterbi(rolls)[0])
しまった、論文読んでたはずなのになぜ人のブログの記事に反応しているんだ！西尾泰和のブログ: Re: ループ内の無名関数
ForwardアルゴリズムとBackwardアルゴリズムを実装してから帰ろうかと思ったけど、慣れない場所で一人になると集中できないことがわかったのでもう帰ります。
それと水曜日はSchemeの日のつもりでしたが、Schemeは夕方から夜にかけてだけにして、昼間はC++の日にしようかなぁとか思ったりしました。手を広げすぎ？
普通の人と違って5月から仕事を始めたのできっと今4月病。そして6月に入ってから5月病になるんだ、きっと。
今日は柏の方に行っていました。ここからお台場の東京テレポートまでは電車で23分、徒歩15分。一方、柏までは電車で24分、バス25分。ただし柏からの帰りは座れます。東京テレポートからの帰りは絶対座れません。新聞すら読めません。うーん。柏の方が楽だなぁ。柏から帰ってくる電車の中で新聞を読み終わって暇だったのでSchemeで遊んだりしてました。数のない世界。divを実装しようとしたところで駅に着いたので中途半端ですがね。お台場への往復のプログラミングができない時間を有効に活用する方法を考えないと行けませんね。やっぱPodCastingで英語耳を鍛えるとかですかねぇ。
そういえば一時期買おうかと考えていたヘッドマウントディスプレイですが、長時間座って移動することがなくなったので使いどころがなくなりました。
index.htmlで区切りの横線が出ていなかったので出すようにしました。MovableTypeでグローバルフィルタを使って独自タグを作ると、明示的にONにしないと使われないので気をつけないと行けませんね。「MTEntryBodyが使われているところ全部でONにする」なんてのができればいいんですけど、そうじゃないとDon't Repeat Yourselfの精神に反しますね。ちなみにZopeでは部品であるstandard_html_headerを再利用して別のstandard_html_headerを作ってオーバーライドすることができます。MovableTypeもMTEntryBodyを再定義できればいいのに。
ATOKでTABを押すと補完ができるんですね！今知りました。
歩いているとマシン いろいろありがとうございます。 うーん 延長ケーブル オブジェクトが持っている 柏の葉 キャンパス 区切りの横線 ケーブル 交換 再定義 春眠暁を覚えず スコープ 静的アーカイブ化 相当 タイヤとの交換 チェックディジット 使いどころ ティ 東京テレポート ないのだけど 2006/05/30 盗人を捕らえてみれば我が子なり ね。 の横線 葉 表現 船橋市海神町南 平成18年5月30日(火) 補完 マシン 耳 無意味で面白くないですね 明示的 MovableType やっぱPodCastingで英語耳 有効 よろしくお願いします。 わかったので を押すと ん Backwardアルゴリズム CG-SW08TXL Don't Repeat Yourselfの精神 ForwardアルゴリズムとBackwardアルゴリズム GRINEdit開発日誌 HD-PHS80U2/UC JavaScriptで正規表現 Knuth- LD-GV/BK15 MovableType PodCastingで英語耳 Q.P. Rainy Scheme TPOに相当 Viterbiアルゴリズム wag ｘｖKL-E20 yak Zopeでは部品
面白い。 っていうか「盗人を捕らえてみれば我が子なり」は打った記憶がないので辞書から持ってきたんでしょうね。「もう」で「申し訳ありません。」、「ごめ３」で「ご迷惑をおかけします。」が出ますね。敬語は基本的に長くなればなるほど敬意を示しているのですが、まさか補完で長いメッセージを入れる時代がくるとは(笑)
最近気づいたのだけど、PythonはRubyよりJavaScriptに似てますね。少なくとも僕にとってはRubyよりJavaScriptの方が理解しやすいです。そしてRubyを覚えて新たに獲得する能力はいまいち思いつかないけど、JavaScriptを覚えたらBookmarkletとかFirefox拡張とかいろいろできるようになりそう。ああ、またRubyを勉強する日が遠ざかっていく…。「プログラミングRuby」はだいぶ前に買ったんですけどねぇ。
明日はC++の日。Knuth's Algorithm XをC++で実装できるかな～？まず開発環境から整えないと行けないんだけども。
メモ：_hdlr_category_desc、ul
ウノウラボ Unoh Labs: ループ内の無名関数を読んで、やっぱりPythonとJavaScriptは似ているなぁ、と思ってしまいました。Pythonに慣れた僕にとっては上記エントリのJavaScriptの挙動は自然だと思えてしまいます。
同じ現象は以下のようなPythonコードでも起こせます。
funcList = []
for i in range(2):
funcList.append(lambda :i)
i = 5
print funcList[0]() # 「5」と表示される
print funcList[1]() # 「5」と表示される
少なくともPythonの場合、この現象はループや無名関数とは無関係です。下のようなコードでも同じ現象が起きます。
i = 1
def foo():
return i
i = 5
print foo() # 「5」と表示される
これはどういうことかというと、関数fooの中で使われているiという変数は「グローバルスコープのiという変数」を意味するのであって、「関数fooが定義された時にグローバルスコープのiが指していた値」を意味するわけではない、ということです。古いPythonではこの問題を解決するために以下のようにBuilder関数を作ったりしていました。
i = 1
def foo_builder(x):
def temp_func():
return x
return temp_func
foo = foo_builder(i)
i = 5
print foo() # 「1」と表示される
ちなみにtemp_fileの代わりにfoo、xの代わりにiを使っても問題ないのですが、読み慣れていない人が混乱するかと思って別の名前をつけてみました。このコードでは、fooのxがfoo_builderのローカルスコープにある変数xを意味するので、グローバルスコープの変数iが指す値が変わっても影響を受けないわけです。これを無名関数でやったのがリンク先のmasatoさんの一つめのコメントであり、Pythonで同じことを書くとこうなります。
i = 1 foo = (lambda x: lambda :x)(i) i = 5 print foo() # 「1」と表示される
で、ここからが本題なのですが最新のPythonでは「引数省略時のデフォルトの値」が関数定義時に評価されることを利用して以下のような書き方ができます。JavaScriptに引数省略機能はないのですか？
i = 1
def foo(x = i):
return x
i = 5
print foo() # 「1」と表示される
GRINEditのインタラクティブ性をライブラリとして再利用できるようにするためには、物理演算による整形だけではなく、マウス制御部分もライブラリとして簡単に再利用できるようにする必要がある。 しかしマウス制御はSWTと密結合だし、現状ではJython.jarも使っている。 切り離せるだろうか？
とりあえずMouseMediatorやMouseOperationがPyObjectを継承していが、これは必要ない。 Mediatorへの参照をコンストラクタが受け取っているのも Mediatorがシングルトンになっていなかった昔の名残だから除去できる。 PyListを返しているMouseMediator#getNames()はMediator#getMouseOperationNames()に移動しても構わないだろう。
とりあえずマウス制御部分のJythonへの依存性は取り除いたが、ViewportTransformerだとかにもアクセスしているから切り出すのは難しそうだなぁ…。うーん。
うーん、ViewportTransformerごと切り出すってのも考えたけども、anchorTableとかとも結合しているから切り出すのはやっぱり難しそうだなぁ。うーん。
やはりNarVisualizerをもう一度作るか…。NarVisualizeがさくっと作れるライブラリというのが一つの目標としていいかもしれない。アレは独自の形のVertexがあり、名前頂点だけ左端に張り付いたり、と制約も入っているし。
Java での XML-RPC の使い方の内容は参考になりますが、多少古い&足りないので補完記事を書いてみます。
上記の記事で使われているライブラリ「helma.xmlrpc.*」はApache XML-RPCに移動しました。「import helma.xmlrpc.*;」の代わりに「import org.apache.xmlrpc.*;」を使う必要があります。
新しいライブラリはApache Download Mirrors - The Apache Software Foundationから近いミラー(日本人ならhttp://www.meisei-u.ac.jpかな？)を選んでダウンロードします。このときに、間違えてバージョン3をダウンロードするとあるはずのメソッドがなくて悩みます。xmlrpc-current-bin.tar.gzではなく、binaryディレクトリのxmlrpc-2.0.zipをダウンロードするとよいと思います。
また、Codec - Commons Codecも必要です。The Jakarta Site - Commons Codec Downloadsから最新のバイナリをダウンロードします。
上記二つのライブラリを解凍し、適当な場所において、Eclipseのビルドパスの設定で「外部JARの追加」をします。(もしEclipseを使っているのなら)
そうすると後はJava での XML-RPC の使い方を参考にWebServerインスタンスを作り、それに適当なクラスのインスタンスをハンドラとして渡してやれば、XML-RPCでそのクラスのpublicメソッドを呼べるようになります。ただし、WebServerインスタンスのstartメソッドを呼んでサーバを開始するのを忘れないように。
WinXPユーザーなら、自作のXML-RPCサーバが最初に起動したときにWindowsファイヤーウォール(か自分で入れたファイヤーウォール)が警告画面を出すかと思います。
また、ソフトウェアの終了時にサーバのshutdownメソッドを呼ばないと、ウィンドウは消えたままサーバだけ動き続けることもあります。次回起動時に「使おうとしたポートが開いていない」とエラーになってしまうので気をつけてshutdownしましょう。
import xmlrpclib
s = xmlrpclib.Server("http://localhost:8080/RPC2")
print s.grinedit.getSelectedVertex()
Fault: <Fault 0: 'org.apache.xmlrpc.XmlRpcException:
Unsupported Java type: class java.util.ArrayList'>
XML-RPCで受け渡しできる型は限られているので当たり前。だけど、どのみちVertexを追加するときにいろいろなサブクラスのインスタンスを渡したくなるわけだから、ここでXML-RPCで受け取れるような型を返すようにMediatorを修正するのは無意味。XML-RPC用にもう1枚レイヤーを作るのが妥当なソリューションでしょうか。XML-RPCのハンドラをJythonで実装することにします。
現状、init.pyの中でJava(apache)のXML-RPCサーバを起動。
# run XML-RPC server
from org.apache.xmlrpc import WebServer
server = WebServer(8080)
server.addHandler("grinedit", med)
server.start()
Mediatorクラスがテスト用に整数を取って1足して返す関数incを持つ。
public class Mediator {
:
public int inc(int x){
return x + 1;
}
}
別プロセスのPython(Jythonではない)から以下のコードを実行。
import xmlrpclib
s = xmlrpclib.Server("http://localhost:8080/RPC2")
print s.grinedit.inc(5)
これで「6」とプリントされます。別プロセスのソフトウェアからXMLでクエリを投げて、GRINEditがそれを受け取って処理をし、結果をまた呼び出し元のソフトウェアに投げ返す、という基本的なところは動きました。
うーん、頭が痛い。今日はさっさと帰って体を休めようかな。ちょっと寒気もするし。
西尾泰和のブログ: XML-RPCとりあえず動くだけ見ると、非常に楽ちんにできたように見えますが、まちがえてalpha版のXML-RPC 3.0をダウンロードしてしまったのであるはずのメソッドが見つからず難儀しました(苦笑)
JavaでXML-RPCするときには…あ、これは日記に書くんじゃなくて別個のエントリにすべきか。
Understanding The Architecture Of SQLite。なるほど、行を挿入すると自動的にROWIDという名前の値が振られ、その値を元にB木が構築されるわけですね。Any column declared INTEGER PRIMARY KEY is an alias for the ROWIDだそうで、このINTEGER PRIMARY KEYを指定して特定された行を取ってくる処理に関してはlog(N)のオーダーになる、と。その他の列を指定して取ってくる処理もあらかじめその列のインデックスを作っておけばlog(N)になるわけですね。ランダムアクセスは速いのですが、逆に「特定のテーブルを丸ごと取ってきてすべてのデータについて解析」なんて目的にはあまり意味がないですね。むーん。
D論太りで12キロ太って66キロになり、腹回りは5月2日時点で83センチになっていたのだけども、ここ1ヶ月のダイエットでとりあえず81センチに減ったみたいです。
例のZIPファイルをダウンロードして処理する話。全部ダウンロードするとサイズが大きいから「ZIPファイルをダウンロードして解凍して必要な情報だけ取り出してZIPファイルを捨てる」というスクリプトを作ろうと思っていたのですが、よくよく考えたら1メガちょいのファイルが2000個あるって言ってもたかだか2GBですね。余計なことを考えてないでさっさとダウンロードしてしまった方がいいかもと思っていまそのスクリプトを走らせています。重複の多いデータだからRDBMSに入れると無駄が多いかなぁ、とか、このデータ構造ならこういうバイナリフォーマットで保存すれば小さくなるなぁ、とかいろいろ考えていたのだけども…。全部あわせてたかだか2GBのデータファイルを圧縮するために工数をかけるより、そのデータの解析の方を優先すべきかも知れないですねぇ。
そうだ、今日はKnuth先生の論文を読んで実装するつもりだったんだ。特定データ構造に特化した使い回しの聞かない圧縮方法なんか考えている場合じゃなかった。
とりあえずダウンロードスクリプトが動いている間に魚を買いに行ってきます。昨晩料理の教科書を見ながら考えた結果、焼き鮭を作ることにしました。
小麦粉も油もネギも、最低売買単位がこんなに大きくちゃ一人暮らしでは使い切れないなぁ。
うーん。メインディッシュは焼き鮭として、焼き鮭だけでは晩ご飯にならないな。スパゲッティでもゆでるかな。この前作った激辛ペペロンチーノでも。でも鮭を焼いてからスパゲッティをゆでると鮭が冷めてしまう。先にスパゲッティか。
照明が暗いので写りが悪くて何かよくわかりませんね。黄色ピーマンがイカみたいに見えます。
初めての焼き鮭の出来具合は…ちょっと小麦粉が多すぎたかも知れないですね。油を吸って取れた粉を脇にどけて粉の落ちていないところで焼きました。
もう28時…。
Python on win32のurllibでダウンロードしたZIPファイルが壊れていて、調べてみたら改行コードが変わってしまっていた件の原因がわかりました。問題点が想像していた場所と異なったことと、Pythonのreprが改行コードを含むファイルを表示する際の特徴とがかぶって問題をややこしくしてしまっていたようです。
問題点および解決策を一言で説明するとPythonでバイナリデータをファイル出力する際には"w"ではなく"wb"(バイナリ書き込みモード)でファイルを開かなければならないと言うことです。こんなことに今頃つまずいて自分でもびっくり。今まで一度もバイナリファイルをあつかったことがなかったんですね。
以下のソースは、試しにいろいろな改行コードをファイルに書きだし、それを読み込んで表示するものです。
fo = file("c:\\test.zip", "w")
fo.write("a(\x0A)")
fo.write("d(\x0D)")
fo.write("da(\x0D\x0A)")
fo.write("ad(\x0A\x0D)")
fo.close()
fi = file("c:\\test.zip")
data = fi.read()
fi.close()
print repr(data)
出力結果は'a(\n)d(\r)da(\n)ad(\n\r)'。これを見て「\nが\x0Dで\rが\x0Aだな」と思ったのが勘違いの始まり。これをウェブサーバにアップロードしてからurllibでダウンロードすると以下のようになります。
>>> import urllib
>>> urllib.urlopen("http://www.nishiohirokazu.org/files/test.zip").read()
'a(\r\n)d(\r)da(\r\r\n)ad(\r\n\r)'
これを見てurllibの使い方が間違っているものと思って悩んでいたのですよ。実際はファイルの出力が問題だったわけです。しかしバイナリモード("wb")で出力してもテキストモード("w")で出力しても、それを読み込んでreprすると「'a(\n)d(\r)da(\n)ad(\n\r)'」と表示されてしまいます。ファイルサイズはバイナリモードで書き込んだものが20バイトで、アスキーモードで書き込んだものは23バイトなので、この時点で改行コードがおかしくなっているのは間違いありません。しかし、Windows用Pythonが"\x0A\x0D"のことを「これはWindowsの改行だから」ということでか「\n」と表示し、しかもただの"\x0D"もUNIX本来の改行なので「\n」と表示してしまうので気づけませんでした。
難しいですね。「Windowsの改行コードは"\r\n"」で統一してしまえば誤解の余地はないのですが、波及範囲が広いので今更変更はできないのでしょう。
結構降ってますねぇ。まぁ、おかげで未来館はすいているとプラス思考してみます。
レシートを洗濯してしまったせいで細かい白いゴミがたくさん部屋に散らばったので掃除機が欲しい…とりあえず懸賞に応募してみよう(この前ので味をしめたらしい)
6月12日のクレジットカードの支払額を引くと手持ちの現金が2万円ちょい。交通費が1日1100円で、食費が900円として、10日しか持たないなぁ。…あ、そうか、クレジットカードで食料を買ったり、カードの使える外食屋に行けばいいのか…。せめて「6月25日に振り込まれます」とかわかっていれば計画のたてようもあるけど、いったいいつになったら振り込まれるのかわからないんじゃどうしようもないですね。6月中には振り込まれることを期待。
ただいま。プラネタリウムは満席でした。受付のお姉さん曰く「開場前から何百人も並んで待たれているので開場の時に来て予約しないと無理」だそうです。いくら何でも「何百人」は誇張じゃないかと…。とりあえず、一般入場が500円で、友の会の年会費が1000円で、友の会会員は入場料無料なので2回で元が取れます。会員になります。
0ヶ月児でも母国語と外国語を識別できるそうです。実験内容はフランスの赤ちゃんにフランス語とロシア語を聞かせた場合に、おしゃぶりを吸う頻度(sucking rate)が有意に変化するというものでした。USB接続でsucking rateを可視化できるおしゃぶりとか売っていたら買ってしまいそうです。
あと、赤ちゃんは寝ているときでも周りの音を聞いていて、聴覚野が盛んに活動しているんだそうです。母親が家にいて父親が外で仕事をしているケース(たぶん自分も子供ができたらそうなるだろう)では、赤ちゃんの中での父親の存在が薄くならないように、声が周りにも聞こえるモードで電話を受けてもらった方がいいかもしれないですね。
展示に関して、いっぱいいろんな生物の神経系が展示してあって面白かったです。ニホンザルの脳がセントバーナードの脳より小さかったのが意外でした。
スーパーは19時前に行くといっぱい売り物があっていいですね。さすがに23時前の閉店ぎりぎりじゃぁダメですね。明日は魚料理を作りたいと思います。初挑戦。
gas station。いやいやいやいや。確かに事故動画だけど予想を裏切られた(笑)
SQLについて勉強していますが、「どうすれば**できるか」じゃなくて「**をするときに内部で何をどうしているか」が書いてある本を読まないと、中で何が起きているのかがさっぱりわかりません。それがわからないことには何が効率のいいクエリーなのかや、どういうテーブル設計が効率がいいのかを考えようがないです。うーん。とりあえず効率のことは度外視して勉強するべきなのか…。
グラフ理論的な意味のVertexはほとんど何も持たない、単体としてクラスにする価値のあまりない概念です。java.lang.Objectみたいなもの。位置や速度の情報を持ったMassPoint(質点)クラスがあり、それを継承したVertexクラスがあるわけです。しかし、今のVertexクラスは箱状の見かけのレンダリングと密結合になってしまっています。Graphが持つのはVertexなのですが、グラフのレイアウト機能を使いたい人は必ずしも今のVertexの外見までは欲しくはないはずです。また、GraphがVertexというConcreteなレンダリング機能を持っているクラスと密結合なせいで、このままでは見かけの違う(たとえば丸い)頂点を追加することができません。
一歩下がって考えると、レンダリング機能が根幹のGraphやEdgeやVertexにあるのがおかしいわけです。というわけでGraphとRenderableGraph、VertexとRenderableVertex、EdgeとRenderableEdgeは分離します。
分離しました。ふむ、Edge.renderの中でVertexのbound(箱のふち)を取得して、矢印がくっつく位置を計算していますね…。しかしVertexが丸かったり四角かったりできるようにするためには辺の中でそんな計算をしていてはダメですね。この部分は辺の方向ベクトルndirを与えて、頂点の中心からのずれoffsetを求めているので…これをRenderableVertexにcalcOffsetをつけてそっちに任せてしまえばいいですね。
あー。Selectionクラスが辺のselected属性にアクセスしているけども、この属性はRenderableEdgeに属すべきか、それともその子のLinearEdgeに属するべきか。RenderableEdgeに属するか、さもなくばどこか別の方法で保持するべきでしょうなぁ…、少なくともLinearEdgeなんていうConcreteなクラスにSelectionクラスの中でキャストするのはあり得ない設計だし。ただ、他の場所に保存すると1回の描画のたびにRenderableEdgeがみんなでそこへアクセスするので、なんだかなぁ…という感じ。辺が「選択されているかどうか」という属性を自分で持つのは自然。ただRenderableEdgeという名前にはそぐわないですね。ただこれだけのためにSelectableEdgeなんてのを作る気もあまり起きませんが。
今日はGRINEditがよく進んだ。そして去年の夏のプログラミングシンポジウムで発表したNarVisualizerを引っ張り出して、向こうのプロジェクトからXML-RPC周りのコードを取り込み、向こうのプロジェクトにはこちらの新しい物理演算エンジンを使うようにして実装のサンプルにする方針で。次回は来週の木曜日。
21時。おなかがすいた。もう帰ります。
あー。これは時刻が出るから21時になる前にちょっと鯖読んで書いたのがばれてしまうｗ
ちなみに一応解説しておくと、コメントは投稿すると承認待ちの状態になり、メールで僕の所に連絡が来ます。自分のエントリに対するコメントは全部読みたいし、コメントスパムが気づくまでの間掲載されてしまうのは嫌だし、と考えると結局こういうソリューションになりました。あと結城浩の日記にインスパイアされています(笑) 匿名で反応できる仕組みは有意義だけども、それが管理者のモデレーションを経ずにすぐにサイトに反映される必要性はそれほではない。
あと、個別エントリーのページのパーマリンクの横のAボタンを押すとAタグが生成されてクリップボードにコピーされるかも知れません。WinXPのFirefoxでしか試してないので他の環境でどうかは不明。個別のページだけじゃなくてカテゴリ内一覧とかトップページとかでも使えるようにした方がよさそうですが…あ、思ったほど難しくはないな。でもいくつものテンプレートに同じスクリプトを入れて回るのはDon't Repeat Yourselfの精神に反しますね。MovableTypeのモジュールの使い方を調べなきゃ。Movable Typeユーザー・マニュアル: テンプレート
そうだ、明日何をするつもりだったのか思い出しました。明日は科学未来館で「「脳！ -内なる不思議の世界へ」関連イベント 脳！フロアトーク -俊英と語る最先端 Vol.4 「赤ちゃんの脳とことば」」があります。
そうそう、それとRubyKaigi2006は結局チケットを買い損ねたので行けません。ちなみに会場は11階ですが、僕の職場は7階です。土日なのでいませんが。
Jythonを使うデメリットがもう一つ。Eclipseのリファクタリング機能で名前を変更したりした場合に、Java的には整合性がとれてエラー表示が全部消えてすっきりした感じになっているのにPython側からの呼び出しがことごとく切断されていて悲しい。まぁ、evalとか重複するクラス名とかがないと仮定すれば置換でいけるのかも知れないけど…。
標準で58カ国の言語に対応しており、これまで認識精度で高い評価を受けておりましたが、v.11.0ではさらに日本語/英語の基本認識エンジンを強化、さらに日欧の文字が混在している文書も「日本語/欧文混在モード」の搭載により高い認識精度を実現しました。
うーん。日本語だけでいいからもうちょっと精度高くなりませんか。もしくはお安くなりませんか。
秋元さんのBlogでHTML構造のグラフによる可視化を知ったので、これを自分のGRINEditで実行するのにどれくらいの工数がかかるのか試してみました。
40分で見栄えの悪いものができました。Jythonでgraph.addVertexなどを叩けばもっと楽にできたはずなのですが、Jython2.1にはPython2.2からついたHTMLParserライブラリがなかったので断念。仕方なくデータファイルを書き出すことにしたものの、空白文字区切りのフォーマットのため頂点に名前が入っていないと色を指定できない…。ううむ。
とりあえずTODOは、まともなファイルフォーマットを作ることと、Jythonではライブラリが足りない or ユーザがPython使いでないというケースを考えてXML-RPCかなにかをサポートすることでしょうか。となるとやっぱりNarVisualizerプロジェクトを吸収するのが一番かも知れませんね、これはXML-RPCでPythonからでもRubyからでも可視化できるソフトなので。
ソースコード(81行、Python)は下記。Node.childrenとはかHTMLパーサのプロトタイプを作った時の名残なので必要ないですね。
from HTMLParser import HTMLParser
import urllib
# 10min. to make prototype parser
# 3min. to make coloring
# 22min. to visualize
colors = {
"a": "0000A0",
"div": "00A000",
"img": "A000A0",
"html": "000000"
}
for tag in "table tr td".split():
colors[tag] = "FF0000"
for tag in "from imput textarea select option".split():
colors[tag] = "FFFF00"
for tag in "br p blockquote".split():
colors[tag] = "A0A000"
def getColor(tag):
return colors.get(tag, "A0A0A0")
vertexList = []
edgeList = []
def addVertex(v):
vertexList.append(v)
return len(vertexList)
class Node:
def __init__(self, name, parent):
self.name = name
self.children = []
self.parent = parent
self.id = addVertex(name)
def append(self, v):
self.children.append(v)
edgeList.append((self.id, v.id))
class MyHTMLParser(HTMLParser):
def start(self, url):
data = urllib.urlopen(url).read()
self.tree = []
self.cur = self.tree
self.feed(data)
self.close()
def handle_starttag(self, tag, attrs):
n = Node(tag, self.cur)
self.cur.append(n)
self.cur = n
def handle_endtag(self, tag):
self.cur = self.cur.parent
url = "http://labs.cybozu.co.jp/blog/akky/archives/2006/05/html_visualized_by_graph.html"
MyHTMLParser().start(url)
fo = open(r"c:\mysite_as_graph.txt", "w")
fo.write("VERTEX\n")
fo.write("%d\n" % len(vertexList))
i = 1
for v in vertexList:
fo.write("%d\t_\t%s\n" % (i, getColor(v)))
i += 1
fo.write("EDGE\n")
for e in edgeList:
fo.write("%d\t%d\n" % e)
fo.close()
GraphインスタンスがVector anchorListを持つようになりました。また、Anchorクラスを作成し、これがアンカー対象の頂点targetと、アンカーされる位置positionを持つようになりました。現状では頂点のアンカーは「優先度の高い『速度を0にせよ』命令による他の物理法則由来の速度の上書き」によって実現されているためpositionは使われていませんが、これは汎用性に乏しいので将来的に「『ターゲット頂点の位置が規定位置から一定誤差以内に収まる』という制約」によって実現することを目指してつけたものです。
これに伴いMassPoint.anchoredは削除されました。
Vector AnchorListはHashtable AnchorTableに変更されました。キーがVertexで値がdouble[] positionです。 ドラッグ中に頂点がマウスについて動くのを、従来は「マウスダウン時にanchored(他の力による速度が0で上書きされる)状態にして、マウスムーブ時にpositionをマウスカーソルの位置から計算して指定」という方法で実装していました。しかし、将来的に制約で実装することを考えるとこれは「マウスダウン時にアンカー(頂点を特定位置に縛り付ける制約)をセットし、マウスムーブ時にアンカーの位置を変更」となる方がよさそうです。そうすると、特定頂点につけられているアンカーの位置を頻繁に変更するわけですから Vectorは適切なデータ構造ではありません。VertexをキーにしたHashtableが適切でしょう。一つの頂点が複数の異なる位置にアンカーされることはありえないということも表現できて一石二鳥。
VecWithPrior(優先度付きベクトル)という癌を取り除くために、一時的にアンカーの優先度を他の力同様の0に変更。つまり「速度ベクトルを0で上書き」ではなく「頂点の位置を目的の位置へ移動するような速度がかかる」に変更したと言うことです。こうすると、頂点をドラッグして動かしたときに「頂点から生えている見えないバネを持って引っ張っている」ような状態になり、後ろから他のバネが引っ張るので頂点がマウスポインタから少し離れた位置に漂ってしまいます。
Constarin(制約)はPhysicalLaw(物理法則)の子クラスではなく、親クラスなのかも知れません。つまり「満たすべき条件を満たしているかどうかのチェック」が常にTrueを返すような特殊なConstrainがPhysicalLawである、という設計です。PhysicalLawの適用はPhysicalLaw#applyなのですが、チェックする関数の名前は何にしましょうかね。boolean validateですかね。
validateとapplyは構造的に非常に似ています。don't repeat yourself。applyがisSatisfied(制約が満足されたか)を返すようにすればいいですね。SpringEdgeやRepulsionは常にtrueを返し、Anchorは動かすべき頂点がなかった場合のみtrueを返す、と。
ViewportTransformerクラスにscaling, invScalingメソッドを追加しました。絶対ベクトルのビューポート変換だけではなく、相対ベクトルの変換もサポートする必要があると思ったので。これで、たとえば「アンカーの位置と頂点の位置のずれがスクリーン座標系で0.1ピクセル未満」なんて処理を行うのに「アンカーの位置をビューポート変換、頂点の位置もビューポート変換、その差を取って0.1と比較」とやらなくても「アンカーの位置と頂点の位置の差分ベクトルをビューポート(スケーリング)変換、その大きさを0.1と比較」とやれるようになります。
一時期「semi-structured dataの可視化」を考えていたせいで、グラフを保持するフィールドの名前がstructure。でもクラスはGraph。フィールドの名前をgraphに変更しました。
Aggregator.aggregateを修正して、制約をサポートしました。制約もPhysicalLawクラスの子クラスですが、applyTillSatisfyメソッドがtrueを返します。
VecWithPrior(優先度付きベクトル)を使用しているところを全部修正してをVecWithPrior.javaを削除しました。コミット完了。
これでVecWithPriorという癌も取り除けたので、他の制約も入れやすくなったはずです。たとえば天井に張り付くとか。NarVisualizerあたりを、このライブラリを使って再生してみようかな。
うーん、ちょっとZIP形式でアップされているデータを自動的にダウンロードして処理するスクリプトを書こうと思ったのですが、「BadZipfile: Bad magic number for central directory」と言われて解凍できません。解凍ツールでも解凍できません。調べてみたらPythonでDLしたファイルとブラウザから右クリックで保存したファイルのサイズが違います…。Iriaでダウンロードしようとしたら「Requested Range Not Satisfiable」なんて言わました。User-Agentを試しに'Mozilla/4.6 [en] (Win95; U)'にしたら一応ダウンロードはできました。というわけでPythonでもUser-Agentを偽装すればいいわけですね。
ダメでした。Iriaが使っているヘッダを全部まねしたのにうまく行きません。
あああっ、改行コードがっ！opener.open(req).read()しているだけなのになぜ変わるっ！
正月にパズル雑誌に載っていた連結数独(数独が複数連結しているもの)を解くために書いたPythonスクリプトを引っ張り出して、特定の条件をみたす数独の問題を作るプログラムを作ってみたのだけども停止しない…orz 問題を解くのよりも問題を作るのの方が難しいのです。
電車を待っている間にプログラムを書くのは難しくないですが、駅から自宅まで歩きながらプログラムを書くのは難しすぎました。１：歩いているとマシンが揺れるので画面が見づらい。 ２：歩いているとマシンが揺れるので左手にかかる負担が大きい。 ３：歩いているとマシンが揺れるのでThinkpadのHDD保護機能で時々固まり、その間脳内補完でプログラムを書かなければならない。 20分のコースで十数行しか書けません。
駅に着いたら11時半だったので明日の朝ご飯のパンが買えませんでした。
電車賃が一日1100円かかっていることが判明。1週間に5500円。4週間で22000円。ビューカードを作ると1%ポイントがついて月に220円？
Knuth先生のDancing Linksアルゴリズムで数独は解けるのだけど、一つの問題につき729x324のマトリックスを作ってしまうのがなんというかすさまじいというか。双方向リストを使って疎な行列を効率よく実装することが前提なのですな。
現在、すべての物理法則は「すべての頂点のリスト」と「すべての辺のリスト」への参照を持っている。しかし「特定の頂点だけ天井に張り付く」だとか「特定の頂点は中心に固定」などのニーズを考えると、これは物理法則がそれぞれ「ターゲット」を持つようにした方がよい。さもなければ、頂点クラスに次々と属性を付与していく羽目になる。現状でanchored(固定されている)というフィールドを持っているが、もし仮に「一部の頂点だけ天井に張り付く」という物理法則を入れようと思ったらtoBeOnCeil(天井に張り付くべき)という属性をVertexクラスに付与するのか？それはどう考えても美しくない。じゃぁ、Vertexクラスを継承してtoBeOnCeil属性を持ったVertexClingable(貼り付ける頂点)クラスを作るのか？これも微妙。
つまり、現状は上のようになっているが、下のようにしたほうがよいのではないかと思う。
aggregator = new Aggregator();
aggregator.addLaw(new SpringEdge());
aggregator.addLaw(new Repulsion());
aggregator.addLaw(new NoVelocityIfAnchored());
aggregator = new Aggregator();
aggregator.addLaw(new SpringEdge(med.edgeList()));
aggregator.addLaw(new Repulsion(med.vertexList()));
aggregator.addLaw(new NoVelocity(med.anchoredVertexList()));
class PhysicalLaw{
public void apply(Context context){
}
}
適用されるたびに対象への参照を受け取っていますね。とりあえずContextクラスとその子のContextWithEdgesを取り除いて修正し、動くことを確認したのでコミットしました。現状は
aggregator = new Aggregator();
aggregator.addLaw(new SpringEdge(edgeList));
aggregator.addLaw(new Repulsion(vertexList));
aggregator.addLaw(new NoVelocityIfAnchored(vertexList));
public class NoVelocityIfAnchored extends PhysicalLaw {
private Vector target;
public NoVelocityIfAnchored(Vector target) {
this.target = target;
}
public void apply(){
for (int i = 0; i < target.size(); i++) {
MassPoint p = (MassPoint) target.get(i);
VecWithPrior zeroVel = new VecWithPrior(0.0, 2, 0.0, 2);
if(p.anchored){
p.velocityList.add(zeroVel);
}
}
}
}
という状況なので、次はNoVelocityIfAnchoredをNoVelocityに変えて、targetとしてVelocityを0にすべき頂点を受け取るように変えましょう。今日はもう9時なので続きは明日。
「この種類の頂点は壁にへばりつく」とか「頂点は画面外には出ない」などは、力として実装すると他の力の影響を受けて満たされないケースが出てくる。他の力の計算が終わり、頂点の位置を更新した後で、そういう「制約」だけ計算してやればよいが、この場合、複数の制約があるとやっぱりお互いに影響を与えあって両方満たされなくなる。いままでは「物理法則」に「優先度」をもうけて、優先度の高いものほど後から計算されるようにしようかと思っていたけども、それはいまいち宣言的じゃない。「物理法則」の特殊なバージョンとして「終了条件」を持った「制約」を作って、その終了条件が満たされるまで演算を繰り返すほうが「物理演算の適用される順番」なんていう些末なことに悩む必要がなくなるのでいいのかも知れない。
物理演算整形ライブラリの目指しているところは「物理演算でのレイアウトを宣言的に記述できる」という所です。「辺は引力を持つ」「頂点間に斥力が働く」「画面外には出ない」「壁は吸着力を持つ」などと書くだけで、動的レイアウトが可能になるのを目指しています。部分的には実現しています。課題は今述べたような「足を引っ張り合う制約」などです。
ハングアップを防ぐために最大繰り替えし数を決めて、規定回数の演算で制約が満たされなかった場合はレイアウトを一時停止する、というのもツールとしては悪くない落としどころかも知れませんね。
「宣言的」という言葉の説明をすべきかなぁ、とググったら制約プログラミングの説明のページがあったので参考までに貼っておきます。constraint.org/INTRODUCTION
そうか！「未踏ソフトウェア教」を作ればいいんだ！(何)
ダメだ！「未踏ソフトウェア創造事業」が「特定の宗教に与する行為」になってしまう！(爆)
メイドカフェとか執事カフェの流れで、未踏カフェがあると面白いのに。壁にbitが並んでたり。普通のマンガ喫茶店程度の料金で技術書が読み放題。収益性が…。
自分で実装しておきながら「おおっ、こんなことできるじゃん」と思ったこと。
実行時に選択範囲の辺を取得し、それの長さフィールドを書き換えることで「選択範囲を収縮させる」ことができる。 デモの時に、動的に頂点の色を変えても見栄えがしないけども、辺を変えると全体が「わっ」と動くからいいかもしれませんね。
