Floating Log

# ブログ移転予定

PyDS を依存ライブラリーに合わせてアップデートしていくのが面倒になってしまったので、 Midnight Floating Thought というブログを Blogger で始めました。

ここの文章はどこに持っていこうか思案中なので、まだしばらく置かせてもらいます。

# 二部グラフ最大マッチング列挙

二部グラフ G=(U, V, E) を与えられたときに、その最大マッチングを列挙するプログラムを書いた (nxbimatch @ bitbucket.org)。 力ずくで探索するのに欲しかったのだが、意外にそういうプログラムが見当たらなかったからだ。

二部グラフ最大マッチングを一つ取り出すアルゴリズムはよく知られていて、Hopcroft-Karp のアルゴリズムが \(O(n^{5/2})\) 時間で走る(\(n\) は頂点数)。

列挙するアルゴリズムは Uno の一つ当たり \(O(n)\) 時間のものが知られているが、計算量を落とすための工夫がややこしい。 工夫を落とすと計算量としては一つ当たり \(O(m)\) 時間しか保証できない(\(m\) は辺数)。 が、自分が考えたい二部グラフが次数制限付き、つまり辺数が頂点数の定数倍以内なので、実質的にこれで \(O(n)\) 時間が達成できる。 ということでこのわりと素朴なアルゴリズムを実装した。

アルゴリズムは以下のようになる。

GEN_MAXIMUM_MATCHING(G):

1. G の最大マッチングを(Hopcroft-Karp で)一つ見つけ、M とする。
2. G の辺に M は U から V, それ以外は V から U と向きを付けた有向グラフを D とする。
3. GEN_MAXIMUM_MATCHING_ITER(D,M)

GEN_MAXIMUM_MATCHING_ITER(D,M):

