d.y.d.

21:28 06/02/27

腹痛ぇww

文字列検索アルゴリズム

実は今まで知らなかったKMP法のやり方を今日はじめて覚えました。とても有名なので名前は知ってたのですが、どこを見ても実用上の性能はBM法に劣ると書かれているので、じゃあBM法知ってるからそれでいいや～、と思って、これまでずっと飛ばし読んでいたのです。調べてみると、データの偏り方によってはKMP法に軍配があがる場面もあると判明。普段は使わないにしても、ちゃんと利点欠点を理解してから判断しておくべきだったなあと反省中であります。

歌

街中で "Since U Been Gone" が流れているのを耳にして、Avril Lavigne の新曲かな？と思って調べてみたら違う人でした。歌い方と声が似ている気がする。気に入ったのでそのうち買う予定。

14:31 06/02/20

CSSテスト

兼、反例。

module F = functor (V : T) -> struct
  let _ = let rec loop x = loop x in
    V.g (fun v -> if V.g (fun _ -> v) then loop() else v)
end

ところで、module IE と module Firefox が文脈等価でないことの一例としてはCSSのwidthの扱いがあることが示されているのですが、どうしたものかな。 pre要素、横幅は親との相対で固定で、横に長いときはその固定幅のままスクロールバーが出て欲しくて、条件コメントはなんとなく使いたくない。うーむ。

追記： namasuteさんが既に全く同じ解を書いておられた。ぎゃーす。

16:46 06/02/16

翻訳

Sunの翻訳ガイド … これは参考になります。他にもいろいろ従ってみようと思った点はあるのですが、特に、「操作の手順を説明する文章では、ユーザーの行為は能動態、機械の動作は受動態にします。」は、これが統一されていないせいで読みにくくなってる箇所が多数Dの和訳にありますね。今後意識するようにします。

知能

やっと読んだ。『考える脳考えるコンピューター』。

なるほどと思える内容でした。この本では「振る舞い」「意識」「感情」「心」といった要素を排除して、「予測」の能力を知能の本質として定義しています。その定義の元での人工知能は「人間っぽい」ものとは大きく離れているだろうけれど、人間っぽさのうち、何か物事を「考えている」という特徴だけを純粋にとらえたものになるだろうし、すなわちそれを「知能」と呼ぶのはなかなか適切な定義だろう、というお話。この考え方が、いくつもの例を通して主張されています。で、確かに読んでみると納得できる気がします。さらに、その「予測」を実現する単一の基本原理・メカニズムについて、脳の新皮質やらニューラルネットやらを通した考察がなされていて、これも面白い。人工知能の実現方法としてだけでなく、「予測」が本質とする根拠として見ても説得力があります。

なんとなく compression and prediction are equivalent という話を思い出したけれどたぶん関係ない。

あと先日ちょっと触れた点について…。古典的には、知的活動において人間と全く同じように振る舞うことができるなら知能があるとする、という十分条件として機械の知能の有無を判定する「チューリングテスト」が提案されていまして、これに対する反論としてサールによる「中国語の部屋」がありました。私はサールのこの例がなぜ反論になっていると思えるのかすら理解できていなかったのですが、この本では、この部屋は「予測」に基づいていないゆえに知能の本質とは外れるのだ、と。しかしだからといって、「コンピュータが知能を持てない」ことにはならない。例えば脳の動作を完全にシミュレートした単調作業をする人間入りの中国語の部屋があれば、それは知能と言える、という立場。なるほど、この立場は理解できる。

23:37 06/02/14

2/14

本日生協の特設チョコレート売り場で、Solitaire（一人遊び）という実に含蓄の深い名前のチョコが売られていたので思わず購入。本当は多分、一粒の宝石、という意味でつけられた名前なのでしょうがそんなことは知らない。

最適化の第一原則

id:lethevert さんのお話…ほぼ全面的に同意です。特に同感なのがこの部分。

パフォーマンスチューニングというのは、パフォーマンスデータを確認して、ボトルネックを確認して行うべきことで、

そして、なのだから、ArrayList を使う根拠が特にないときにも List list = new ArrayList() と書かざるを得ない現状はよろしくないと思うのですよ。「ArrayListが良い」と確認する必要ができて確認したときに初めて、ArrayListと書きたい。そうでない時には書きたくない。これを実現するためにインターフェイスのnewという構文が適当かどうかについては実は全然ちゃんと考えていないのですけど、とにかく具体的な実装を明示せずに仕様を満たすインスタンスを生成できる、というのは悪くない、というのが私の考えです。

先日の記事を見ると、 Listは例が悪い、データ構造は実装によってまったく特性が違うから、というのが lethevert さんの考えだと思います。そしてこの一点が、私が異論を唱えてみたいところです。（確かに SAXパーサーなどで例示した方が明らかに問題がクリアになるのですが、まあそれはそれで。）

Listに限らず、コレクション系は、実装によってその性能特性がものすごく変わる。だから、もしもまじめに計算量のことを考えているプログラマなら、どんな場合でもそのListの実装がどうでもいいなんてことにはならないと思う。（ある実装なら数秒の処理が、ある実装だと数時間ということが、珍しくないのがデータ構造の世界だから）

実装に本当に興味がない例として挙げておられた整数の場合ですら、性能は実装によって何百倍何千倍のオーダーで変わります。BigInteger の内部表現が2進のビット演算に適した表現形式なのか。あるいはシンプルに文字列化して10進表示するのを主眼に据えた表現形式なのか。乗算はFFTなのかKaratsuba法なのか単純な筆算方式なのか。計算量のことしか考えていないプログラマなら、実装の差は看過できません。ですが、ほとんどの場合、実装に興味がないのは正しい。 BigIntegerを使うとは言っても実際の数値は32bitや64bitを少々あふれるかもしれない程度で、常識的な操作では速度差やメモリ効率の差が有意になるような何万桁の値は来なかったり。そもそも整数演算が最適にチューニングしたときの100倍遅くても問題にはならなかったり。実際に使う操作は加算だけで、差が出てくる乗除算は一度も使っていなかったり。もちろん整数演算の効率が物凄く効いてくる場面も多々あるのは確かですが、同時に、そんなものは気にならない、気にすべきでない場面も沢山あります。で、そういう場面で毎度具体的な実装を指定して整数オブジェクトを生成するのは非常にわずらわしい。

