北海道苫小牧市出身のPGが書くブログ

JITで爆速なgperlを試す

perl, gperl

Linux Mint上でgperlをビルドした。原則、ないと言われたものをどんどんaptで入れてっただけだけど、jit/jit.hがないって言われてそいつだけaptで解決できなかったのでこのPostScriptのファイル読んでlibjitをビルドした。

これで万事うまくgperlが作れたのでベンチ用のフィボナッチ数列を早速動かしてみると、

% time ./gperl sample/benchmark/fib.pl
14930352
./gperl sample/benchmark/fib.pl  0.21s user 0.01s system 192% cpu 0.112 total
% time perl5.18.0 sample/benchmark/fib.pl
14930352
perl5.18.0 sample/benchmark/fib.pl  7.78s user 0.00s system 99% cpu 7.806 total

perl5.18.0の37倍くらい速かった。この処理はjitが最大限効くgperlに非常に有利な処理ではあるけど、とはいえ、それでもやっぱりgperlは速い。

ついでにさらに差がつくと思われるたらいまわし関数も。こちらは自分の環境ではそのままだとセグフォして動かなかったので、関数の戻り値を変数で受けるように変更してからの実行。

% time ./gperl sample/benchmark/tarai.pl
13
./gperl sample/benchmark/tarai.pl  0.57s user 0.00s system 196% cpu 0.289 total
% time perl sample/benchmark/tarai.pl
13
perl sample/benchmark/tarai.pl  27.99s user 0.00s system 99% cpu 28.052 total

こちらは49倍速かった。ちなみに発表資料では100倍くらい差がつくという話もあったので、環境によってはもっと差が出るのかもしれない*1。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 00:23

今日は 圏論勉強会 第5回 の日です

レポート, math

圏論勉強会ではない方の圏論勉強会 第5回です。資料とustreamは公開されています。

• 今日は倚子が追加された
• ワークスアプリケーションズ社さんに感謝しましよう

第5回: 様々な射 / 講師 @9_ties さん

• Hom集合についての補足
  • A言語とB言語のトランスレーターtと問題のA言語での解法fがあるとする
  • B言語での解法はt.f (共変)
  • B言語でのインタプリタをinterpとすると、A言語のインタプリタはinterp.t (反変)
  • オブジェクト思考でも同様の考え方ができる
    • インスンタンスを作るのは共変
    • フィールドから値を取り出すのは反変
  • 計算機では射は実装する可能性があるもの → 自動で射を移せるのはありがたい
• 同型射
  • g.f = 1, f.g = 1, 同型射がある対象同士は同型
  • gは逆射 → 一意なのでf^-1と書く
  • 証明 → gとhがfの逆射であれば、g = g.id = g.f.h = id.h = h
• 函手は可換図を保つ → 同型性も保つ
  • fが同型射 → F(f)も同型射
  • fが同型射 → F(f^-1) = F(f)^-1
  • A ≃ B → F(A) ≃ F(B)
• C^opは同型性を保つ
  • 反変函手も同型性を保つ
• Hom(X,-)は共変、Hom(-,X)は反変
  • A ≃ B → Hom(X, A) ≃ Hom(X, B), Hom(A, X) ≃ Hom(B, X)
  • Aの回りの射とBの周りの射が対応
  • オブジェクトの性質は射に表われるので、重要
  • gとhをHom(X, f)とHom(f^-1, Y)でf.gとh.f^-1に移しても可換図は保たれる
• AとBが同型であれば区別できない
  • Aに関して成り立つことはBに関しても成り立つ
  • 具体的でないとわからないことは圏論で調べるのに向かない
• 例: (R, +)と(R, ×)は同型
  • 全然違うものだけど、区別できない
  • 例えば、メモリ効率などは不明
  • 一つの圏の中で全て表現しようと思うべきではない
  • 圏論で述べられる範囲については気をつけたほうが良い
• 同値関係 → 二項関係が、反射律、対称律、推移律、を満す
• 同型は同値関係
  • A≃A (恒等射)。A≃B ならば B≃A。A≃B,B≃CならばA≃C(合成)
• モノイドでの同型 → x・y = y・x = eのことなので、可逆元
  • (R, ×)の同型射は0以外の全ての実数
  • 同型"射"は関数とは限らない