1. D に辺がなければ終了。
2. D にサイクルがなければ、 GEN_MAXIMUM_MATCHING_ITER_PATH(D,M)
3. サイクルの一つを C とし、C に沿って M の辺を交換したマッチングを M' とし、M' を出力する。
4. C と M の共通辺の一つを e とする。
5. D から e および e と端点を共有する全ての辺を取り除いたグラフを D+ とし、GEN_MAXIMUM_MATCHING_ITER(D+,M)
6. D の辺を C に沿って反転し e を取り除いたグラフを D- とし、GEN_MAXIMUM_MATCHING_ITER(D-,M')

GEN_MAXIMUM_MATCHING_ITER_PATH(D,M):

1. D に辺がなければ終了。
2. D に長さ 2 の交替パスが存在しなければ終了。
3. 長さ 2 の交替パスの一つを P とし、M に含まれる辺を e, 含まれない辺を f とする。
4. M から e を取り除いて f を加えたものを M' とし、M' を出力する。
5. D から f を取り除いたグラフを D- とし、GEN_MAXIMUM_MATCHING_ITER_PATH(D-,M)
6. D から f および f と端点を共有する全ての辺を取り除いたグラフを D+ とし、GEN_MAXIMUM_MATCHING_ITER_PATH(D+,M')

素朴でない実装は、計算量を落とすために GEN_MAXIMUM_MATCHING_ITER の 3 でサイクルを"上手く"選択する。

アルゴリズムの中でいくつもの有向グラフを次々に作っているが、グラフの実装として採用した NetworkX ではコピーが非常に重たい操作なので、辺を抜いたり戻したりを繰り返す方が速い。 プログラムを読んで、一番直観的でない部分は多分ここ。

参考文献:

• Hopcroft & Karp "An \(n^{5/2}\) Algorithm for Maximum Matchings in Bipartite Graphs"
• Uno "Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs"

# Gentoo Prefix 翻訳

Gentoo Prefix の翻訳を進めた。 プロジェクトトップページ を更新し、 ブートストラップ手順 を新しく翻訳した(古い Mac 用ブートストラップ手順はお払い箱だ)。

ブートストラップは本当に手軽になった。 ブートストラップ・スクリプトをダウンロードして、chmod して走らせると、二つか三つ質問(インストール場所はどこがいいかとか)に答えれば自動でインストールしてくれる。

# 定数配分

総選挙も終わったが、また定数配分を巡って訴訟が起こされている。 (たとえば 衆院選無効求め提訴＝「1票の格差」で広島の弁護士―午後、全国一斉に とか)

ところで議員定数の配分自体を法で決める必要性はどこにあるんだろう。 全体の定数と選挙制度そのものと配分アルゴリズムを法で決めれば、あとは国勢調査ごとにアルゴリズムを実装したプログラムを動かして配分を決定するぐらい役人任せでいいのではないか。 アルゴリズムを決める際には、選挙区同士の格差何倍以内とか、選挙区に飛び地ができないようにするとか、そういった制約を事前に決めてしまう。 その方が簡単だと思うのだが。

# /etc/portage/package.*

ついったーでも書いたネタだけど。

emerge --autounmask-write=y とか app-portage/flaggie とか、/etc/potage/package.* のファイルを自動的に編集するものがある。 ところが /etc/potage/ には直接 package.accept_keywords のようなファイルを置く代わりに、package.accept_keywords というディレクトリを掘ってそこに適当な名前のファイルを置いても構わない、というルールになっている。 そのディレクトリ内のファイルが複数存在する場合に、上記のようなソフトウェアで書き換えられるファイルはどれか?

答: 辞書順で最後のファイル。

       --autounmask-write [ y | n ]
              If --autounmask is enabled, changes are written to config files,
              respecting CONFIG_PROTECT and --ask.  If the corresponding pack‐
              age.* is a file, the changes are appended to  it,  if  it  is  a
              directory,  changes  are  written  to the lexicographically last
              file. This way it is always ensured that the  new  changes  take
              precedence over existing changes.

emerge(1)

というわけで、たとえば overlay が提供する設定と自分でする設定とで分けておくときには自分用を zzz とかにしておけば安全、となる。

ちなみにこのネタの元は sage-on-gentoo の overlay で提供されている package.* 用のファイルを sage という名前でリンクしておいたら書き換えられそうになった、というところから始まっている。

# 青空文庫

iPhone で青空文庫の文章を数編読んでみた。 樋口一葉は元々一文が長いのに画面が狭いせいでぶつぎりになって大変読みにくい。 芥川龍之介は普通に読めた。

それとは全く別の次元で、ページを捲るアニメーションが鬱陶しいことが判った。 普通に本を読んでいるときでもページの最後の文字の残像を残しつつ次のページに進むような捲り方をしていたりするので、画面に再現するにはいっそカードを滑らせるようなアニメーションの方がいい。 最後の文字を見ながらページを捲れるから。

それから物理的な本には厚さ、ページ数、章、節などの様々なインデックスがあるが、その代替になるものが欠けていて、少し前のページを一瞬確認して続きに戻るというような作業ができない。 代わりにどんなインターフェイスを備えればいいのか、となると良い案は浮かばないのだが。

# なんのきこのき 25周年記念号

「上は 95 から下は 16 まで」
95 って俺のことかーっ!

というわけで最年長参加者で(ID順に掲載されているので)巻頭に作品が載ってる。 巻頭とは思わなかった…

何作かマンガが載っていて、それが何か時代の変化を感じさせる。 昔も「Foujita」は印象に残っているし、士郎正宗風のとかも載っていなかったわけではないけど、自分の年代にはほぼ小説/詩/イラストで構成されていたので。

(判る人にしか判らない文章になってしまったが、リンクを張っておくので察してください: ペン(先)なブログ)

# 読む速度・聞く速度

最近、英語のポッドキャストを聞いているときに思ったのだが、英語で話されているのを聞いて理解できる速度が文章を読める速度を越えている。 これはかなり衝撃的。 というのも、日本語では明らかに逆だから。 だからこそ何となく英語でも(日本語よりも遅いにしろ)読む方が速いと思い込んでいた。 でも、聞いて理解できると思う速度のわりと早口の英語に追い付く速度で(それが文章に起こしてあったとしても)読めないと認めざるを得ない。

特にオチは無いのだが、英語の教科書を読むより講義を聴く方が効率的なのかもしれないと思ったという話。

# COMA ゼミ

COMA ゼミ で喋ってきた。 グラフに付随する edge polytope の Ehrhart 多項式を代数的に計算しようという話。 去年前半に書いた論文の話で、自分が考えた部分はまだしも、前提知識というか背景知識というか先人が切り開いて整備してくれていた部分がだいぶあやふやになっていて難儀した。

# eix がブリンクして見づらい

eix-0.27.1 になって、出力がやたらブリンクするようになって、見づらいこと甚だしい。 などと文句を言っているバグがあるか探したけど無かった。 え、みんなこれ平気なの?

とりあえず、パッチを当ててみよう、と ebuild の中を覗くと src_prepare に epatch_user という行があった。 これはどこかにパッチを置くと勝手に当ててくれるやつだ、とまでは思い出したが、勿論詳細は思い出せないのでぐぐる。

• epatch_user; # FTW (M0RONIC CODER IN LOL WAY)
• 6.f. 非標準のpatchをあてる (Gentoo Linux x86 ハンドブック)

/etc/portage/patches/ だった(prefix の場合は当然前に EPREFIX が付いた場所)。

diff -ur src/eixTk.orig/ansicolor.cc src/eixTk/ansicolor.cc
--- src/eixTk.orig/ansicolor.cc	2012-09-19 06:11:02.000000000 +0900
+++ src/eixTk/ansicolor.cc	2012-10-05 00:00:00.000000000 +0900
@@ -147,7 +147,7 @@
 			static const unsigned int kLen = 10;
 			char buf[kLen];
 			if(iscol < 0) {
-				snprintf(buf, kLen, ";%d;5;%s", static_cast(col), curr.c_str());
+				snprintf(buf, kLen, ";%d;25;%s", static_cast(col), curr.c_str());
 			} else {
 				snprintf(buf, kLen, ";%d", static_cast(col));
 			}
diff -ur src/eixTk.orig/ansicolor_print.cc src/eixTk/ansicolor_print.cc
--- src/eixTk.orig/ansicolor_print.cc	2012-09-20 02:29:48.000000000 +0900
+++ src/eixTk/ansicolor_print.cc	2012-10-05 00:00:00.000000000 +0900
@@ -54,7 +54,7 @@
 void
 Display::output(CalcType color, CalcType fg, CalcType bg)
 {
-	printf("\x1B[%s38;5;%d;48;5;%dm%3d ",
+	printf("\x1B[%s38;25;%d;48;25;%dm%3d ",
 		(bold ? "1;" : ""),
 		static_cast(foreground ? color : fg),
 		static_cast(foreground ? bg : color),

このパッチを /etc/portage/patches/app-portage/eix-0.27.1/ に適当な名前で置いて emerge すればブリンクしなくなる。 (5 が blink, 25 が no-blink らしい)

# 列挙合宿

半年前にもあったが、水曜日から二泊三日、列挙合宿＠群馬大学伊香保研修所に参加してきた。 列挙に関係のありそうな何かを誰かが話してそれについて議論するという場。 今回は少し発表したのだが、おかげでいくつかフィードバックをもらえた。

ちょうど伊香保の祭りと時期が重なっていたので、ちょっと雨が止んでいる隙に見に行ってみた。 急な石段を御輿が上り下りするらしいのだが、時間帯が悪かったのかあまり動きのないときだった。 それはさておき、祭りの提灯に大きめ(幅が7〜8センチぐらいか)の蛾が入り込んでいるのが面白かった。 多分地元の人はいつものことなので気にも留めないし、まともな観光客もそんなものは見ないだろうけど、御輿なんかよりよほど物珍しい。

# PyConJP 2012 2日目

昨日に引き続き PyConJP。

PyPy の話、リクルーティングセッションなどで午前中を過ごし、午後は併設の Sphinx Conference(世界初らしい)。

# PyConJP 2012 1日目

PyConJP 2012 に参加している。 品川シーサイドの産業技術大学院大学。 法人としては首都大学東京になっていたがどういう関係なのかは知らない。 会場入りして受付をさっさとすませようと思ったら、印刷された名札が自分の分が無かった。 受付票を印刷しておいて良かった。

基調講演は、質疑応答が長すぎだろうと思った。

その後のセッションはずっと併設の Google App Engine の部屋にいた。 いろいろアップデートしないといけないものが溜まっているので(SDKのバージョン,pythonのバージョン,データストアなど)モチベーションを上げないと。

19:00から近くのホテルでパーティー。 立食なのであまり食べられず、結局後半は壁際の椅子に座っていろいろ話を聞いていた。

# 日本列島は太平洋に流れ出した

注意: これから書くものは裏付けのない思い付きなので、そこのところを誤解しないように。

前提知識は幾つかあるのだが、まず一つは千数百万年前ユーラシア大陸の縁にあった日本列島(の元になる岩塊)は、東北日本が反時計回りに西南日本が時計回りに回転し日本海が拡大して現在の日本列島ができたということ。 そのとき陸地として残らずに日本海に消えた部分もあり、さらに日本海には拡大した海底すら存在するという。 二つ目はプレートテクトニクスの説明に依れば、太平洋プレートが(大雑把に言って)ユーラシアプレートに沈み込んでいる場所に日本列島はあるということ。 このため、通常日本列島には東西圧縮の圧力が掛かっている。 三つ目、理由はよく判っていないが太平洋の西側には島弧が多いという事実。

一つ目の日本列島の動きを考えるに当たって、地図で現在の日本列島を眺めてみる。 そうすると、津軽海峡から日向灘までの海溝の線が大体綺麗な弧を成している(伊豆半島は後で考える)。 ほぼまっすぐ並んでいたものが弧を描くようになるような状況を考えると、粘り気のある液体がどろっと流れたような状況が思い起こされる。 いい加減に(時間のスケールと大きさのスケールを適当に調整すれば)陸地だって流体だ、と考えれば日本列島もユーラシア大陸の縁が太平洋に流れ出したように見えるだろう。

そこで問題になるのは、太平洋プレートの動きである。 押されている流体は流れ出さなかろう。 実際、長い目で見た平均も短いスパンでの観察も、太平洋はユーラシアの下に潜り込んで圧縮する力を掛けていると見ていいのだろう。 だが、それでも日本列島は流れ出した、と主張するには次のことが言えればいい。

「ユーラシア大陸を押す力が相対的に弱まったことがある」

相対的というのは太平洋側の押す力が弱まってもいいし、ユーラシアプレート側に引く動きがあってもいいという意味だが、ここで三つ目の事実が生きてくる。 太平洋プレートの西端の島弧たちが今ここで考えているようなメカニズムで生まれているのなら、太平洋プレートの押す力が弱まる傾向にあると言えるのではないだろうか。 「イベント」の発生原因までは見当が付かない。

ということで、結論めいたことを言っておくと、千数百万年前に太平洋プレートのとある場所でユーラシアを押す力が弱まるイベントが発生した。 それによって、日本海溝は大きく後退し、それを埋めるように日本列島はユーラシア大陸の縁から流れ出し、現在の位置まで移動した。

日本海溝が昔はもっと西にあった証拠としては、南側の延長もやはりそうであったと考えると、フィリピン海プレートはその時拡大している。 実際四国沖の海底である四国海盆は三千万年前から千数百万年前にかけて拡大した海底であるとされている。 その西側に当たる日向灘の辺りが日本列島の流れ出しの南の端となるわけだが、ここに九州パラオ海嶺という海底の山脈が伸びている。 これが現在の伊豆小笠原列島のように海溝の西側の火山列だったとすると、まあ現在の四国辺りが太平洋プレートの沈み込んでいた位置だろう。 伊豆小笠原列島は、したがってこのイベントの後にできた(伊豆半島はそれが西南日本に衝突してできているのでもっと新しい)。

東北地方の回転が続いているとして将来日本列島は日本海の方に折れ曲がる、という予測を見たこともあるが、多分、今度は伊豆を南端に東北日本が太平洋に流れ出して海に沈むのではないかと予測するのだが、どうだろうか。

# iPhone

携帯の機種を変更しようとしばらく前から思っていた。 今日ようやく実行に移した。

最初、ワンセグ無しでおサイフケータイ有りな機種を選ぼうと思っていたのだが、au でその条件を満たすのは1年前に出た G'z one だけだ。 G'z one はないだろう、ということでおサイフケータイも無しで。 そうして海外社製スマホから選ぶことになって、じゃあ iPhone でもいいんじゃない? そんな選択。