2012/07/13

Unbounded spigot algorithm

ふとしたきっかけでπなどの値を「頭から順番に」求めるSpigotアルゴリズムを 見直していたら、「メモリの許す限り順番に値を計算し続ける」アルゴリズムを示した 論文を見つけた。

• Jeremy Gibbons, Unbounded Spigot Algorithms for the Digits of Pi

よくあるspigotアルゴリズムは計算したい桁数を最初に決めてデータ構造を初期化する必要がある。Gaucheのexamples/spigotに入ってるのもそれ。 一方、こちらのアルゴリズムはあらかじめ精度を決めておく必要がない。

論文のコードはHaskellで書かれている。

piとpiLは使っている級数の違い。後者の方が生成が速い。論文には他にもう一種類出ている。

実行例。結果は無限数列で返ってくるので欲しいところまで取れば良い。

*Main> take 100 Main.piL
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4,5,9,2,3,0,7,8,1,6,4,0,6,2,8,6,2,0,8,9,9,8,6,2,8,0,3,4,8,2,5,3,4,2,1,1,7,0,6,7]

遅延評価に大きく依存したコードなので通常のSchemeに直すのは面倒そうだが、 gauche.lazy を使えばわりと素直にGaucheに移植できる。 元コードのパターンマッチ部分を手で展開するのはさすがにしんどかったので ちょっとマクロの手を借りた (define*のところ)。

あと、上の素直なコードだと状態配列がすぐに巨大なbignumになって、多倍長演算の遅い Gaucheには負担なので、可能な限り約分するようにしている (lftのところ)。

pi、piL はジェネレータを返すので、こんな感じで結果を取り出せる。

gosh> (generator->list (piL) 100)
(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1 0 5 8 2 0 9 7 4 9 4 4 5 9 2 3 0 7 8 1 6 4 0 6 2 8 6 2 0 8 9 9 8 6 2 8 0 3 4 8 2 5 3 4 2 1 1 7 0 6 7)

先頭から次々に、いくらでも桁を取り出せるのは魅力的なんだけれど、 実際に走らせてみると状態配列(lft)の値が(適宜約分しても)どんどん大きくなるので、 実は計算量はO(n^2)とかになってるっぽい。桁数が進むとどんどん遅くなる。 なのでおもしろいけれど実用的ではなさそうだ。

Tags: Gauche, Haskell, Programming

2012/07/12

ピアノレッスン54回目

• Stravinsky: Tango for piano
  • 自分の思い描く感じで弾けるようになってきた、ような気がする。 細部まできちんと弾くのはまだ難しい。
• Janáček: 1.X.1905
  • M=48で。リズムキープが難しい。

Tag: Piano

2012/07/11

Clojureの選択

Clojureはなぜ遅いのか、という話

• Martin's Computer Programming Blog: Why is Clojure so slow?

JVM言語同士で比べてもやっぱり遅い。

• 起動の遅さが際立っている。これはどうも初期化時にdocstringやその他のメタデータをセットアップするのに時間がかかってるらしい。
• 初期化が終わって実際の処理に入っても遅い。これはimmutableなデータ構造のオーバヘッドらしい。immutableなデータ構造でもアルゴリズムのオーダーをmutableなやつと同じにすることはできるが、定数係数のオーバヘッドはある。

まあ、でもRichはそれは覚悟の上というか、設計上そういう選択 (遅いのはわかってるが 他のメリットを優先) をしたわけだからなあ。比べられる土俵が悪いという気はする。 そうは言っても比べられちゃうのは仕方ないけれど。

Gaucheでは上の2点については速度の方を優先する選択をしている。 util.sparseのsparse vectorはClojureのpersistent vector構造を 参考にしているけどmutableだし、docstringが無い理由のひとつはまさしく 起動時のオーバヘッドを避けるためだ。

どちらの選択も絶対的な良し悪しがあるわけじゃなく、目的によるとしか言えない。

もっともClojureはREPLでなければバッチコンパイルを通せるのだから、 docstringをまとめてひとつのdata領域に押し込めるとかできそうなものだけど、 JVMの制約だったりするんだろうか。ネイティブに落とす感覚だと、 コンパイル時にメタデータをデータ配列に固めちゃって、関数の方にはオフセットを 持たせとけば、実行開始時にデータ配列をmmapするだけなんで一瞬で済むはずだけど。

