ToDo:
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
via http://research.swtch.com/qsort
「quicksort の最悪計算量は O(n^2) ですよ、でも pivot のとりかたとかでだいたい大丈夫にすることはできますよ」、ってのはよく言われる話だけど、実際 quicksort が n^2 になるようなデータを作る方法を考えてみた、っていう話。
作りかたがちょっと面白くて、 qsort を実際に呼んで、 callback で呼ばれる比較関数で小さい数字から少しずつデータを確定させていく、みたいな。
このコード、 mac とか linux で実行してみると n^2 にならない。 russ cox によると glibc の qsort は実際は merge sort らしいからそういうもんらしい。 mac もそういう感じなのかな。 N が小さい時はわりと n^2 ぽい挙動してるけど…
ぱっとコード見た感じ、 2*(log(N)-1) 回越えて再帰する時は heapsort する、みたいなコードに見えるかな。まーなんとなくわからんでもないし、あとまぁそれならそういう挙動するかな的な。
自分で適当に qsort 書いてみて antiqsort に渡してみたら、モロに O(n^2) になった。おもしろい。 qsort は C だとっていうか余計なメモリ使わない実装は結構むずかしいと思ってて、昔書いた時はすっと書けなかった気がするけど、今回はそんなに苦労しなかった。全然テストしてないからあってるかは知らんけど。
void myqsort(void* base, size_t nel, size_t width,
int (*compar)(const void*, const void*)) {
char* pivot = (char*)base;
char* b = pivot + width;
char* e = (char*)base + nel * width;
char* buf = (char*)malloc(width);
size_t lc = 0;
while (b < e) {
int r = compar(pivot, b);
if (r >= 0) {
b += width;
lc++;
} else {
e -= width;
memcpy(buf, b, width);
memcpy(b, e, width);
memcpy(e, buf, width);
}
}
if (lc) {
memcpy(buf, b - width, width);
memcpy(b - width, pivot, width);
memcpy(pivot, buf, width);
myqsort(pivot, lc, width, compar);
}
free(buf);
if (nel - 1 - lc)
myqsort(b, nel - 1 - lc, width, compar);
}
(16:59)
こういうマップを妄想してた。
###L### # \\\ # # # # # # # #* # # * * # # * # # # # # #* # # # # # # *# # * * # # * # # # # R # #######
僕の AI に解かせてみたところ、なるほどこのロボット頭で岩止めれるのか…と気付いた。
(01:56)
2時に寝て8時に起きてしんどすぎると二度寝して、11時くらいと12時くらいと1時くらいと2時くらいでそれを繰り返して、明日からアメリカだから休もう…とメール書いた。で、また3時くらいでそれをやって、その時飯を喰って、あと2回そういう繰り返しをして今に至るがまだ体だるい…
とりあえずそろそろ準備しないとな…
(19:41)
http://herpolhode.com/rob/utah2000.pdf
読んだ。まーそうなんだろなっていう。よくわかってないけど CS とか半分くらいはそろそろ大学でやることじゃないんじゃないかな…てのは割とずっと思ってることだけど。
計算量とか数学系は続けりゃいいと思うし、科学技術計算のための大型計算機とかもやりゃいいと思う。ただシステムプログラミングとかは、もう企業にやらせりゃいいんじゃないかな…ていう感はある。12年前の rob pike の苦言を見て、そんな感じなんだろうなあと今思うてことは、たぶんあんま良くなってないんだろうな…
(21:43)
kinaba さんの動画ぼんやり見ててソルバというかシミュレータのバグに気付いた。
トランポリンの入口入った時に同じ出口に向かうやつ全部消えるってやつ、消さなくても次入ったら消える感じでいいかなーと思ってたけど、上に乗ってた石は動きだすべきなんだね…くそう完全に正しいの作れたかなーと思ってたのにがっかりだ。
これくらいはまぁ大変だけど実装できた気がするな。つっても1時間くらいはかかるだろうから、きわどいところだなー。
C++ より次元が多くてすばらしく見える Befunge 欠点は変更がしづらいことで、基本一度書いたコードの位置を移動させようとすると、多大な苦労を強いられることになる。特にメモリレイアウトとか変えようとすると死ぬので、最初にだいたいこういう感じで書こう…と決めた通りになるべく進めたい。
読みにくいのも問題といえば問題で、あーあそこバグってるなーと思っても、実際バグってるコードを探すのが結構大変。たった100行程度のコードなのに! 普通はそういうのをふせぐためにコメントを書いたりすると良いわけだけど、コメントがこれまた書きづらい。というのは、コメントに副作用があるのが問題で、ここは絶対に実行されてない、と確信を持つのに時間がかかるし、将来的にここを通したくなることは無い、って言える場所が少ない。例えば、
> このへんからメインループがはじまる
>
| ゴール判定のためにラムダの残り数を数えるコードがこのへんにある
goal->@
^ 1ターンが終わると端を通って戻る
みたいなコードがあって、上の例だと親切のつもりで書いた goal ってコメントが、 g は Befunge では実行できる命令なので、特にエラーも出ず、スタックの長さが突然変わることになる。この例みたいな重要なコードパスならまーすぐ気付くだろうけど、あんまり通らないとことか、あるいは今トランポリンを集中工事してるんだ、って時に洪水のとこがバグったりすると、すごい遅れて気付くことになる。というわけで今集中してるとこ以外はいじらないのが得策で、コメントもほとんど書けない感じだった。一応、未実装のとこは付近に空間ができがちなんで、 @ で潰して近くに文字列置いたりはしてたけど。
うーむ残念だ。他にもバグあったりするかなぁ…
(00:43)
README が文章も typo も無茶苦茶ですがな。英語がうんぬん以前に論理的につながって無い系。
こう疲れてるんで、 README は後から提出できる感じにしてほしいよね…
(01:21)
3日間聞いてたのは、ウテナ→ミク→ぷよm@s という感じだった。基本的になんかやかましいのが鳴ってると集中できるんだけど、ウテナとかミクずっとはさすがにうざい。ていうかミクはわりとすぐにつらくなってやめた。
ぷよm@s は色んな音が流れつつ、たまにやかましいのが流れるのが僕的には作業向けなんだけど、丈が短いからすぐループしはじめる。別な part に移動したらいいんだけど、今回は細心の注意が必要すぎる作業をしてたので、結果としてなんかずっと同じ曲聞いてた気がする…
それで思い出したんだけど、 part27 のあずささんの連鎖がいつ見てもすごいと思い出した。コレの11手目。
http://ips.karou.jp/simu/pv.html?_0uk8iiSkCukaiucgkwkIcgcKMKW-S1
via http://unknown72.seesaa.net/article/235037702.html
フツーに考えるとこういう12手発火5連になる気がする。作中で指摘されてたのは4+5の4ダブで、初代だとそっちの方がいいんだろうけど。
http://ips.karou.jp/simu/pe.html?_0uk8iiSkCukaiucgkwkIcIcaMKW-S1
(01:50)
いつもメモり忘れるけど、このモードを使うと Befunge のコードが書きやすくなる。
しかし自分ではっつけた結果をよく見ると、 contest2.map で C++ コードが befunge のコードに負けてやがってうける。
(21:56)
最近思うことは飽和連鎖量が足りないなっていう。で、ぐぐってたら最初に出てきたやつ
http://www.geocities.co.jp/Playtown-Domino/6390/Bulletin/lecture/lecture6.html
これが、モロにGTR系なのに
C B CC BAA BAC
とかいうキツい形が最初に思いついてダメだなぁとか思った。ちょっとゆっくり一手一手考えるみたいなことした方がいいのかな…
あと初手で
BA BBA AAC
とかできた後に AB AC AD どれが来てもわりと悩むことが多い気がするなぁと思った。ネクスト考えないと、どの場合も A を5個消ししちゃうのが良いのかな… AC AD は2列目に立てるのもいいと思うんだけど。
(01:02)
A BC CCA BACD BBACDC AACCDC
の ABAB が
A AB BCB CCA BACD BBACDC AACCDC
とかになりがち。
BAB CAB CCA BACD BBACDC AACCDC
なら全然よいということを考えると、左端のフタが一つってのがイマイチ系なのかな…
(01:07)
i@u6 0:46 [master]
> cat non_static_data_init.cc
struct S {
int i = 42;
};
i@u6 0:46 [master]
> g++ -std=c++0x non_static_data_init.cc
non_static_data_init.cc:2:11: 残念ですが未実装です: non-static data member initializers
non_static_data_init.cc:2:11: エラー: ISO C++ forbids in-class initialization of non-const static member ‘i’
zsh: exit 1 g++ -std=c++0x non_static_data_init.cc
そ、そうですか…
(00:47)
http://blog.64p.org/entry/2012/07/11/224008
via https://plus.google.com/102550604876259086885/posts/AnEoGQexUcG
scons なんて始まってもいねえよ! ってのが僕の感覚だなあ、たいしてしらないけど、必要じゃない機能ばっか充実しているという mukai さんのイメージに賛成する感じ。
scons に関していつも言ってる悪口に、ファイルが本当に変更された時にだけ依存関係をビルドしなおしてくれるという便利な機能がある。
これはどういうことかというと、 hello.c から hello.o と hello を作ったあと、 hello.c を touch してもビルドしなおしてくれないと。 stdio.h とか書きかえた時とか、そういう特殊なことしてるからわざわざ touch してるわけで、なんか余計なお世話としか言えない。で、しょうがないなと hello.c の末尾に空行を一行足したりすると、 hello.o はリビルドされるけど hello はされない。何故なら hello.o のチェックサムは変わってないから。
そしてその余計なお節介にしか思えない機能が自慢気に書いてあるあたり、なんかすくなくとも僕の感覚とはずれてるなあ…としか思えない。
http://www.scons.org/doc/0.98.5/HTML/scons-user/c779.html
で、まーそういう余計なお節介があると知ると、あの遅さがそういう余計なお節介のせいではないか…とか思われて、どうしたもんかと思ってしまう。
ただ、一応今ぐぐってみると、色々速くする方法はあるみたいだ…ただ make 系ツールのデフォルトの挙動を遅いものにするセンスからして、このへん頑張っても make 程度にも速くならないんじゃないかな…とか思ってしまうよね…
http://www.scons.org/wiki/GoFastButton
あといつも言ってることだけど、ビルドシステムってのは、こうなんか、人々に再生産させたくなるようなオーラがただよってるらしく、なんか許しがたい数既にあるので、 make にムカついて僕の考えた無敵のビルドシステムを作ろうとしてる人はコレを見て考えなおしてほしい…
http://en.wikipedia.org/wiki/List_of_build_automation_software
mukai さんも書いてる通り、 automake/cmake/gyp あたりは一つ上のレイヤにいるので、そのへんはまぁ OK 。 autoconf のレイヤは特に代替があまり作られてない気がするけど、まぁ Unix 乱立がおさまりすぎて、ああいうのの時代は終わりつつあるのかもな…
ところで autotools はひとくくりにして、嫌ってる人が多い気がするけど、僕的には autoconf は必要で automake は死んでもいい派。 autoconf 無しだと、わりと色々詰んでると思うんだけどな… cmake は autoconf 的なことを少しだけしてくれた気がしたけど、どうだっけ…
libtool は実際問題正しくライブラリ用の make 書ける気がしないから、本質的じゃないけどあれも必要かな…とか言ってると automake 無しで libtool 使うの大変とかで必要になってきて、こまるわけだ…一度 automake 抜きで autoconf/libtoolize 使うとか練習してみるのも良いかもしれない…
(00:57)
sucks シリーズ、 JS はあまりよく知らないのにすごいのがいっぱいあるから書いてなかったけど、ちょっと書いてみた。
http://shinh.skr.jp/h/?JSSucks
(01:23)
の話を聞いて、 GCC でコンパイルしたコンパイラは大丈夫で、そのコンパイラでコンパイルしたやつはまだ大丈夫だけど、次でクラッシュするバグがあった、みたいな話をしていた。
で、 TCC であそんでたとき似たようなのがふたつあったなーと思ってたんだけど、片方しか思い出せない。そっちの片方はまだ2世代目が3世代目をビルドする時のやつで、こんな感じだったと思う。
INT_MIN 以下の値のリテラルの扱いがバグってて、なんかデカい値になっちゃう。 GCC はそんなバグ持ってないから1世代目は大丈夫。2世代目はそのバグを持った1世代目コンパイラでコンパイルされているので、コード中に一箇所だけある INT_MIN 以下の値が出てくるぶぶんがおかしくなってる。そのデカい数字が何でできてるかっていうと、 32bit 相対 call で届くかをチェックする部分で、届かないから trampoline 作らんといかんのに作らないから届かなくて SEGV する、っていうような感じだった。
このクラッシュは記憶がたしかなら3世代目を tcc -run で実行してる時、つまり
tcc -run tcc.c -run tcc.c -c hello.c
的なことしてる時しか当時は再現しなくて、小さいプログラムだと件のチェックに漏れるような種類の長距離 call が出てこなかった、とかなんとか。このへん記憶あやしくて最後に走らせるコードは tcctest.c でも再現してたかもしれない。
このバグ再現させるには JIT 生成されたプログラムから負方向の 32bit を越える距離の関数 call をする必要があって、これが小さいプログラムだと起きない。なんでかっていうと、プログラムは malloc された空間に置かれてて、 glibc の malloc は小さい malloc に対して最初のうちは 32bit におさまるアドレスを返すから。でも、デカいプログラムだとデカい malloc をする必要があって、となると 64bit なアドレスがかえってきてやっと問題が再現する…とかいう感じだったと思う。
うーんでも詳細イマイチ覚えてない…
それをゴマかした時の変更はこれだったんだと思うんだけど、ただこれは上記の話をきちんと説明しきれてない気がするんだよな…
http://repo.or.cz/w/tinycc.git/commitdiff/51a7f163ad4a363953ae744afbc12cd7bd381097
あともう一個はよくある 32bit 命令を 64bit アドレスに対して使っちゃってた、っていう系だと思う。この手のバグは頻繁に起こりすぎてて、世代を経ると発生するみたいなヘンなヤツでもイマイチ詳細を覚えてないんだよな…
(00:04)
http://shinh.skr.jp/m/?date=20090416
微妙な記録を見つけた。
tcc -run tcc.c -run tcc.c は tcc -run tcc.c -run tcctest.c より先に動いたらしい。で、前者の方動かすのに最後に必要だった変更はそのデカい int literal だった、っていうのは、時期的にも正しい記憶だったようだ。
(00:11)
cydaea はなんか強かった。 FoT 的に細かい敵たくさんは案外めんどい。 NV 捨てて、 sweeping wind 入れて何度かやったら勝てた。倒した時はもういけるかとゴリ押ししたらかなりギリギリ感があった感じだった…
http://us.battle.net/d3/en/calculator/monk#abXkgi!XUY!acbaYY
azmodan は初見普段ビルドで余裕。 melee 的にはザコだな…まあ血の池弱くなってるんだよねたぶん…
iskatu もなんか強かった。細かい敵たくさんはやはりきつい。 FoT がきついので、 cripping wave とかを久々に入れてみる。あとはザコ多い戦闘では恒例の sweeping wind
http://us.battle.net/d3/en/calculator/monk#WbXkgi!XUT!YcbaYY
(14:19)
rakanoth 。結構強い。 sweeping wind 足したり防御重視にしたり。 sweeping wind はどうも普段からあると良いと思うんだけど、 primary 二つないとザコ戦しんどいんだよな… enchantress のスキル変えてみたりも。
http://us.battle.net/d3/en/calculator/monk#aiXhgj!XUT!aYbaYc
MoE と ally 頼りで殴り続けて、喰らいはじめたら breath of heaven 使って逃げるか、 serenity で殴り続ける。両方 CD の時は逃げ続ける
(16:07)
http://shinh.skr.jp/m/?date=20120703#p01
で書いた libarchive の tar は zip 内の symbolic link をちゃんと溶かしてくれないのであった…
(16:27)
モンク終了。
izual は WD の時はあれだけ苦労したのにザコだった。普段のスキルのまま倒せた。
diablo もまぁ長いだけでザコ…なんか第三形態って攻撃かなり激しくなってるんだな WD の時は常に離れてるから気付かなかった…スキルは rakanoth と同じ。
装備とかは ghom からなんも変わってないと思う…本当に ghom さんラスボスだった…
DPS16k armor6779(5339+1340) res708(all:450) life27961 LoH691
ghom の時と違う理由は単に二刀流か盾かってだけ。装備は全体的に spirit regen 無くてキツいな…という感じだった。
(22:53)
ghom たおした。
nerf とか入らんかったから farm だけで倒せる装備が入るの待つのがだるかったので、あっさり AH 無ししばりをヤメて安物を買いあさった。
最初は盾装備 15k くらいで戦ってて、あと1割くらいかなーてとこで enrage しちゃったので、1割くらいなら余計に殴れるかな…と思ったけど、また enrage すると悲しいので、盾やめて両手持ちにした。
DPS20k armor5482(3857+1625) res732(all:474) life28101 LoH600
http://us.battle.net/d3/en/calculator/monk#biXkgY!XUY!cYbaYc
買ったものは
ざっくり 1M くらいか。それでずいぶん強くなるなっていうか正直もうこれでクリアできる装備なんじゃないかな…
変わらなかったのは胸腰腕肩。
(00:47)
ついでに siegebreaker 倒した。 reflect damage ついてようが普段から LoH ついてるモンクからすればザコもいいとこだな…
act3 のこの部分元々簡単だったけど、それにしても簡単だった。どうもいい装備買いすぎた疑惑がありますね…目についたものを転売してたせいで金減るどころか増えてるんだけど…
そういえばウワサの vault てやつを回ってみた時に NV5 のまま belial ラクに殺せたりしたし(まあこの子は enrage さえしなければたいして問題じゃない)。
(01:36)
| 前 | 2025年 9月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 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 | ||||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
_ mtve [:)]