• 半順序集合での同型 → x <= y, y <= x より x = y 、つまり自分自身のみ
• 証明の圏における同型 → 同値な命題
• fが単射 → f(x) = f(y) ならば x = y
• fが全射 → 任意のyについて、y = f(x)なるxがあること
• fが全単射 → 全射かつ単射
• Setsにおける全単射は同型射 → 証明はスライド参照
• 集合の要素の数が等しい → 全単射があること
  • カントールにより、無限集合にも一般化。濃度(cardinal number)。
  • Nと偶数の集合の濃度は等しい
  • カントール「任意の集合Aについて、A→P(A)への全射は存在しない」(P(A)の方が大きい)
  • 無限集合にもサイズ大小がある
  • オブジェクトの中の性質を射で表現したと言える
  • 計算機科学とも無関係ではない
• 証明(対角線論法): f:A→P(A)で全射のものがあったとする
  • X = {x: f(x)にxが含まれない}とする
  • 全射なので、f(x) = Xなるxがあるはずだが、xがXに含まれても含まれなくても矛盾
  • 計算機科学で言えば、停止性を判断するプログラムが作れないこと、の証明となる
• プログラムは文字の集まりなので、自然数と同じ濃度
  • できることとできないことがある、ということを意味する
  • 例えば、計算機では求めることができない実数が存在する
• レトラクト → 同型を少し弱めたもの
  • r.s = 1のみ成り立つとする
  • sがセクション(断面、切断(幾何学分野より))
  • rがレトラクション(撤回する、と言う)
  • 直感的には、sで埋めこんだものをrで復元できる
• 函手はレトラクトを保つ
• Setsにおけるレトラクト
  • セクションは単射
  • レトラクションは全射
  • レトラクションは集合を類別(classify)する
  • セクションは類別されたグループから元を選択している
  • 選択公理の圏論的な形式化となる
• s.rとはなんなのか
  • 全ての元を、セクションによって選択された元に移す → 射影と見なせる
  • 羃等な射になる
• rのセクションが存在 ⇔ 任意のfについてf = r.gとなるgが存在
  • ⇒ g = s.f とするとr . (s . f) = f
  • ← 自明
• プログラミングで言えば、射(プログラム)を分解できるか
  • 仕様→HTMLとDSL→HTMLがあったときに、DSL→HTMLにセクションがあれば仕様→DSLで常に表現できる
• 位相空間と連続写像の圏
  • S1(円)→D2(円盤)への埋め込みはレトラクションか
  • 連続写像では取り出せない
  • レトラクションは何かを含む、ことを言うには強すぎる条件
• fがレトラクションを持つ→rでfをキャンセルできる
  • monomorphism(モノ射、モニック射)
  • m.f=m.g ならば、f=gであること
• Setsのモノ射と単射は同値
  • fとgを1からの射として具体例をイメージするとわかりやすい
• epimorphism(エピ射)
  • f.e = g.e ならば f = gであること
• Setsでのエピ射は全射
• 同型射→モニックかつエピック
• fがレトラクションを持つ→fはモニック
• fがセクションを持つ→fはエピック
• モニックかつエピックでも、同型射とは限らない
  • Monの圏で、f:(N,+)→(Z,+)を考えると、同型射ではない
  • しかし、モニックかつエピック。g(-n)の移り先はg(n)で決まるため
  • fは0以上の部分の断面をとっているが、断面だけで等しいと言えてしまう(テキストのEx. 2.5)
• Cのモノ射はC^opのエピ射。
  • モノの性質を示せばエピの性質を示したことになる
  • 来週以降は双対性をどんどん使う
• 羃等射 → e.e=eなるe
  • (s. r).(s.r) = s.id.r = s.r (先程の証明)
  • 分裂羃等射(split idempotent) → 羃等射がセクションとレトラクションに分解できる
• プログラミングで言うと、連続して実行しても１度だけ実行しても同じ
  • 最適化や正規化に使える。冗長性(redundancy)を扱う文脈で使う
  • 並列アルゴリズムで、共有メモリに同じ命令列が並んだり。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 19:51

私のHom関手暗記法

math

圏論勉強会 第4回のHom関手で悲鳴が上がってたので補足してみる。

