週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
昨日やっとFinger Treeのサイトにアクセスできました。読んでみます。
  • Abstを読んでオーダーだけ確認。
  • p. 4の図に激しく混乱。
  • とりあえずAbstの知識だけで説明。
  • p. 4をやっと理解。
  • p. 8 Concatenation に驚愕。concatが非常に短く記述できることに感動しました。
  • 別にconcatって、この構造ではないほかの木構造でもそれほど難しくないような気もしてきました。 ←今ここ

基本は両端がちょっと浅いTreeです。そのためにDequeの動作、つまり最初と最後に償却Θ(1)時間で要素を追加したり削除したりできます。それと別の理由で、concatが償却Θ(log n)時間でできます。時間の評価が償却なので慣れないとちょっと理解しにくいかもしれません。私はまだ慣れてません。

どうしてこの構造になったのかは少し興味があります。Abstractに、「この時間での動作を達成するデータ構造はすでにある。しかしFinger Treeはもっと単純である」とあるので、関連論文を読むことによってそのあたりの歴史的知識がつくかもしれません。

スポンサーサイト

先ほど作ったDna2rna.hsがあんまり遅いので、ログをはかせつつどこが遅いか調べていました。すると、読み込みをSequenceに変換するところが遅いことが発覚。

list2sq :: [a] -> Seq a
list2sq = foldl |> Data.Sequence.empty
この定義が遅かったようです。しかも、そもそもData.SequenceにfromListが存在するのでこれは必要ありません。

fromListにすべて書き換えたらものすごく高速になりました。今のところ一分しないでrnaを吐き出します。stackを大きくする必要も、eager評価する必要もなくなりました。

出力されるrnaはまだ間違っていますが。 次はバグとりです。

今回のICFPCで注目を浴びた、HaskellのライブラリにあるData.Sequence。これで本当にDNA2RNAの高速な実装ができるのでしょうか。とりあえず実装。

テストDNAで実験した後、EndoのDNAを食わせてみました。すると、

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.
などというエラーメッセージが出て止まってしまいました。 スタック 8 MB を食い尽くしたそうです。 指示通りにスタックサイズを64, 80, 256 MBなどと拡張してみるものの、まったくエラーが消えません。

仕方ないので`seq`を駆使してeager評価。やっと何とかなるようになりました。まだ途中で止まってしまうので評価にバグがあるはずですが、手元には正しいdna2rnaもあるのでなんとかなりそうです。

Data.Sequenceのほかにも、eager評価するというヒントもウェブ上で仕入れたもので、今まで全然使ったことがありませんでした。まだhaskell experienceが足りないことを実感。

ちなみに、Sequenceのインターフェスは普通で、特に苦痛もなくプログラムがかけました。コードのほとんどは次のviewl インターフェスによるパターンマッチです。

data ViewL a
 = EmptyL
 | (:<) a (Seq a)
viewl :: Seq a -> ViewL a
リストのパターンマッチと変わりません。非常に楽です。

http://www.mapmsg.com/games/statetris/usa/

http://labs.cybozu.co.jp/blog/akky/archives/2007/07/statetris-48.html経由

全然アメリカの州とか知らない私でも、Easyを選んだら10:30位で解けました。 最後のコメントで "What planet are you from?" とか言われましたが。

さすがに地球人でもアメリカの州の位置をまったく知らない人はもっとたくさんいるはずですが......

ちなみに、Virginiaが西の方にあると信じていたのがすべての原因です。間違いないです。

終わりました。ばたんきゅうすぎます。

あんまりにも眠いので画像だけ上げて寝ます。

今日のびっくり:

ある動画で流れていたBGMが、 かしわもちのBGMと同じでした。

素材なのでかぶることはあるとかそういう問題ではなく、単純に背筋が凍りました。

昨日7/16/2007、夜11時代に地震がありました。それなりにゆれたと思います。しかしそれに関するニュースがほとんど見当たりません。新潟の余震かと思って「地震」で検索したものの、この時間のものにたずねあたりません。

見つけました。北海道新聞です。
北海道新聞:十勝で震度4 震源地は京都沖 異常震域現象起きる

 札幌管区気象台によると、今回の地震は、震源から遠くても震源付近より震度が大きくなる異常震域現象と呼ばれる。
 沈み込んだプレート付近で震源の深い地震が起きると、異常震域が生じる場合があり、今回は太平洋プレート付近で発生した地震波が、プレートの延びる北海道太平洋側に達したという。
時間と震源がわかったので気象庁地震情報も。 震源より離れたところで大きな震度が観測されています。非常に奇妙です。

記事によると、震源が深いとこのような現象が起こるそうです。ところで、370 km ってどのくらいの深さでしょう? 中越沖地震の震源が深さ 17 km なので桁が違うのはすぐにわかります。具体的に輪切りにした地球のどのあたりなのでしょう?

助けてWikipedia先生。 Wikipedia 地球によると、

6-35~670km -- 上部マントル
深さ370 km は上部マントルです。そこって半分解けてたりしませんか? 震源なのだからそのはずはないと思いますが、一応確認します。

Wikipedia マントルによると地殻と上部マントルとをあわせてリソスフェアと言い、ここはその名のとおり硬い、と。 リソスフェアの厚さはどのくらいでしょう? Wikipedia リソスフェアを見てみます。

以下引用。

その厚さは加えられた力に対する物理的な応答で定義され、測定方法によって様々な値を取る。短い時間スケールの力に対しては(例えば地震)かなり深部の高温部分でさえも弾性的に応答するので、リソスフェアは厚い(時に数100キロメートル)。逆に長い時間スケールでは(例えば大陸氷河の消長)、浅部の十分に弾性的な性質を持つ部分だけが長い期間その過重を支えることができる。従って、厚さは数10キロメートル程度になる。通常リソスフェアの厚さと言えば後者を指すが、いずれにしても一つに定まらない量である。
要するに適用範囲しだいで値が変わるようです。「リソスフェアの厚さ」がこれほど面白そうな話になるとは思いもしませんでした。

週末にアルカトラズ島(参考:Wikipediaのアルカトラズ島)に行ってきました。

旧要塞、旧監獄、そしてスー族が一時期占拠したアルカトラズ島です。特に監獄として非常に有名です。その監獄の展示が非常に強力で感動しました。

音声ガイドによる案内がついていて、これがまず多国語対応。しかも日本語のガイドがよくできています。ガイドは囚人の日常、教誨師の日常とそれからいくつかある事件を解説しています。いずれも臨場感にあふれています。どこのドキュメンタリー番組かと思いました。しかも実物付きです。

一例

「料理は囚人の栄養を考えて、それなりのバランスがとれるものにしていました。」という理由でスパゲッティがよくでるようになり、囚人がスパゲッティ嫌いになっていきます。ついに「今度またスパゲッティが出たら、テーブルをひっくり返してやるぞ!」と言い出す囚人までいる始末。あげくにまたスパゲッティが出ると、そいつはテーブルをガシャーンと倒します。周囲の囚人も悪乗りしてガシャーンと。そのうち大変な騒ぎになって、看守が大慌てで鎮めます。
このあたりはテーブルを倒す音、騒ぎの声、それから看守の警笛などがちゃんと効果音として入っています。


という記事を下書きにしたまま二週間が過ぎました。ここは東京でございます。

前の記事は当然これを意識したネタフリでした。肝心のネタを出さず放置したためなんかコメントがついていますがそれもまた面白いことです。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。