ToDo:
1時間くらいでさっくり読んだ。 さっくり本だと思う。 いい本だとは思うけど、まぁ初心者向けすぎる感は。 まぁそれでもいくつかああこんなコマンドあったんだってのがあったけど。
というわけで欲しいもの @gdb
(00:25)
どっちもありそうなもんなんだけどね…
(22:48)
どれも絶対あると確信してるんだが。
(22:53)
http://twitter.com/alohakun/status/5506693038
これで思い出して前に啓蒙書を貸してもらって読んだけど、証明をさっぱり忘れつつあるので記憶を再構成しておこうと思う。うぃっきぺたんを参考にしつつ俺メモ…
http://en.wikipedia.org/wiki/Four_color_theorem
まず一つの点から4本以上線がのびるような頂点があるグラフは考えなくてもいい。
×
があったら
v | ^
に変換しちゃえば3本のびるグラフに還元できるから。
2本しかのびてない頂点はつまり、単純に領域数増やしに関わってのは無視できて、孤立した円みたいなヤツも自明に関係なくて、全体を囲むやつとかも外っかわの色のせいで4色じゃ塗れなくなっているとすると、中もどうせ4色で塗れませんよね〜ということで忘れていい。でまぁこのケース忘れることから、隣国が1つしか無い国っていうのもいないとしていい。
次はオイラーの多面体公式
http://ja.wikipedia.org/wiki/%E5%A4%9A%E9%9D%A2%E4%BD%93
頂点の数(V) - 辺の数(E) + 面の数(F) = 2
を使う。なんかしらんけど色をぬる領域が頂点として、隣国との国境が辺、でまぁ地図上の頂点が面として考えている。ややこしいな…
3本線が生えてる頂点しか無いことから、 2E = 3F 。 6V - 6E + 6F = 12 につっこむと、
6V - 2E = 12
頂点から出てる線の数を i とした時に、そういう頂点の数を vi とすると、
6Σvi - Σi*vi = Σ(6-i)*vi = 12
ということは i<6 のものが最低一個無いと左辺が正にならないので、最低一つは隣国の数が5以下の国があるわけだ。そこを攻める。
攻める前に、背理法の準備。ここに4色で塗れない地図があったとして、その中で最小の国数となる地図 G を考える。つまり G から国を 1 つ取り除いたら4色で塗れるようになってしまうようなもの。
さて G は隣国2つしかない国を持てない。その隣国2つの国を取り除いて隣国同士をくっつけた地図も依然として4色で塗ることは不可能で、 G が最小という仮定を壊す。
G は隣国3つしか無い国も持てない。これも隣国3つを取り除いて頂点にしちゃった地図も依然として4色彩色不可能だから。
隣国4つもちょっと賢い理由で無理。隣国4つがそれぞれ全部違う色でかつ自分の色とも違ったとして、赤青黄緑の順でぐるりとまわっているのが隣国で自分が紫とかする。赤の国から出発して、黄→赤→黄→赤→…と交互にたどっていけるパスがあるはず。無いなら黄は赤でいいことになってしまう(はしょりすぎだが)。同じ理由で青と緑を交互にたどるパスもある。さてそれらはどうやって交差してるのでしょうかー無理ー。ということで隣国4つも無理。
5色定理はこの論法で隣国5つのケースも潰せるので、証明できる。ここまではそんなにむつかしくないというか、とても綺麗な論法だったわけだ。
で、5つがむずい。というかその、「隣国5つの国が1つはいるよね〜」という条件だけからではどう考えても矛盾が導けなかったので、「隣国 X の国の回りに隣国 Y の国があるようなパターンか、ほげほげなパターンか、あるいはふがふがなパターンか…のどれかは絶対あるよね〜」とかそんな感じで、パターンをどんどん増やしていって、一個一個潰していく感じでやっていった。でまぁ証明難しげなパターンがあったらそのパターンの中でまたパターン増やして…みたいなことをやって、片っ端からこんぴゅーた様で証明した、っていうような感じだったらしい。
でまぁそいうパターンが証明時で2000近くとかあったんだから、泥臭いことこの上ないという。
最後の部分なんかわかりやすいパターンの例とか本に載ってた気がする。今度立ち読みして再構成しよう…
(10:09)
TODO
(16:38)
をやろうとしたけどうまくいかんな…
とりあえず background.html にフラッシュ置いたら SEGV した :( まぁ置けないのはいいのかもしれんが SEGV はどうなんだと思ったので 報告するか今度眺めておこうと思う。
次に content script 側でページにフラッシュを つっこむ実装にしてみようとやってみた。 でもどうもうまくいかない。 なんでだろ。
(16:42)
おもしろかった。
BulletSML を聞いていて、 何か jsdmkun 作ってる時にコンパイルするアプローチだと アレが難しいよなーと思っていた、アレは何だっただろう… とひたすら思い出していたけど思い出せなかった。 その後一瞬で思い出したんだが単に継続だ。 BulletSML では普通に継続使ってるから問題ないのであった。
(17:20)
んで Shibuya.lisp 終わってから行ったら遅れてた。
というかそもそも今思い出したけど Shibuya.lisp 自体存在をきっちり忘れていて、 というか登録した記憶がきっちり無くて、 masa_edw さんの twitter を見て 「あー今日 Shibuya.lisp かー俺も行きたかったなぁ」 と思ってサイト見たら何か登録されていて 焦って飛んでいったとかいうそんなこんな。
で chrome の方はまぁなんかみんなよく知ってるなぁとかそんなこんな。 extension はやっぱこうまだ API 全然足りないよなぁ。
(17:29)
はまぁ悪くはなかったんだけど、 コードが無闇に長いしもう毎回クッキー読み書きする実装でいいんじゃね? と当たり前のことを思ったのでそいう実装を作ってみた。
http://github.com/shinh/w3m/commit/abcedbb2d7222f97157221cf52b00b3b600c6431
これでしばらく使ってみて良さげなら w3mcooksrv はもう捨てよう。
(20:03)
なんだ JS だけでできるんじゃないか… Linux でもすごくよく動いてるので、 もう chrome linux の omnibox とか忘れていい。
TODO がちまちまと消えていってうれしい
(22:25)
死んだみたいだ。
なんか常にオレンジ色のバッテリ表示が点滅しているし、 ためしにケーブル抜いてみたら死んだ。
別に困りはしないんだけど UPS つき PC として買ってるので なんか損した気がするね…
あとこの PC もファンがさわがしい…
(04:16)
なんか普通に javascript: とかは w3m に変更無しで 動いたりするようになったわけなんだけど、 https 困ったなーと思った。 普通の https プロキシみたいな動きじゃなくて、 https の URL を HTTP で拾いに行くような挙動を ブラウザがしてくれないと色々めんどうくさい気がする。
(04:20)
なんで無いのー
そしてこのパッチがどうやって当時動いてたのか、さっぱりわからない…
http://www.sic.med.tohoku.ac.jp/~satodai/w3m-dev/200010.month/1195.html
さっぱりわからんから自分のカンでやるか…
(12:35)
http://github.com/shinh/w3m/commit/c64a257e6bee7bf8b27f6f21892447846b980b02
実装した。 本当に動くかなんか知らない。
(14:04)
w3m で JS を動かす計画の一環として、 とりあえず休日にごろごろしながら WebKit API 使った HTTP プロキシとかを作っていた。 Gtk+ port の WebKit API (WebKit は環境ごとに API が違う) はまぁなんかあまりなにもできなさそうに見えて実は結構色々できて、 普通の GET くらいはストレスなく動く感じになった。
onload までのタイミングで実行された JS はちゃんと反映されているはず。 画像とか iframe を読みに行くのとか、 layout を走らせようとするのは殺せたと思う。
Gtk+ port は、なんかヘッダだけじゃダメで、 cpp 見ないと signal の仕様とかよーわからんのがキツかった。
でもなんか request のヘッダで 書き換えれないものがあるように思うのがキツい。 wireshark で調べるに、 Cookie が通らない。 Cookie は WebKit 側で処理しちゃってもらってもいいかもだけど、 Accept-Encoding とかも書き変わっちゃって そのへん後々困るかもなぁという感じ。
書き変わってるのは、
とこの2つだけか。
あとまぁそのへん気付いたのは ログイン系の挙動がおかしすぎるからなんだけど、 ログインに関しては cookie を WebKit が処理してくれてれば 勝手にうまいこと行ってくれてもいいはずで、 このへんよくわからんちん。
選択肢としては、
などがある気がする。
クッキーはまぁ SoupCookieJar とかに自分でつっこむのもいいし、 WebKit に任せられるならそれもいい気がする。 Accept-Encoding が落ちるのは微妙だねえっていうか これいじってるのはなんでなんだ。 Gtk+ ポートがアホだからとかそんなだったら悲しいから調べる価値はありそう。 まぁ見てる感じ Qt の方が熱心に開発されてはいるんだよな。
HTML に対して loader 使うのをやめるのは悲しいけど、 まぁ実害はそんなにないかもしれない。 あーでも圧縮の展開とかは soup は面倒見てくれない感じかな。 だとするとちょいめんどいか。
プロキシをやめるのはどうせ JS の処理は proxy としてだけではうまいこといかんので、 最終形態としては悪くはないんだけど、 プロキシにしておくと wget とかからも使えていいので なるべくなら避けたい。
Gtk+ やめて Qt に行くのはまぁ十分な API があるならアリ。 ただ調べるのめんどうという理由だけで避けれるなら避けたい。 あと Chromium port の WebKit API の が upstream されたら それでも良さそうな気はする。 user script とかありそうなのは良い。
あともっともっと些細な問題として user stylesheet 読めないってのがある。 layout tests controller とか読む感じでは そもそもサポートされてなさそうな感じがするんだけど、 API はあるんだよな。 Qt もこのへんは無いように見えるのがにんとも。
(16:48)
SVNリポジトリ変えたというかマシンぶっとんで変わったから、 既にチェックアウトされてるものを切り替えるスクリプトを書こうと思って、 適当に ~/bin/svnswitch とかいうファイルを作ろうと開いたら、 既に望みのものがそこにあった。 名前まで一致するのはなんともですね。
それはそうと github はパッチとか簡単に表示されるのはまぁいいんだけど、 git って一人で使うには不便だよなぁと思う。 なんていうか master だけあればいいわけで、 git push/pull でわざわざ sync するのが割とめんどい。 まぁなんかスクリプト書くかな。
(06:25)
共有っていうか今のセッションの ヒストリは別に持ってて欲しいんだけど、 保存は常に見た順でしておいて欲しいよね。
クッキーは w3mcooksrv で処理してる今となっては 一番 w3m のうざい部分の一つになってたんだけど、 まぁ別に各プロセスで同期とかして欲しくもないので、 こっちは特にサーバ化とかするまでもないのであった。
http://github.com/shinh/w3m/commit/53a5adaecee42d46efb5b458defe0f1f03ccbeaf
ていうかクッキーも必要なタイミングで毎回読むっていうのも まぁありっちゃありなんだよなぁ。
(15:15)
i@um ~/wrk/sevil> ./dump Sat Oct 31 17:00:08 um dump[13353] <Error>: kCGErrorInvalidOperation: _CGSFindSharedWindow: WID 40 Sat Oct 31 17:00:08 um dump[13353] <Error>: kCGErrorFailure: Set a breakpoint @ CGErrorBreakpoint() to catch errors as they are logged. Screen size: (1280, 800)
CGSValue で string 受けるのが CFString になったのかなぁ という感じだったので変えてみたらそれでもなんかエラーが。
(17:01)
仕事が楽しいとかは本気で本当によくないと思っているので、 本当に本気でこれはいけないと思う。
しかしそろそろ本気で英語なんとかならんもんかなぁとか 思うようになってきた。 もちろん努力をする気とか自分のお金を使う気とかは 依然として全くないのだけど、 こう、ラクしてというか何もせずに、 ある日突然うまくなっているべきだと思う。
このままではいけない。 こんな本質的でない問題はいつのまにか勝手に 乗り越えられているべき問題なのである。 例えばアメリカで日本語全面採用とか。 そういう問題意識ばかりがつのっていく。
(16:50)
x86 では "A" とかで受けてやればそれだけでいいわけなんだけど、 x86-64 では色々大変みたいだ。
http://d.hatena.ne.jp/rero/20071208/p1
よくわからんけどポータブルな rdtsc としては こんなかんじでいいのかね。
http://github.com/shinh/test/blob/2a7a2bf7dbffae14851725154e187a636bb269ff/rdtsc.c
(17:05)
http://d.hatena.ne.jp/camlspotter/20091026/1256567062
http://twitter.com/shinh/status/5194338611
http://twitter.com/shinh/status/5194346481
さて読もう!
08049860 <camlDame_rev__dame_rev_58>: 8049860: 83 ec 04 sub $0x4,%esp 8049863: 89 c1 mov %eax,%ecx # なんか知らんが第一引数は eax なのかね… 8049865: 83 f9 01 cmp $0x1,%ecx # なんか知らんが nil の内部表現は 1 なのかね… 8049868: 74 46 je 80498b0 <camlDame_rev__dame_rev_58+0x50> 804986a: a1 40 b5 05 08 mov 0x805b540,%eax # 0805b540 B caml_young_ptr なんだこれは! とりあえず GC 関係ぽい。 young って世代別とかそいうやつかいな 804986f: 83 e8 0c sub $0xc,%eax # なんか知らんが値減らして保存しなおしてるみたいだ! 8049872: a3 40 b5 05 08 mov %eax,0x805b540 8049877: 3b 05 44 b5 05 08 cmp 0x805b544,%eax # 0805b544 B caml_young_limit 804987d: 72 3a jb 80498b9 <camlDame_rev__dame_rev_58+0x59> # これの行き先が GC なので、まぁ GC 関係 804987f: 8d 58 04 lea 0x4(%eax),%ebx # ここから本番。なんかたぶんリストの確保が終わってて ebx に入るのですよ、たぶん 8049882: 89 1c 24 mov %ebx,(%esp) # たぶんこれがいま ebx=[] 8049885: c7 43 fc 00 08 00 00 movl $0x800,-0x4(%ebx) # (%eax) じゃないのか悩むが謎の定数を元の eax のところに入れてて、うーんこれはなんだろう 804988c: 8b 01 mov (%ecx),%eax # x を eax に入れた 804988e: 89 03 mov %eax,(%ebx) # ebx=[] の car を [x] にした 8049890: c7 43 04 01 00 00 00 movl $0x1,0x4(%ebx) # ebx=[] の cdr に 1 (やっぱ nil やね) をつっこむ 8049897: 8b 41 04 mov 0x4(%ecx),%eax # xs を eax に入れて 804989a: e8 c1 ff ff ff call 8049860 <camlDame_rev__dame_rev_58> # 再帰呼び出し 804989f: 8b 1c 24 mov (%esp),%ebx # スタックに置いておいた [x] を持ってきた 80498a2: 83 c4 04 add $0x4,%esp 80498a5: e9 16 08 00 00 jmp 804a0c0 <camlPervasives__$40_167> # 0x40 は '@' なのでまぁそういうことだろう 80498aa: 8d b6 00 00 00 00 lea 0x0(%esi),%esi # 何これここ来ることあるんか!!! → とりあえず gdb で break しかけても止まらない。 80498b0: b8 01 00 00 00 mov $0x1,%eax 80498b5: 83 c4 04 add $0x4,%esp 80498b8: c3 ret 80498b9: e8 3a d7 00 00 call 8056ff8 <caml_call_gc> 80498be: eb aa jmp 804986a <camlDame_rev__dame_rev_58+0xa>
わかったことは引数は eax, ebx と入れて渡す呼び出し規約だということだった。 あと GC まわりのコードはこれだけではよくわからん。 てか [x] のために allocate ぽいことしちゃうのはちょっといけてないなー
さて次は @ を読もう!
0804a0c0 <camlPervasives__$40_167>: 804a0c0: 83 ec 04 sub $0x4,%esp 804a0c3: 83 f8 01 cmp $0x1,%eax # 第一引数がカラだったらさっさと終わろうね☆ 804a0c6: 74 48 je 804a110 <camlPervasives__$40_167+0x50> 804a0c8: 8b 50 04 mov 0x4(%eax),%edx # 第一引数の cdr 804a0cb: 8b 08 mov (%eax),%ecx # 第一引数の car 804a0cd: 89 0c 24 mov %ecx,(%esp) # car の方は保存しておいて 804a0d0: 89 d0 mov %edx,%eax # cdr の方を次の関数 call の第一引数にして 804a0d2: e8 e9 ff ff ff call 804a0c0 <camlPervasives__$40_167> # 再帰! (ebx=第二引数は触ってないのでそのまま) 804a0d7: 89 c1 mov %eax,%ecx # 帰ってきたリストを ecx に。この時点で第二引数はくっついてるはず 804a0d9: a1 40 b5 05 08 mov 0x805b540,%eax # また GC ゾ〜ン 804a0de: 83 e8 0c sub $0xc,%eax 804a0e1: a3 40 b5 05 08 mov %eax,0x805b540 804a0e6: 3b 05 44 b5 05 08 cmp 0x805b544,%eax 804a0ec: 72 28 jb 804a116 <camlPervasives__$40_167+0x56> 804a0ee: 8d 40 04 lea 0x4(%eax),%eax # まぁこれで eax にカラリストが入ったんだろう 804a0f1: c7 40 fc 00 08 00 00 movl $0x800,-0x4(%eax) 804a0f8: 8b 1c 24 mov (%esp),%ebx # 保存しておいた car の方を 804a0fb: 89 18 mov %ebx,(%eax) # 確保したカラリストの car に入れるよ 804a0fd: 89 48 04 mov %ecx,0x4(%eax) # cdr は帰ってきた値ね 804a100: 83 c4 04 add $0x4,%esp 804a103: c3 ret 804a104: 8d b6 00 00 00 00 lea 0x0(%esi),%esi # また使われてなさそうなコードがあるね… 804a10a: 8d bf 00 00 00 00 lea 0x0(%edi),%edi # また使われてなさそうなコードがあるね… 804a110: 89 d8 mov %ebx,%eax # ここは第一引数がカラリストだった場合なので、単に第二引数をかえせば良い! 804a112: 83 c4 04 add $0x4,%esp 804a115: c3 ret 804a116: e8 dd ce 00 00 call 8056ff8 <caml_call_gc> 804a11b: eb bc jmp 804a0d9 <camlPervasives__$40_167+0x19> 804a11d: 8d 76 00 lea 0x0(%esi),%esi
ええとこれは… 正直どうしてこうなった…と思ってしまうな… これが関数型かー
何が言いたいかというとなんで list を append するのに allocation が大量発生してるんだよ! っていう
でまぁどう見ても O(n^2) でしかないので、 まぁ GC でこんだけ遅くなるのかなぁ。
(15:31)
http://risky-safety.org/~zinnia/d/2009/10/#20091021-t0-h1-p3
個人的には topcoder とかならまだゴルフの方を真剣にオススメするのですが。 問題がまだ現実世界に近いという意味で。
id:sumim さんがやっておられるように、 ブログとかで話題になってる問題を解いてみるってのは結構いいなぁと感じます。 あとたまに wikipedia とかにのってるアルゴリズムを 実際に書いてみるとかするんですが、そいうのもいい気がしています。 こないだ mutex 書いてたのはまさにそんな感じ。
http://d.hatena.ne.jp/shinichiro_h/20091018#1255797222
(01:27)
本当は瞬間移動の指輪と瞬間移動制御の指輪も欲しいね。
(01:35)
| 前 | 2025年 7月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
_ shinh [おしえてもらった - stash & stash clear => これは reset やろアホと前も聞いた気がす..]
_ shinh [さらにおしえてもらった - あとから track => git branch -f --track master ..]