Hom関手がなんであるかは@9_tiesさんもおっしゃっていたようにひたすら手を動かすしかなくて、圏論を覚えたいのであればしっかりと復習する必要がある部分なのは間違いない。とは言え、効率のよい暗記法を編み出すことは大いに理解の助けにはなるだろう。

Hom関手は個人的には以下のように双関手として覚えている。まず、どこからどこの関手かをしっかり覚える。ドメイン側が反変になるのがポイントだ。

• Hom(-, -) : C^op × C → Sets *1

これがどういう関手かだが、ざっくりとC^op×Cの対象(A, B)をHom(A, B)へ、C^op×Cの射(f, g)をHom(f, g)へ移す、と覚えてしまってよい。後は、Hom(A, B)とHom(f, g)がなんなのかわかっていれば、Hom関手の定義をすぐ思い出すことができる。

Hom(A, B)については今日の勉強会で集中して説明があったので言及は必要ないだろう。AからBへ向かう射の集合である。

問題となるのはf:A1←A2, g:B1→B2の移り先であるHom(f, g)の方。まず、これはSetsの射なのでHom(A1, B1)→Hom(A2, B2)なる関数だ。そして、定義は以下のようになる。

• Hom(f, g) (h) = f;h;g

つまり、渡された関数を２つの射で単純に挟み込む、と覚えられる。;は合成.の反対を表す記号で、f;g = g.fで定義する。C言語を触ったことがあるプログラマであれば、 f(); h(); g(); のように順番に射をつなげることを表す表記と思えばよい。この定義で型があうことは、fが双対圏の射であることに気をつければ、hがHom(A1, B1)の要素であることから簡単に確かめられるだろう。

さて、今日の勉強会ではHom(X, -)のような関手が出てきたので、ここまで述べた暗記法で射f:A→Bの行き先を調べると Hom(X, f)となってしまって、暗記法のパターンにうまくあてはまらず使えないように思える。しかし、ちょっと自明な読み替えさえすれば、そんなことはない。

圏論ではよく、射id_AのことをAと対象と同じ記号で表記する。1つの対象について必ず一つの恒等射が存在するので、この記法で矛盾は生じない。Hom(X, f)のXがこの記法によって書かれていると思えば、先の暗記法が使える。XはC^opの射なので、X = id_X:X←Xと思える。

• Hom(X, f) (h) = Hom(id_X, f) (h) = id_X;h;f = f . h . id_X = f . h

つまり、Hom(X, f) = (f .) となり、勉強会と同じ結果となった。

反変関手 Hom(-, X)も同じように上述の暗記法で表現できる。まとめると、「Hom(f, g)というモノはfとgで引数の射hを挟み込む関数」ということさえ覚えていれば、Hom関手の定義について復元が十分可能であり、これを以てHom関手をマスターしたといっても過言ではない。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 23:54

今日は 圏論勉強会 第4回 の日です

レポート, math

圏論勉強会ではない方の圏論勉強会 第4回にまたやって来ました。資料とustreamは公開されています。

• ワークスアプリケーションズ社に入ると、リハーサルも見れてお得だよ！

第4回: 射で考える / 講師 @9_ties さん

• 様々な概念を圏論の言葉のみで述べる
• 今日もHaskellのセクション記法使う : (1 +)みたいの
• Hom集合
  • テキストの順番を無視してるけど、非常に重要な概念
  • 「今回は大変厳しい会になります」
• 単集合(unit set, singleton) : 要素がひとつの集合
  • 単集合1から集合Aへの関数は、Aの要素の数だけ
  • Aから1への関数は、1つ
  • 要素が2個の集合からAへの関数は、|A|^2
  • 集合Aから要素が2個への集合への関数は、Aの部分集合の数(2^|A|)だけある
• 関数空間: 集合AからBへのすべての関数の集合
  • 関数空間の構造(例えば要素がいくつあるか)は、AとBの構造から決まる
• Hom(A, B)、hom-set : AからBへ向かうすべての射の集合
  • 「集合」であることに注意
  • Aの要素と、Hom(1, A)の要素は同一視ができる A ≃ Hom(1, A)
  • 対象、射、合成だけでは、Aの要素(Aの内部)について述べられない
  • Hom(1, A)の要素は射なので、圏論の言葉で述べられる
  • Hom(2, A) ≃ A×A、Hom(A,2) ≃ P(A)
  • Hom(A, 1)の要素は1つだけ → 普遍性(来週やる内容)
