[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。 逆向き！ このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。 しかも、さっきから説明なしで意味ありげにくっついていた、 「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、 ということを意味しています。（上のソート
![[KMP77] を読んでみた - d.y.d.](https://cdn-ak-scissors.b.st-hatena.com/image/square/e6fe840dfdcca31b69f48171e0de96a69b93595b/height=288;version=1;width=512/http%3A%2F%2Fwww.kmonos.net%2Fwlog%2Fsub%2Fdual%2F8.png)
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
Twitter の翻訳 - d.y.d.
00:07 11/07/28 LOPSTR / PPDP 2011 LOPSTR と PPDP という共同開催の国際会議に行っていました。論理に基づく / 宣言型のプログラミングがテーマだそうです。 実況は例によって togetter.com/li/164644 にまとめてあります。 LOPSTR の方は、あまりよく知らなかったんですが、発表を聴いてみると、かなりガッツリと Prolog の言語仕様のディープなところに触れるような話があって、まるで、 C++ や Scala で盛り上がってる自分のTwitterのタイムラインの Prolog 版を見てるような雰囲気で楽しかったです。 Sloth 聴いた中では Sloth という Haskell のライブラリの話が一番面白かったので、帰ってから関連論文を読んでいました。 何をするライブラリかというと、書いた関数が「できるかぎり遅延評価する」も
アルゴリズムコンテストの挑み方 (3) - d.y.d.
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
ゆの in D - d.y.d.
17:37 08/07/30 ICFP Workshops via 住井さん で、 ML Workshop の採択論文リストが出てることを知りました。 "Many holes in Hindley-Milner" (複数穴あり Zipper 的なものをMLで扱う話、穴の個数を型情報に含めるための加算できる自然数表現を差分リストで、 っていう技が面白かった) と "Unrestricted call-by-value recursion" （call-by-value で再帰的な (ループした) データ定義を実現する手法、これで、フルの call-by-need セマンティクスがなくてもそっち方面で使われてる テクニックをいくらか持ってこれるよ）というのだけ読んでみた。 他の併設ワークショップ の論文リストも 揃ってきてるみたいですね。 個人的に WGP の "Concepts =? Typ
d.y.d.Я９Я∽
10:14 08/04/29 いろいろ 来月末 東京メトロ沿線ウォーキング のために、じゃなかった、友人の結婚式があるらしいので、ちょっと一瞬日本に戻ります。 いやまあ、メトロウォーキングには行きますが。 りふぁらにれす アニメ、というのが通説らしいですが個人的にはゲーム。 プログラミングと俺（続き） 前回 書き忘れた。中学校の"技術"の授業で LOGO でタートルグラフィックスとかもやりました。 使ってた処理系でどこまでできたのかは全く知らないのですが、まあひたすらお絵描きしてました。 つまりメガデモ製作です(違。いろんな図形を描くときそれに伴って動くタートルをいかに作品内に取り込むか など真剣に考えたりしてました。LOGO っていう言語についてはもう、「てじゅんは」っていうキーワードしか 覚えてないですね。タートルグラフィックスって、適当なコードを適当にパラメタ変えて色々走らせると す
d.y.d. memo: POPL 2
17:17 08/01/30 ところで C++ か JavaScript か PHP が批判されてるのを見ると思わず何か言いたくなってしまうのだけど、 考えてみるに、他の言語だと割とどうでもいい。そういう意味では、今の自分が好きなプログラミング言語は この３つということになるのかなあ……などと徒然なるままに思いました。 単純に、つきあいが長い方から３つというだけかもしれない。 いやしかし、PHPに対する批判の多くはその通りであるとは思うのですが。 Attacking PHP で触れられてる「リストであり辞書でもある」 array ってあれは普通に便利じゃないです？ 結構他の言語でも欲しくなるのですが。 17:08 08/01/29 PHP で Yコンビネータ PHP じゃ Y コンビネータつくれない と聞いて。 <?php // PHPでは関数呼び出しは 関数名(...) か 変数(...
w.l.o.g.
23:48 04/04/07 これ考えたヤツは天才だと思う。 六法 譲ってもらった。まだ本棚を買っていないので、 入手量に気をつけないとすぐに部屋に書物の山が形成されてしまいそう…。 そういえばSBには、３年前に暗号化関係の本を貸すと宣言して それっきりになっていたような気がするっていうか忘れてたすみません。 大名廃絶録 20:47 04/04/06 Windowsに付属してくるスパイダソリティアというゲームがありまして。 暇つぶしに遊び始めてしまって、気がついたらあっという間に一時間も過ぎていた、 なんて経験をされた人も少なくないと思います。 さてそんなスパイダソリティアの「初級」、 100発100中で解けてつまならいとお考えの方に新しい遊び方を提案いたしましょう。 まずはゲームスタート。 オーケイ、スタートだ。そして そしてまず全部配る。さあ解いてみよう！ 難易度 上級と同程度以上には
d.y.d. 「帰宅 from PPL」
18:59 07/03/31 3/31 今日はエイプリルフールですね（←嘘 RSS この日記のRSSをちゃんと自前で生成するようにしました。 http://www.kmonos.net/wlog/index.rdf です。 Auto Discovery もそっちに向けてあります。なんか変なところあったら突っ込みよろしくお願いします。 とりあえず感想としては、RSSみたいに名前空間が混じりまくるXMLを扱おうと思うとE4X結構めんどくさかったです。 18:15 07/03/28 まんが 近所の本屋で見あたらなかったのでちょっと遠出して 『大東京トイボックス』購入。 あと、もちろんもずくも。 モーニングでやってた（らしい、コミックしか読んでないので）『東京トイボックス』がBIRZに 移って再開したものとのこと。弱小ゲーム制作会社があれこれする物語。 前作かなり面白かったので期待してました。そし
d.y.d. - 01:34 06/12/07 - Python Workshop 04
01:16 06/12/29 年末まとめ 日記を読み返したりその他状況証拠から、今年の自分を振り返るのコーナー。 今年やったこと行ったとこ等と、今年読んだり聞いたりして好きになった 本/音楽などなどを適当に並べていきます。 後者は私が今年読んだ/聴いた作品から選んでいるので、必ずしも、 この一年の間に発表されたものとは限りません。 1月。 やったこと：修論 (MTran) 書いてたはず。XMLが木構造が正規表現がオートマトンがどうとかいう話。実装が やっつけ仕事にもほどがあるのでなんとかしなきゃなあと思いつつはや１年。 マンガ：『いわせてみてえもんだ』の続きが気になってしかたなくなりました。夏頃から ヤングガンガンで連載が始まって、今ちょうどもうすぐWeb版に話が追いつきそうな ところなので続きが気になってしかたないです。 2月。 本：『考える脳 考えるコンピューター』 "予測" こそが
d.y.d.
16:48 06/10/31 無限ループ From このへん。 _=*"".."_" 0H10B、とかはありでしょうか。このRangeのmin辺りを呼べばメモリも食わず経済的です。 ゴミメール す 写 つ 男 当 ご 景 行 わ こ 先 秋 女 ぐ 真 ま 性 サ 希 気 き た の 日 も 性 に 付 り 会 ｜ 望 も 違 く 度 小 一 h の ご き 本 員 ク も 徐 い し ア 池 段 t 写 希 プ 当 様 ル 充 々 で 山 ド よ と (以下略) なんか縦書きのスパムが来ててちょっと面白かったです。フィルタ避けでしょうか。 でもURLまで縦書きだと、さすがに誰もたどろうとしないと思うんだ。 クリックは当然のこと、コピペもできない。 ゴルフ ネタバレはないですよ。 Switchboard: 109B (Ruby, とりあえず書いてスペース削っただけ版) → 88B～
d.y.d.
21:21 05/09/29 ですのーと 本棚をぼけーっと 見ててふと、写真で左から４冊目の数論入門、訳者名と著者名をあわせて やがみライト だ！ と、大発見をした気分になっていました。どうでもいいですね。 20Q 20Q。おお、商品化されるのか。 これは買わねば！ 05:31 05/09/29 ICFP Programming Contest 結果でてますね。 combat３位おめでとーございます。 今回のコンテストは二段階制になっていて、『最初の３日間で、 テーマとして与えられたゲーム（マップ上の銀行から金を盗んで逃げる"泥棒"と、 それを捕まえるべく頑張る"警官"の駆け引きゲーム）の２種類のボットを作ってsubmit。 その２週間後にゲームが微妙に拡張されたり仕様変更されたりするので、 １日でボットを作り直して、再submit』というものでした。 もちろん最終的ルールにおいて一番強い
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
