d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
行列と項書換 - d.y.d.
21:54 10/06/30 行列と項書換 "Termination of String Rewriting with Matrix Interpretations" という論文を読みました。 これは何かというとつまり、 ICFPコンテストの元ネタとして 紹介 されていた論文です。 れ い 年、 冗談９割で、主催者の専門分野にちなんだ問題が出るに違いない！と叫んでいるのですが、 本当に来るとは思わなかった…。 さて。項書き換え (term rewriting) と呼ばれる研究分野がありまして、 例えばこんな問題を調べています。 文字列に対して、「以下の操作のどれかを好きに選ぶ ＆ 実行する」を繰り返します。 abc という部分文字列を de に書き換える （abc ⇒ de と書きます） ef ⇒ g fgh ⇒ ij どんな文字列からスタートしても、最後には、どの規則も使えない状態 （つ
TLE '10 - d.y.d.
09:37 10/02/28 PrezzProcezz TLEのPREP は、私のコードは縮める前がこんな感じで、 // println(X) #define p(X) X _Pragma("") // H = 百の位が… (a: 3で割って0余る場合、 b: 1余る、 c: ２余る) #define a(H) d(H 0) e(H 1) f(H 2) d(H 3) e(H 4) f(H 5) d(H 6) e(H 7) f(H 8) d(H 9) #define b(H) e(H 0) f(H 1) d(H 2) e(H 3) f(H 4) d(H 5) e(H 6) f(H 7) d(H 8) e(H 9) #define c(H) f(H 0) d(H 1) e(H 2) f(H 3) d(H 4) e(H 5) f(H 6) d(H 7) e(H 8) f(H 9) // HJ =
ちょっとだけマイナーなSTLの話 - d.y.d.
21:23 09/11/29 ドラクエ３ ドラゴンクエスト III モバイル版 が配信開始されたと聞いてはプレイせずにはいられない、ということで、さっきクリア。 内容は 「SFC版のベタ移植 - すごろく場 + AI戦闘」 ですね。 すごろく場が減った分、限定アイテムが他の場所に移動 （パワーベルト・ドラゴンテイル・ドラゴンローブ・グリンガムのムチが小さなメダル賞品に。 光のドレスがゾーマ城の宝箱に。雷神の剣も宝箱だった気がする。あと、小さなメダルの総数が110枚で変化無しらしいので、 すごろく場にあった分が通常マップに押し出されて、ところてん式に押された炎のブーメランもメダル賞品化）。 不思議なボレロと女神の指輪は見てない。なくなった？ AIは、マヌーサ/ラリホー/マホトーン辺りを効く相手にだけ積極的に使ってくれるので参考になる＆便利。 勇者もAI駆動にできるモードが欲しかった 細かいと
d.y.d.
19:34 09/09/19 ※Multi Exit 「C言語の関数呼び出しで引数は何個も渡せるのに返値は１個しかないのはどうしたことだどうせスタックに置く個数が変わるだけなのに」問題に関連する話に 「リターンアドレスが１個しかないのはどうしたことだ」問題があります。 どうにかしてみましょう。 String|NotFound get( Map<Int,String> map, Int key ) { if( lowlevel_primitive_map_has_key(map, key) ) return lowlevel_primitive_unsafe_map_get(map, key); // 1個目のリターンアドレスに返る return new NotFound("Error: the key \""+key+"\" not found"); // 2個目のリターンアドレスに返る
Title Here
1/61 自己紹介 • なまえ： k.inaba (けーいなば) • なにもの？： 珍妙言語機能妄想日記書き – http://www.kmonos.net/wlog/ – 「タグストラクチャル型」 「お気楽非決定性」「return[f→g]」 「物知りなぬるぽ」「Я９Я∽」 「手続型リアクティブ」「Int./¥d+/」 「名前推論」「Aspect指向Yコンビネータ」 … 2/61 プログラミング言語の過去 • 1954 FORTRAN • 1958 LISP, ALGOL • 1959 COBOL • … 3/61 プログラミング言語の過去 • BC7000～4000 印欧祖語 • BC5000～0 日本語 • AD410～500 英語 • 1954 FORTRAN • 1958 LISP, ALGOL • 1959 COBOL • … これら数千年の歴史をもつ言語を 「プログラミング言
Title Here
いまどきの！？ プログラミング言語理論 いなば かずひろ 稲葉 一浩 http://www.kmonos.net/ http://twitter.com/kinaba 言語組：講義資料 2/39 お話しする内容 •時は2009年 •「プログラミング言語」の 「理論」の 「研究者」のあいだで •今なにがアツい？ 3/39 理論系のトップレベルの学会 •POPL 2009 –Symposium on Principles of Programming Languages »“プログラミング言語の本質” •ESOP 2009 –European Symposium on Programming 4/39 今年の時間割:POPL 2009 • 並行性 (Concurrency) • 型１(Types) • その他１ (Medley) • 静的解析１ (Static analysis) • 関数型ﾌ
d.y.d.
20:52 09/07/30 こんすとぽ 確か cppll でかなり昔に見た記憶があるんですが、C++ のこれ int I = 42; const int CI = I; // OK! int* pI = &I; const int* pCI = pI; // OK! int** ppI = &pI; const int** ppCI = ppI; // コンパイルエラー! int** から const int** への変換はできません! は何故こういう仕様になっているのでしょうか？というのは面白いクイズだなーと。 「2番目が安全なのと同じで、3番目も型的には安全では？」と一瞬思ってしまうのですが、 そんなことはなく、このキャストを許すと const なはずのものを書き換えられてしまいます。 具体的にどうやるかは読者の皆様への宿題です（←偉そう）。 知った当時はよく仕様考えてあるなーすげー
論文ファイブ - d.y.d.
16:40 09/01/28 インドコンテスト おとといのを読み返してて、 全体として並列並行系多いなーといっておきながら、 個別紹介に１個もそれ系のがなくて面白いなあと思いました。 と、それはともかく、今年もインド発プログラミングコンテストのお知らせが来てました。 ICPCやTopCoder系の問題の出る CodeCraft、 Project Euler系の問題の出る MathematiKa、 あと今年はなんだか縛り付きプログラミング（ゴルフとか）系の Time Limit Exceeded というのがあるらしい。毎年恒例行事にするつもりなのかな。 去年のはわりと面白かったので、今年も参加してみるつもり。 23:10 09/01/26 POPL 2009 行ってきました。MS Research 多いなーというのと、 まあ当たり前ですが並列並行系多いなーというのが全体的な感想。 以下印象に
アルゴリズムコンテストの挑み方 (2) - d.y.d.
21:25 08/10/27 論文 の締め切り終わったら頑張った自分へのご褒美（笑）であれとこれとそれをやる時間をとるぞー！ ……みたいなことを思っていたはずなのに、いざ提出し終わると気が抜けて何一つやる気がでない問題。 困った困った。 ナイチル たくさん人がいらしてる今のうちに 「ナイトメア☆チルドレン」新装版 面白いよみんな買おうぜ！ などと書いてみる。 自分のマンガの趣味はわりと平凡だと思ってて、 流行ってるマンガは大抵好きだし自分の好きなのはだいたい流行ってるし。 なのになぜだか藤野もやむ作品だけは唯一の例外で、とっても不思議でならない。 100回くらいアニメ化されてて然るべきだと思う。 何回か書いてますがとにかく最終話が好きで、 そこまでのシナリオが一気に集まって一つ一つのセリフが３倍の重みを持つように収斂していく幕引き。 あれは良い。 17:12 08/10/24 アルゴリズム
アルゴリズムコンテストの挑み方 - d.y.d.
17:29 08/09/30 クロスワード 暇つぶしに "Clueless Crossword" という冊子を買ってみて意外とハマっています。 クロスワードパズルなんだけど、単語のヒントの代わりに、 各マスに1～26の数字が振ってあって同じ数字のマスには同じA～Zが入るように埋めるというもの。 「母音っぽくて二連続して語尾にも出てくるのは多分 E だろう、もしかしたら O の可能性はなくもないけど」 みたいに埋めていく。 ちょっと違うけど フラッシュであった。 20:15 08/09/28 だいちのよろい そろそろ日本に戻る前に観光するぞ月間、ということにして、ウルル（エアーズロック）に行ってきました。 もっとワイルドな感じかと思ったら、完全にリゾートのリゾートによるリゾートのための地帯になってました。 まあそんなもんか。 本日は強風のため登るの禁止とのことだったので、周りから見るだけ。
d.y.d. 正規表現にマッチする例をランダム生成
15:43 07/05/17 正規表現にマッチする例 soutaroさんの 正規表現にマッチする例をランダム生成 する話を見てたら、 自分でも書きたくなってきました。というわけでソース。 正規表現を構文解析してオートマトンに コンパイルしてから、その上を似非ランダムウォークしてます。対応してる正規表現は ?と+と*と|と.と[…]だけです。[…]の中の-とか^とかにも反応しません。あと IE と Rhino でしかチェックしてないので他の環境で動かなかったらゴメンナサイ。 きっともっとマトモなのをsoutaroさんが公開されるはずです。 ボタンを押したらこの上↑に10個例が生成されるはず。 で、動かしてみて思ったのは、当たり前だけど繰り返しが長続きしないなー、と。 確かに、ループをちゃんと意識しないと面白い結果にならないかもしれないですね。 なるほど。 追記12:15 07/05/18 ぎ
d.y.d.
00:18 05/11/26 経県値 母上からの指摘で秋田県が赤くなりました。修正。 山形と茨城もこれでよかったか微妙に自信なし。 （追記：茨城も赤いことが判明。） 木和 私の Tree Summing のコードが見たい人は、このページのソース内コメント 読んで下さい。「もっと読む」機能とか実装するの面倒なので手抜きばんざい。 あーでも、自分で解いてみて、できれば２日くらい悩んでみた人じゃないと 読んでも全然面白くないと思いますよん。 Ｃ言語の言語仕様の隅を突いてコードを短くする技能ってのは完璧に趣味の領域に 属すると思いますが、それとは別の「短く簡潔に書けるアルゴリズムを考える」能力の 方は、普段からわりと重要なのではないかという気もします。単純な話、コードの量が 少ないほど、バグの元も少ないわけで。例えば今回の問題を解くためだけに、自分 でTreeクラスを定義してそれを生成するpars
ゆの 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. 文字コード＆ベイズ推定
12:21 06/05/28 うたひめ 先日の記事に書いたように KOKIA にハマりまして、 とりあえず片っ端から聴いてみることにしました。まずは 1st アルバムの 『songbird』 から … …４曲目の "白い雪" ヤバい。超ヤバい。なんだこれ。ツボすぎる。 ベスト盤を聴いたとき感じた揺らぎなく落ち着いた歌唱力的な曲を期待して聴きはじめたら、 予想外の声質の歌が飛び込んできてびっくりしました。もちろん抜群に巧いのに かわりはないんですが、ずっと儚げな、ガラス細工みたいなイメージの、ああ、その、 つまり白い雪みたいな雰囲気の綺麗な声で。その声と奇跡的にマッチしたメロディ。 すごいなあ。９曲目の "ありがとう…" もベスト盤でのリテイクと比べて同じ印象で、 Amazonのreview で TenderBerry さんという方が近いことを書いておられました。 しかし書いてて自分の語彙の
d.y.d.おもしろいみろん
13:33 08/06/29 RSS of kmonos/wlog moved! http://www.kmonos.net/wlog/index.rdf いや、移動したのは15ヶ月前なので、すでにご存じの方は華麗にスルーしてください。 「ここのRSSが文字化けしてるよー」という方だけ、↑に登録変更していただけると、 直るかと思います。お手数おかけしてスミマセン。定期的に「文字化けってる」という 指摘を見かけるので再度ブロードキャストです。こう、辛辣な評議会とかで怒られそうですけど、 諸般の事情により古い方からリダイレクトかけるの難しいらしいのだよね… それはそうと、昨日の記事に追記しました。 10:26 08/06/28 Logic ∩ CS 検索してたらたまたまヒットした "On the Unusual Effectiveness of Logic in Computer Scienc
Structural C++ - d.y.d.
19:05 08/05/31 本 私が一番好きなSFと言えば『百万年の船』ですが、 昨日読んで『タウ・ゼロ』が二番目に好きなSFに なりました。最近本の感想が大袈裟です。このどうしようもなく取り返しのつかない方向に お話が突っ走っていくっぷりが楽しい。あと、私が感情移入する気になれる主人公ってそうそういない。 いやそれはともかく、 まだこの二冊しか読んだことないのですけど、どうも自分はポール・アンダースンを読み漁るべきっぽいな。 UTPC UTPC というのに参加してました。 みんな解いてるから解けるはず！と思って挑み続けた E が結局解けずじまいでした。 うわーん。K かせめて H に時間使うべきだった。しかし若者勢とロートル勢のバランスが絶妙だ。 → 提出物一式。 13:58 08/05/29 ICFPの ICFP Programming Contest のページが更新されてました。
d.y.d.構文解析の話をしよう
16:46 08/03/30 YZ1.DLL 0.30 リリース しました。 具体的には、ヘッダの格納ファイル数フィールドに実際より大きい値が入ってると変なとこ読もうとして落ちるバグ修正。 GreenPad の修正は来週くらいには…。 Booooooost Boost 1.35.0 来てました。 Asio と Fusion と GIL の三枚看板がでかいですが、Bimap が地味に便利だ。 あと、mbさんのEgg のレビューが明日からでしょうか。（また スケジュール から消えてますが…Protoが入る前までロールバックしてる？） 他人事ながらドキドキ。 17:36 08/03/28 ケース 十年来の疑問なんですが、"case" に単独で対応する日本語ってなんになるんですかね。 "case-insensitive" や "lowercase" の "case"。単に "case-insens
d.y.d. Pluggable Type Systems
19:27 08/02/29 不動点ふたたび LtU で "Data Types a la Carte" を読みました。これの鍵となる技は「型コンストラクタに対する不動点演算子」だと思うのだけど、 あれ、なんで俺これ考えたことなかったんだ…？と不思議に思うくらい楽しげなアイデアですね。てい。 // 不動点演算子 via テンプレート。Dで。 // // Haskell でいう"普通の"不動点関数 fix f = f (fix f) と同じようなもの // = の代わりに継承になっちゃってますけど、まあ似たようなものです class Fix!(alias F) : F!(Fix!(F)) {} 不動点演算の実装は本題ではないので、Yコンビネータみたいな無駄な複雑化はしない方針で。 さて、これを使って class Pair(T) { T left; T right; } ２個同じ型の値のペアを
Home - プログラミング言語 D (日本語訳)
#!/usr/bin/rdmd // Computes average line length for standard input. import std.stdio; void main() { ulong lines = 0; double sumLength = 0; foreach (line; stdin.byLine()) { ++lines; sumLength += line.length; } writeln("Average line length: ", lines ? sumLength / lines : 0); } Standard input Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris tristique rutrum sem, nec convallis enim bibe
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