• Q. Hom(1, A)が要素の個数を表すためには、1の構造(要素)について言及が必要では？
  • A. 1を圏論の言葉で定式化できる(そこに向かう射が1つのみ存在)
• Hom集合は、対象自体よりも豊かな構造をしている → Hom集合を調べるとよい
  • 集合 → Setsの対象。圏Cの議論をSetsへ移せる
• Sets(N, R) → すべての実数列 *2
• 半順序集合と単調関数からなる圏Posについて、Pos(N, R) → 単調増加実数列
• ベクトル空間と線形写像からなる圏VctのVct(V, R) → 双対ベクトル空間
  • Vが有限次元だと、双対ベクトル空間からVが復元できる
• Mon(N+, Z×) ≃ Z
  • f(1) = 2とすると、f(2) = f(1 + 1) = f(1) × f(1) = 4
  • 1の行き先だけでモノイド準同型fは決まってしまう
  • モノイドの圏から、コドメインの台集合が出てきた
• Hask(a, b) := a -> b に属する値
  • 前提: エラーが起こる関数は無視する(⊥は考えない)
  • f :: Integer -> () に属するのは f x = () しかない
  • Hom(A, 1)に要素が1つであることに対応
  • f :: () -> Integer に属するのは f () = n (nはInteger)
  • 型(Hom集合)を見ることで、実装の複雑さがわかる
• 普遍射: 〜〜を満たす射は一個 → 実装も1つに定まる
• ⊥を考えてみると、 g x = g x なる g :: Integer -> () が考えられる
  • ()は2点集合なので、Integerの部分集合の数だけ実装が作れてしまう
  • ⊥は再来週くらいに話す予定
• Hom(X, A)に構造を入れる
  • Aに構造があれば、Hom集合にも構造を入れられる
• Sets(X, M)でMがモノイドであれば、Sets(X, M)もモノイド
  • 各点ごと(pointwizeな)定義ができる → (f・g)(x) := f(x)・g(x)
• Aが半順序集合であればSets(X, A)も半順序集合
  • f <= g を f(x) <= g(x) で定義
• 関手圏 D^Cの構成は、Hom(C, D)にDの構造を入れることの一般化
  • 射をpointwiseに集めたものが自然変換
• Mがモノイドの時、Hom(X, M) ≃ M^X
  • Xは離散圏、Mはモノイド(対象が1つの圏)と見なす
  • M^X内の関手は1つ。自然変換はMの射の数だけ。
  • 関手圏の話は今後も繰り返すので、徐々に理解して欲しい
• Haskellでの例: instance Monoid b => Monoid (a -> b)
  • Int -> Intの関数がf, gがあれば、Sum . f <> Sum . gができるようになる
  • 「誰か役に立つ用途を考えてください」
• generalized element
  • Hom(X, A)はAの構造そのものと見なせる
  • 射a :: X → Aをgeneralized elementと呼ぶことができる
  • 言い換えると、Hom(X, A)を「Aのものの集合」と見なす立場、のこと
• point-free病 style
  • 射と合成のみでプログラムを書くこと
  • 言い換えると、圏論の言葉だけでプログラムを表現する
  • one = \() -> 1 とすると、要素1と射oneが一対一対応に
• 帰納法でこの概念を定義すると議論しやすくなる
  • zero = \() -> 0
  • succ = \n -> n + 1
  • succ . succ . succ . zero は 3を意味する
  • 少ない語彙でプログラムを表現できる
• Hom関手
  • 「ここからすごく重い話なので覚悟を」「圏論におけるボス的存在」
  • Hom(X, -) : C → Sets という関手。対象Aを集合Hom(X, A)へ移す
  • - には何か入るという意味
  • 射f : A → B は Hom(X, A) → Hom(X, B) なる関数にならなければならない
  • Hom(X, -)が関手であれば、普通の関手の議論ができて嬉しい
• 例: Hom(1, -) : Sets -> Sets を考えてみる
  • Hom(1, A) → Hom(1, B)を考えるのだけど・・・
  • f は Hom(1, f) (a) = f . a なる関数Hom(1, f)に移って欲しい
  • つまり、fを(f .)に移す
  • 1を任意の集合Xにしても、状況は同じと考えられる