(Gaucheは静的データに関してはポインタの絶対値を持たせているので、 起動時にld.soがリロケートするオーバヘッドはかかっているはず。こちらは 起動速度と実行速度のトレードオフ。)

Tags: Gauche, Clojure

2012/07/05

ピアノレッスン53回目

• Kapustin: Op40-8
  • MM=120。指よりも頭が律速になってる感じ。
• Janáček: 1.X.1905
  • 第一楽章通し。まだゆっくり。妙なアクセントがつかないように気をつける。

Tag: Piano

2012/07/05

gitと継続の類似性、というのをふと考えた。

gitは変更の依存関係を記録している。マージを考えなければ、これはブランチを葉とする木構造になる。一方、継続がある処理系ではスタックが木構造になる。ただしgitではスタックのポップに相当する操作 (git checkout HEAD^) はあまり一般的ではないが。

call/ccで継続を捕まえるのは、gitの開発ツリーで現在のHEADコミットIDを覚えておく(タグでもつけて)ことに相当する。git checkout HEAD^ で開発を巻き戻しても、コミットIDさえ覚えていればいつでもその状態に戻ってこれる。

• 現在のブランチでcall/ccを発行=現在のコミットBを記録

       CALL/CC
  ---A----B
          ^SP
  

• いくつかスタックを積む=コミットする

       CALL/CC
  ---A----B----C----D----E
                         ^SP
  

• もいちどcall/ccでコミットEを記憶

       CALL/CC        CALL/CC
  ---A----B----C----D----E
                         ^SP
  

• 最初のcall/ccで捕まえた継続を起動する(大域脱出) は git reset --hard B に相当

       CALL/CC        CALL/CC
  ---A----B----C----D----E
          ^SP
  

call/cc を使ったコルーチンは、二つのブランチを行ったり来たりする感じ。

• 上の状態から別の変更をいくつかコミットした。

       CALL/CC        CALL/CC
  ---A----B----C----D----E
           \
            \
             F----G----H
                       ^SP
  

• ここでcall/ccでもってIを記録しておいて…

       CALL/CC        CALL/CC
  ---A----B----C----D----E
           \
            \       CALL/CC
             F----G----H
                       ^SP
  

• Eを記憶していた継続を起動 = git checkoutでブランチを乗り換え

       CALL/CC        CALL/CC
  ---A----B----C----D----E
           \             ^SP
            \       CALL/CC
             F----G----H
  

• コルーチンはそれぞれの枝の最先端をどっかに記録しておいて行ったり来たりすることで、 ブランチを切り替えて仕事するのに類似。

部分継続はgit rebaseに少し似ているかもしれない。 git resetと区別するために、部分継続のshift/resetを 大文字でSHIFT/RESETと書くことにする。

• スタックが深くなってゆく途中でRESET、SHIFTを発行したとする。

        RESET          SHIFT
  ---A----B----C----D----E
                         ^SP
  

• SHIFT部分の実行を終えると、スタックは自動的にresetまで巻き戻される。git reset --hard B したと思えばいい。

        RESET          SHIFT
  ---A----B----C----D----E
          ^SP
  

• ここからもひとつpopしたとする。 (git checkout HEAD^)

        RESET          SHIFT
  ---A----B----C----D----E
     ^SP
  

• 新たな変更を加えてcommitしてく。

        RESET          SHIFT
  ---A----B----C----D----E
      \
       \
        F----G
             ^SP
  

• 途中でRESETしたとする。

        RESET          SHIFT
  ---A----B----C----D----E
      \
       \   RESET
        F----G----H----I
                       ^SP
  

• この時点でさっきのSHIFTで捕まえた部分継続を起動することは、 git rebase --onto G B E に相当する。

        RESET          SHIFT
  ---A----B----C----D----E
      \
       \   RESET
        F----G----C'---D'---E'
                            ^SP
  

とここまで考えたんだけど、マージとか考え出すとアナロジーが破綻するので やっぱり無理がある気がして放り投げ。オチは無い。

Tags: 継続, git, Programming