週記
そのうち、カレンダーで自動管理できるようにします。→そのうちって何年後。
今テスト移行中です→http://shuns.sblo.jp/
2007-11-29
繁体字windowsでタスクマネージャが「工作管理員」だった衝撃。
プログラマなら知っているべき10(12)のアルゴリズム
色々あるけど、「今の俺たちが何も考えずにプログラムを書けるのはなぜか」ってのなら次の奴かなぁ。
- Quicksort
- あまねくプログラムでの多大なる貢献により
- RSA
- 暗号化についての貢献により
- Lempel-Ziv / Burrows-Wheeler transform
- 圧縮による貢献により
- Fast Fourier Transform
- あまねく映像・音楽部門での貢献と、数値計算での多大なる貢献により
- Topological Sort
- パッケージ管理とmakeについての貢献により
- Copying Garbage Collection
- JavaとC#での貢献により
- Dijkstra / Bellman-Ford
- ルーティングを日夜支えた貢献により
- LR parsing
- プログラミング言語を支えた貢献により
- Longest common sequence
- Linusのバザールを支えた貢献により
他にデータ構造部門があれば、線形リスト、B-tree (とその変形)、ハッシュ表、スキップリストを挙げたい。ちょっと微妙かなと思ったのでskip listだけ削除。
2007-11-18
研究のGoogleJ:守破離なんてことを考えたりしていた。俺は破に入るのが早すぎるともっぱらの評判である。
segfault
なんか6月ごろ経験したia64でふっ飛ぶバグは未解決ぽい。とりあえず落とす最小テストケースを作って投稿しようかな。
2007-11-14
FFTW&Cilkの人あんな会社を作っていたのか。びっくり。
ブーム
ブームに乗って、Tools/MaxFlow-Dinicを書いてみました。少しずつ手を入れて改善する予定。まずはなんちゃって過ぎるDFSを再帰にしないとな。
そいえば
最小費用流だとコストスケーリング付きG-Tがそこそこ短くて速かったのを思い出した。他にないのかな。
2007-11-12
性能のいい人
http://d.hatena.ne.jp/sumii/20071112/p1
僕にも単純に性能のいい人・悪い人が確率的に存在しているようにしか見えません。母集団に対しフィルタをどれだけ掛けたかの違いだけです。
追記:「は」→「も」と修正。ついでに追記。
2007-11-8
PC^2が"secure enviroment"とか呼ばれていて粉茶吹いた。うちらなんかjudge machineを落としてしまったことがあるもんね!(かなり笑えない)
……と書いて、ひょっとしてそういう理由で? とか思ってしまった。
参考
2005年八王子大会で、我々はqueue<>にデータをつっこみまくってジャッジマシンをメモリ不足で落としました。
後1問解ければ2位だっただけに大変高階しています。
Pの人との会話で
- プログラミング経験値は考えてコーディングした時間に比例する。
- フライトシム経験値は考えて飛行した時間に比例する。
- 数学経験値は考えて式変形・証明した時間に比例する。
- 物理経験値は考えて微積分した時間に比例する。
- 作文経験値は考えて記述した時間に比例する。
- ロマサガ経験点は考えて高速ナブラした時間に比例する。
とかいうのを考えた。つまりコピペ=0。
投稿受付中(何
2007-11-4
UnknownのコーチとしてICPC東京大会に参加してきました。 今年はだいぶ易化したようで、解く順番に選択肢が生じるレベルでした。毎年これぐらいの難易度だと「死に問」が出なくて良いですね。
Unknownのみなさん2位おめでとう。コーチとしては非常に精神衛生上良い戦いっぷりで非常にありがたいチームです。自分たちのチームは相当コーチの心臓に悪かったんだろうとコーチになってはじめて把握しました>歴代コーチのみなさま。
それにしても越前が最後の1分で通してくるとは。unkに優勝おめでとうと言おうとしたら、終了後に越前に9個目の風船が持ってこられて大ショック。
だが一番の衝撃はこっちだった
まさかGoogleJ:叙述トリックをリアルで食らうとは思わなんだ。 改めてみるとあらゆる場所に伏線が張られていた……。
2007-11-1
Caml-listのdigestを購読して居るんだけど、正直約1名ほど受信拒否リストに入れたい投稿者ががが。
とりあえずノイズより酷いのは勘弁。
やっぱCWNだけ読むべきなのかな。それともdigestやめて、上の人を自動junk判定して、Xavier Leroy氏が反応しているのだけ読むとかすべきなのかなぁ。
spamに時間を取られているみたいでなんか悔しい。
げむ
CoHが酷いことになってしまったせいで、Oblivionが再度発掘&プレイされることに。てかCoHを1.71に戻してくれ。
BHGが作ったらしいAoE3?/TADに手を出すかなぁ。今の状況で買うとプレイ時間で間違いなく睡眠時間が飛んでいくので迷い中。
あと、正直なところスパムRTSは飽きてるんだよなぁ。CoHやらなくなったのもそれだし。スパムゲーに変わってしまった。RoN好きだったのもスパムがやりにくいからだったし。
上記2エントリの結論
No more spam. でもSPAMはたまに食べると美味しい。
ひらめいた
ICFPC-2006 & 2007があるじゃないか!
OCaml
MapとHashtblでfoldが左右逆なのが何度見ても許せない。
Blogサービス選定中
- いつでもテキストダンプが取れる
- Evilでない
- PHPでない
- GPL or BSD
…条件きびしーのかな。
2007-10-12
OCaml to Javascript compilerらしい。何人か作っていた人がいたけど、リリースされたのを見たのはこれが初めて、かな。
OF
Relic QAは本当に何をやっているんでしょうか。
某スレ
書き込んでいるのは私じゃないですよぉー。
TODOめも
- La_p4
eg+de某社の何か- 某氏の何か
2007-10-10
ICFP-PC 2007 techreportが出ました。いろいろと内部が書いてあって笑えます。さて、2006年度のやつに早く手を付けねば……。
追記
RSSとPermalinkなくてごめんなさい。>各所
2007-10-4
Jane St. Capitalが東京officeに募集を掛けているらしい。腕に覚えのあるFプログラマの型^h方、いかがでしょうか?
2007-10-3
2007-9-26
http://ocaml-reins.sourceforge.net/
Jane ST. C.のSummer projectでできた「persistentな標準的データ構造いっぱいうはうは」なプロジェクト。Persistentって何、ってひとはWikipedia:Persistent_data_structureを見るべし。
OF待ち
THQのマーケティングとRelicのQAとRelicのリリースノート作成者はなにをやっているのでしょうか……。このままでは手が出せん。
2007-9-24
この計算が終わったら……OF買おうと思うんだ……。
アルゴリズムは出来たけど、既存手法と差が出てかつ単純なケースがなかなか思いつきません。差が出ない単純なケースと差が出る複雑(で時間が掛かる)ケースはすぐに思いつくんですが。というか後者の為に開発したんですが、後者は著しく時間が掛かるのでアレしたくないという。むにゃむにゃ。
あー死亡フラグしか立ってない。
2007-9-17
あれ、
type void = V of void
て定義できなかったっけ……と思って
# type void = V of void;; type void = V of void # let rec v = V v;; val v : void = V (V (以下数十行ほど省略)
とやったところでこれを思い出した。
type void
でいいような気がする。試してみたけど3.09/3.10で通った。本筋に全く関係ない超絶な枝葉で正直我ながらうざさ爆発とか思っているので某所にコメントとかは付けない。
というか
これができないと循環リストが定義できないぃ。Obj.magic使えって?
2007-9-12
無理数を知らない子供たち
って書きそうになってやめた。
元記事はふつうに賛成だがなぁ。参考:8/3エントリ
追記:もっとも根幹で「なにができるか」がわからないと、なぜアルゴリズムやデータ構造が有るのかわからない。だからまずアーキテクチャを勉強するべきだと思う。その足がかりがマシン語。そういう視点で見ているからべつにZ80でかまわない、基本演算で何が出来るかを知っていればそれだけで違う。あと、アーキテクチャをソフト視点で見るかハード視点で見るかは大きな違いで、僕はソフト視点だ。(どっかのH木研の人には「何を考えているのか」と言われそうだが。)ソフト視点ならRAM modelやexternal memory modelがあるしこれは全プログラマ必修だと思う。そうでないとなぜリストと配列というデータ構造があるのかわからない。どこぞのLL言語ではこの2つが一緒くたにされていたりするんですがね。
追記2:「関数型言語を知らない子供たち」まだー?
追記3:「LL言語」って何だ俺。「OCaml言語」とか「IT技術」とかの親戚か。
2007-9-5
2ヶ月くらいフルに使って推進してきたネタが昨日ぽしゃりましてダメージを受けております。
こういう業界にいたら当たり前なんだけど、それでも凹んでしまう。
追記:なんか考えていたら(かなり険しそうな)別の道が出てきた。……これは某先生の某日記と同じ展開?
追記2:別の道もつぶれた。orz
2007-8-10
ICFP-C東日本参加者のお疲れ会(のようなもの)。
「ムーアの法則が成り立てばNP完全問題は線型時間で解ける」 「渋谷から10分の都内有数のゴルフ場経営者」
どちらもウーロン茶吹いた。
2007-8-7
未踏の成果報告会を聞きに行ってきました。初っぱないきなりパンチカードと穿孔機でPMさんたちが盛り上がっているのを見てニヤニヤしていました。さすがだ。
とりあえず今日のまとめは
- GPUいいよGPU
でしょうか。なんか本来の発表者のうち4つぐらい無視した発言ですが。GPUはまさにいまが旬という気がします。あと付け加えるなら、
- M研出身の人はみんなアセンブラで会話できるんだなぁとか思ったんですがこれは理解でしょうか誤解でしょうか
- 微妙に分野が近いと用語の差違に戸惑う罠
- ○○○○○○化はやってみたいねぇ
2007-8-3
Education is learning what you didn't even know you didn't know. -- Daniel J. Boorstin
「プログラミングなんて誰がやっても同じ」とか言う人は、ちょっと勉強してみると良いと思うんだ。世界広がるよ?
まぁとりあえず
SQLが書ければプログラマっていうのも間違いじゃない。それは立派なプログラミング言語だ。
スクリプト言語1つだって、書ければ立派なプログラマだ。
でも、それだけがプログラミングじゃないし、それが全てだと思うのはあまりに勿体ない気がする。
プログラミングは道具だ。良い道具、手になじむ道具、細かいところに手が届く道具を持っている方が楽に、高機能な新たな道具を作れる。持っている道具が、70年代の研究結果をラッピングした「SQL」で終わってしまっているのは、ちょっと勿体ない。ちょっと背伸びするだけでもっといろいろな道具を持てるのに。
だから、DBとXMLさえ分かればそれがプログラミングの全てだっていうのは…ちょっと、あまりに勿体ないと思うんだ。
だからといって
特にアカデミアに、産業を見下している人が居るのは、よろしくないと思うんだ。うん。
「教えてやる」とか「分かりやすい形にしてやる」とか、ちょっとそう言う見方はどうかと思うんだ。
50年後のための研究は大切だけど、その50年を支える人たちがいてはじめて成り立つ研究だって事を忘れちゃまずい。50年間生き残れなかった技術は山ほどあるのだから。
2007-7-25
ICFP-C (not ICFP)、ちらほら聞こえる声について
去年の物議と、今年のinterpreterに関連して。前もって断っておくと、これは決してkinabaさんに対する批判ではありません。
去年は別にポインタと整数が相互変換可能な言語でなくても、再利用可能なメモリを保持していればVMは決して重くなかった(camlのチームでこのアプローチがあった)。というわけで、去年のumixはC専用という(discuss-MLで流れた)指摘は筋違いだと私は思っています。彼らは不平を言う前に実装を確認するべきだったんです。ちゃんとメモリ再利用重要ってアドバイスに有りますよね? 元ドキュメントの。
今年も関数型データ構造がなければ実装が特別難しいという訳ではないと思います。たとえば今年のdiscuss-MLでは「char*のリストで処理したら10秒切ったよ」という話が流れていました。
去年も今年も言語によって不得意がどうのというのは、インタプリタ言語を使っている場合を除いて不適当では無いかと思うわけです。(逆にここ2年Python/ruby/perl teamはかなり割を食ったのでは無かろうか)
「○○だと楽な問題」はかならず存在するんだから、自分の選んだ言語でそうでない場合に、どう工夫するかがハッカーとしての腕の見せ所でしょう。そのために言語を選ぶのも腕の見せ所でしょう。それを怠って問題が悪いとか言うもんじゃない!
……という物議を醸しかねない発言をしてみる。
去年も今年も、出題者側はものすごい時間をかけて準備をしていますし、両方で効率的な実装があることもちゃんと確認していると思います。その証拠に、必要な情報はちゃんとアドバイスにかかれています。だから、問題sucksとか言っちゃだめ。
バランスは別問題?
それは別として、スタートラインがちょっと後ろすぎた気がする。もうちょっと前に設定しても、上位はゴルフ大会・中位は遺伝子修理大会で十分勝負として成立したのでは? と思いました。まぁ「お前遅すぎだからm9」と言われると反論できないわけですが……。
ICFP-C (not ICFP)、ちらほら聞こえる声について2
ICFPはICFP contestじゃなぃぃぃぃぃぃぃいぃぃぃ
とかいってたら
rubyで解いている強者発見。
2007-7-23
ICFP contest(not ICFP)
今年はphoenix君、GUSさんにIhi者という組み合わせで参加してきました。結果。 うちのチームはminnanoamlで、残念ながら15位入賞は果たせませんでした。
とりあえず自分が書いたprefixアセンブラを晒しておきます。(asmprefix.tar.gz) 我々のdna2rnaインタプリタは、cygwinでOSごと持っていくという素敵なバグのために非公開です。 欲しい人はメールでもください。参考までに言うと、ropeを用いて実装しました。
追記:
from kinabaさん日記:
これで for(;;) { String x = "x"; } もリソースリークするんだけど。
えーと <ext/rope> のせいだ俺は悪くない。もうropeとか死ねばいいのに。
STLのソースを追っていったところ、「マルチスレッド環境で参照カウントするために、
ropeの各ノード毎にCreateMutexしてる。」「でもCloseしてない。」。こんにゃろう。
今とりあえずシングルスレッドで用は足りるので、mutex周り全部コメントアウト。直った。
快適快適。ついでにDNAインタプリタが倍速になった。
これかーーーー!!!
dna2rnaの実装についてですが、関数型なら個人的に最もエレガントな解法、というか自分ならこれで書くかなと思ったのはRandom-access listかFinger-treesで、これは知らなかったのですが後者はなんとGHCのSequenceにすでに入っているらしく、そのまま利用できたそうです。いーなー。Haskellによるエレガントな実装はきっとtanakhさんあたりが公開してくれることでしょう。他にもちろん破壊的なデータ構造でも行けますし(ropeとかですね)、listでコンカチしたstringとかでも行けるとのことでした。
我々は結局、暗号を解く手がかりをほとんど持たず、外からgeneを呼ぶことしか出来ませんでした。最後にad-hocに結果を出すフェーズを、もうちょっと早くからやっていればもう少し結果が違ったかもしれません……。
それにしてもshinh method強すぎ。
あとでちょこちょこ書き足します。
わかったこと
- ocamlbuildは超便利。tryfinallyとそれを使ったocamlscriptを3.10に移植してしまおうかと思ったぐらい。CVS版使おうかな。
- Endoはendonuclease由来なんだと思ったんだけど違うのかしら? →なるほど納得。anaとかcataとかが無くて残念w
- mp3は気付かなかった人が多かったらしい。でも我々はその先のヒントに気付かなかった。
- なんか速い実装は20秒とかで終わるらしい。Σ→10秒切るらしい。ほげー!
- トップ集団の人たちの逆アセンブルの結果とか凄まじいな
- Excellllllent!!
- こうして見ると段ボール塗れなかったのが大きいなぁ
2007-6-30
「一日5000typing? 社保庁はなんて凄いんだ! 5000回も型付けをするなんて、俺には出来ないよ!」
pattern guards
http://code.google.com/p/ocaml-patterns/
p4使ってviewに近いパターンマッチ文法拡張を入れたよという話(超斜め読み)。when部分でマッチが出来るらしい。
2007-6-22
camlp4@3.10をどうにか書けるようになった。いろいろ変わっている+ドキュメントがまだないのでちょっと困った。
ぷろぐらま?
http://anond.hatelabo.jp/20070621222911
考えさせられる。こういうケースが希でないことは知っているんだけど。
こういう人が歳を取って「上流工程」に移動する。学生は現在のITの状況を聞いて進路決定をする。かくして日本のITに就職する優秀な若者は消え、業界はますます暗くなる、と。素晴らしいスパイラルである。ぐの会社にISerが集まるのは至極当然だ。
就職とか、情報系での博士の受け皿とか、横から見ていていろいろ思ったこととかがあるんだけど、それはまた別の機会、時間のあるときに書きたい。
2007-6-19
「それ波動関数表示にしたらどうなるんですか?」という素朴な質問に、とても重要なことを気付かされた。おぉぅ。
Bracketはただの記号なのだが、記号は思考の梃子であるから重要なのだなぁと気付かされた一日。
線形代数は本当に(ry
2007-5-30
ふむふむ、こうやって使うのか。今度やってみよう。
2007-5-28
今日の結論
(NDA)。
今日のorz
三単現忘れすぎ>俺。とりあえずいろいろ酷かったので直した。記事の恥は書き捨て。
…見直す度に誤りが見つかる。取りきれるのは何時だ?
…というか最初の表現はall your base are (ry状態であったことよ。
2007-5-27
書類書きに疲れたのでProgramming/OCaml/JokeFizzBuzzこんな物を書いてみた。
追記1: >狐氏 反応ありがとうございます。それは考えたのですが、なかなか縮まなかったので諦めました。きっとphoenix氏あたりがエレガントな解を提供してくれる物と信じます。
追記2: ちなみに私はpattern-matchもしくはguard派です。
追記3: そしてちょっとずつ追加
追記4: http://golf.shinh.org/p.rb?FizzBuzzみたら普通に100bがあった。遠いー!
2007-5-18
いろんなところで出ていますが、3.10リリースです。
個人的に重要なのは
- nativeでスタックトレース追加
- Camlp4が変わりました
だけだなぁ。O'の部分は正直気にしていないので。
追記: ライブラリ見たらだいぶ嬉しい変更が。
- Sys.is_directoryが追加
- Bigarray.mmapがスタート位置の引数を取れる
- Scanfに%rが追加
2007-4-29
http://www.spoj.pl/ranks/SQRT2/
大会中は諸般の事情により抑えていたSQRT2を再開。 200万桁まであと2歩。
2007-4-20
観測できない確率過程なら乱数生成器としては妥当な気がする。
量子も原子核崩壊も熱ゆらぎも、「実験的に」確率的事象であることが分かっていて、「現在広く信じられている、実験事実によく合うように作られた理論の枠組みで、それを確率事象であると信じることが妥当である」点で同一である。
ひょっとしたら今日にも反証が出るかもしれない。現実は違うかもしれない。でも今の私の知識では、どれもが確率事象であることは現在「広く信じられている」。
2007-4-17
黒魔術
手を染めてしまった。
type internal =
{ sign : int;
abs_value : nat }
let nat_of_bi (x: big_int) = ((Obj.magic x) : internal).abs_value
let bi_of_nat x = ((Obj.magic { sign = 1; abs_value = x }): big_int)
let dmw k = k / length_of_digit, k mod length_of_digit
let shift_left_long x k =
(* shift k bits, long range *)
let nx = nat_of_bi x in
let kdw, kmw = dmw k in
let size = length_nat nx in
let outn = make_nat (size + 1 + kdw) in
blit_nat outn kdw nx 0 size;
if(kmw <> 0)
then shift_left_nat outn kdw size outn (size + kdw) kmw
else ();
bi_of_nat outn
勝てません
これ以上はどうすればいいのか…。次の反復は4倍時間掛かるし。2進10進変換がネックだから最初から10進にするかなー。
観察
桁数の伸び方からどうやったのかわかった。
2007-4-5
アカデミアにどれぐらい期待するかは出身学科の影響が強いらしい。N=2なので問題だが。
3ヶ月以上考えてきた次のテーマのネタが、全く別の先行研究に帰着できることに気付いて、喜ぶべきか悲しむべきか微妙な状況。
2007-4-3
Twiki really sucks. Devastatingly.
MoinMoin?がいかに良くできていたかを思い知らされた。
2007-3-8
とか書きつつ単文更新。
主な更新点は書いてあるとおり、
- Exception時スタックトレースの追加
- build tool: ocamlbuildの追加。OCamlMakefileも変わるのかな。
- camlp4刷新。構文木traverseとか文法大改変とか。
2007-1-9
ふいた。
2007-1-1
今年の目標。
研究
- 修論をとっととカタす。
- 論文をとっとと書く。
- 短期研究ネタ'aと'bをとっとと動かす。
- 見積もりをより正確にする。
- 低分子のアレとかコレとかを考える。
- 非平衡のアレとかを考える。
プログラミング
- 使いやすい趣味アプリをつくる。わざわざダウンロードさせるのはダメだ。
- 某コンパイラの次期バージョンを設計してみる。
- 自分用浮動小数DSLコンパイラを書き上げる。
- Coqを習得する。
- Coq以外で言語を覚える。+2個ぐらい目標。
- 連続系の勉強をもうちょっとする。
その他
- 料理を覚える。
- アナログ回路を一通り勉強する。
こんなもんか。1年要らないものがほとんどだが、まぁ。
追加
- p4
- 先輩に放置プレイを仕掛けるという不埒をやめる
- ICFP-PCを遊ぶ。
キーワード:
参照:[SideMenu] [週記/2005-05] [週記/2005-08] [FrontPageJP] [週記/2005-12]