• fを(f .)に移す話は第二回でやった
  • aをendomorphism (a ・)に移すのは、M(*, -) : M → Setsを考えたことになる
• 共変Hom関手 C(X, -)の定義
  • 対象Aを集合C(X, A)へ
  • 射fを関数C(X, f) = (f .) :: C(X, A) → C(X, B)へ
• 関手であることの証明
  • Hom(X, f.g)(h) = (f.g .)(h) = f.g.h
  • (Hom(X, f).Hom(X, g))(h) = Hom(X, f) (g . h) = f.g.h
  • 結合則は満たす。恒等射も同様
• 反変(contravariant)Hom関手 C(-, X)の定義
  • 対象AはC(A, X)に映る
  • 射f::A→BはC(f, X) = (. f) :: C(B, X) → C(A, X)
  • 射が逆になってるので関手ではない → 双対圏C^op→Setsの関手にはなっている
• ここを乗り越えれば圏論は簡単と思えるようになるはず
  • 次回は同型、モノ、エピ、普遍射など

ツイートする

Permalink | コメント(0) | トラックバック(1) | 19:49

Configuring Linux Mint on LaVie Z

インストールが終わったので設定メモ(随時更新)。

日本語化

ここ。

様々なアプリでEmacsキーバインディング

以下みたいな感じ。(ほんとはdconf Editor使ったけど)

$ sudo apt-get install dconf-tools
$ gsettings set org.mate.interface gtk-key-theme Emacs

Skypeで日本語変換(iBus)

~/.xprofile に以下を追加。

# https://wiki.archlinux.org/index.php/IBus
export GTK_IM_MODULE=ibus
export XMODIFIERS=@im=ibus
export QT_IM_MODULE=ibus
ibus-daemon -drx

特定ホストへのssh接続がめちゃくちゃ遅い

~/.ssh/config に以下(昔もやった記憶あるけどなんだっけこの設定)。

HOST *
    GSSAPIAuthentication no

haskell-platformインストール

必要なもの入れる。

$ sudo ln -s /usr/lib/x86_64-linux-gnu/libgmp.so.10.0.5 /usr/lib/libgmp.so.3
$ sudo apt-get install zlib1g-dev
$ sudo apt-get install freeglut3-dev

あとはghc(apt-getしたら古かったのでソースから入れた)とhaskell-platformをそれぞれ手順通りにビルド。

CPUが本気出してくれない

cpufreq-infoとかcpufreq-setとか。

(未解決)SkypeでEmacsキーバインディング

(未解決)*.localへhttp接続できない

ツイートする

Permalink | コメント(0) | トラックバック(0) | 23:16

Installing Linux Mint on LaVie Z

LZ750/LSを中古で買ってLinux Mintを突っ込んだメモ。

ちょっと前のエントリだけど、UEFI Secure Boot と Linux の微妙な関係を読めば今はちょうどブートローダー周りの過渡期にあるということが分かる。なので、普通に作業するとインストールディスクが起動しなかったりインストールしたOSが起動しなかったりといったことが起きる。起動までにやったことは以下。

UEFIに対応したLinuxを探す

LZ750/LSの場合はBIOSでLegacy BIOSブートにも変更できるのだが、そうするとWindows 8が立ち上がらなくなってしまう。対応したOSを探した方が良い。

Mintの場合はVersion 13(Maya)がLTS(Long term support release)なので始めこれを入れようとしたのだが、どうもうまくいかなくて*1、最終的にVersion 15を入れたらうまくいった。

BIOSの設定を弄る

LZ750/LSの場合は、Secure BOOTとFast BOOTをOFFにする必要がある。これでインストールCDが立ち上がるはず。

Boot-Repairでブート領域を直す

Installing Ubuntu Quickly and Easily via Trial and Errorの手順通りに頑張る。通常インストールしても立ち上がらないので、再度起動ディスクからBoot-Repairをインストールしてこれを使って直す感じ。

ここまでやって、Windows 8とLinux Mintのデュアルブート環境ができた。

ツイートする

Permalink | コメント(0) | トラックバック(1) | 14:46