コレクション系、Listでも全く同じことが言えます。常識的な操作の範囲ではそもそも差が出るような大きなデータは来なかったり、List操作が100倍遅くても問題にならない場面だったり、実際に使う操作はaddとfor文だけで、差が出るようなget(int)や途中への挿入は一度も使っていなかったり。他の方はどうかわかりませんが、私個人に関しては一番最後のような使い方をするListがほとんど全てでして、これを毎回具体的な実装方法まで指定してインスタンス生成したくないと常々思っていたのでした。

もちろん、コレクション操作の性能がクリティカルに効いてくる場面は多々存在しますし、そのような場面では緻密に計算量を評価して最適なデータ構造について考えるべきです。さらに、プログラマたる者、そういう場面を見過ごさぬように計算量について常に気を配っておく必要があるのももちろんです。その上で、チューニングする必要のないと判断した場面では、もっとも楽で綺麗で読みやすいプログラミングを心がけるべきではないでしょうか。「すべての箇所で計算量が最適になるようにカリカリに調整する」のではなく、「チューニングする必要のある場所とない場所をきちんと判断して、前者には最適なデータ構造を与え、後者はそういう考慮がいらないことをコードの上でも示す、そう区別する」のがまじめに計算量のことを考えているプログラマではないかな、と。

20:49 06/02/13

続・PC修理

ドスパラすげぇ！預けて28時間で修理完了しました連絡が来た！素晴らしい！でも今度はサウンドの調子がえらい悪いんですが！どーしよう！

携帯電話

秋葉原に行ったついでに機種変更してきました。 SA700iS。 GPS機能の付いてる唯一のFoma。これ最強。

ところで、電話の際に番号通知する設定に変更するには「ネットワーク暗証番号」というのが要るらしいのですが、あれ、忘れた。そんなものあったっけ？というわけで手続きするまでしばらくの間、私が電話をかけると非通知になるそうなので、そこんとこよろしくお願いします。＞関係しそうな方々

00:49 06/02/11

PC修理

代車と同じような感じで、代ノートPCサービスってありませんかね。それなりに需要はあると思うのだけどなあ。今日サポートセンターに持ち込んで見るとして、 24日までに戻って来るだろうか。

それはそうと ATOK 2006 はx64対応です。わーい。ノートが帰ってきたら買う！

23:09 06/02/06

java.util.List

Onion開発日記経由でnew List()っていう話。これは確かに欲しいです。動機はみずしまさんが書いておられるのとほぼ同じで、変数をList型と宣言するような場合は、実装が何リストなのかは全くもってどーでもいいから。（Iterator.next が定数時間で動いて List.add(Object) が定数償却時間で終わることは暗黙のうちに期待しちゃってるけど）他の性質が欲しいことは無い…あるべきではない、と思うのですよ。もし仮に頻繁にリストの途中に挿入したかったりランダムアクセスしたかったりするなら、自分なら、変数の型もListではなくLinkedListなりArrayListなりにします。「ただのリストではダメで、ランダムアクセスがO(1)でないと困る」ような変数にListという型を与えるのは変だと思うし。（Mapに対するSortedMapみたいに適切な性質を保証したサブインターフェイスがあればそっちにするのですけど、無いので仕方ない。）

そして逆に、"拡張for文で回れさえすれば済む変数をLinkedListやArrayListという具体的な型で宣言する" のももちろん変。もちろん変なので、同様に、"拡張for文で回れさえすれば済むオブジェクトを new する時にLinkedListやArrayListなどと具体的な型を書かねばならない" のは避けたいなあと思うわけでした。

CSS

ちょっと新スタイルシートテスト中。これまで、borderを使うのはいかにもCSSCSSしてて嫌い、と考えていましたが、突然逆に border だらけにしてみるとどうなるかという挑戦。h1要素のハミガキ粉みたいな使い方は自分ではなかなか気に入ってるのだけどどうか。WinIE6 と FireFox1.5 でしか表示確認していないので、他の環境で崩れてたらゴメンナサイ。連絡くださればできるだけ修正します。

Claymore

ぎいゃぁあー！先月までのあれ全部死亡フラグか。凄いな。

20:23 06/02/04

ノートPC

バックライトの調子がおかしい…。時々突然消えてしまう。修理に出してる余裕あるかなあ。

D言語

newsgroupより。 DWT(SWT for D)を標準GUIライブラリってことにしない？という動きが。自分はWindows専用で事足りてたので SDWF をずっと使ってるのですが、ちょいとDWTも触ってみますか。標準で窓が出せて絵が描けるのはホビープログラマ向けには最重要の条件だと思うので、なにか一つ標準を決めるのには大賛成。

00:16 06/02/02

Gシャツ

Google Code Jam のTシャツが届きました。正確には、10日くらい前に届いていたらしいのですが受け取ってる時間がなくて、今日やっと手に入りました。袖に 092305 という謎の番号がプリントされています。「これなんだろう？また謎解きか？」としばらく首をひねっていたのですが、友人に見せたら日付に決まってるじゃんと即答が返ってきて悔シイ。

Zeta

PC-CRAFT はやっぱり Berry Japan のつながりらしい。うーん。他で買いなおすか。

Derive Your Dreams