サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
衆院選
www.kmonos.net
21:42 11/09/12 一番下に追記あります。 最遅ソート 最遅ソートアルゴリズム研究会 (beyond the bogosort) http://twitter.com/#!/y_benjo/status/112915204546887680 というつぶやきを見て、最も遅いソートアルゴリズムは何だろう、ということが気になりはじめました。 もちろん Bogosort や Stooge sort や Permutation sort は遅いです。遅いんですが、これらのソートアルゴリズムは、 明らかに完全に無駄な操作を繰り返すことで時間を稼いでいる面があります。これはズルい。チートです。 ズルくなくて、しかも遅いアルゴリズムは何でしょうか。 フォーマルに 自分の疑問をきちんと定義します。 wikipedia:比較ソートの理論限界 にあるように、「比較演算の回数」に着目することで、最速のソ
00:41 11/08/04 計算のきまり ( )を使った式の計算には次のようなきまりがあります。 （□ ＋ ○） × △ ＝ □ × △ ＋ ○ × △ （□ － ○） × △ ＝ □ × △ － ○ × △ ... たし算とかけ算には、次のようなきまりがあります。 □ ＋ ○ ＝ ○ ＋ □ （□ ＋ ○） ＋ △ ＝ □ ＋ （○ ＋ △） □ × ○ ＝ ○ × □ （□ × ○） × △ ＝ □ × （○ × △） この考えを使って、くふうして暗算で計算しよう。 小学校算数 5学年 - Wikibooks 分配法則・交換法則・結合法則。 とても当たり前で、当たり前すぎて、ほとんどの人は、もう特に意識することもない法則かもしれません。 でも、プログラミングを知っている僕らは、立ち止まってこの法則の価値に触れることができる。 末尾再帰化 最近のコンパイラは、こんな最適化をします。 i
00:07 11/07/28 LOPSTR / PPDP 2011 LOPSTR と PPDP という共同開催の国際会議に行っていました。論理に基づく / 宣言型のプログラミングがテーマだそうです。 実況は例によって togetter.com/li/164644 にまとめてあります。 LOPSTR の方は、あまりよく知らなかったんですが、発表を聴いてみると、かなりガッツリと Prolog の言語仕様のディープなところに触れるような話があって、まるで、 C++ や Scala で盛り上がってる自分のTwitterのタイムラインの Prolog 版を見てるような雰囲気で楽しかったです。 Sloth 聴いた中では Sloth という Haskell のライブラリの話が一番面白かったので、帰ってから関連論文を読んでいました。 何をするライブラリかというと、書いた関数が「できるかぎり遅延評価する」も
22:15 11/06/27 ICFPC 2011 ここ 8 年くらいほぼ毎年参加していた ICFP Programming Contest ですが、今年は出題者側に回ってみました。 問題の原型決定の議論、画像に変なネタを仕込む、Windows版バイナリのビルドをする、対戦サーバの中身を突貫でどうにかする、 などなどをしていました。 ゲームのバランス調整が非常によくできていたとの評価を頂いているのですが、 肝心のその辺りは、出題チーム内の熟練者達の高度な議論に既についていけなくなっており、 私は全然貢献できていないという…。 詳しいことは 9 月の ICFP で発表があると思いますので、ここでは今年のテーマの紹介だけ。 公式の問題文はこちら です。 一言でいうと、関数を呪文に変えて撃ち合う、プログラミング魔法バトル。 Lambda: the Gathering L:tG という２人対戦ゲー
22:42 11/04/10 D言語会議 http://partake.in/events/feac18f7-0b78-4129-92c5-ad0cce8feafb 行きました。とりあえずDに興味がありそうな人を一カ所に集めるから後は好きにしろ、 的な repeatedly さんらしい豪快な集会でしたが6時間ずっと部屋中盛り上がっていて面白かったです。 僕は toHash/getHash 周りの話（後述）を、誰か捕まえて議論しに行こうと思っていたはずなのですが、 問題であると僕が思うコードを人に説明するだけしてネタを振った辺りで突然飽きて、 他のことをずっとやっていました。ザ・無責任。 他のことというのは、半年ちかく前に見つけた Issue 5184 - throw ClassName.templatedStaticMethod(...) cannot be parsed このバグです。な
17:35 11/02/14 TLE '11 変則コードゴルフ大会 TLE に参加していました。 7位でした。無念…。終了１時間前には3位だったんですよ！（言い訳） 問題はこちら です。 自分のソースコードは sub/TLE11 こんな感じでした。 以下、ネタバレ感想など。 短いコードが知りたい方は 優勝者の解説 をご覧あれ。 COUNTI 自然数 i が入力されたら、「自分のソースコードの i バイト目に出てくる文字は、 自分のソースコードの中に、何回出現するか」を出力しよう。できるだけ短いコードで。 基本的にゴルフ大会なので、どの問題も短く書ければ短いほど点数が高いです。 main(){...いつでも4を表示するコード...}//どの文字も4文字ずつになるよう足りない字をここで補充 というのを即座に思いついて、submit 開始直後に投入。 したら、主催者さんがこれでは面白くないなーと
3-b5. wxD で GUI プログラミング 初出: 2007/03/07 最新: 2007/03/07 [3. D言語各論] に戻る wxD とは wxD とは、 wxWidgets をD言語から使えるようにしたGUIライブラリです。 D言語向けのGUIライブラリは数多く開発されていますが、その中でもwxDは マルチプラットフォーム対応 (Windows, Linux, MacOS 等) UTF-8 をきちんと扱えている 開発がちゃんと続いている という点で一番安心して使えそうというのが私の感想です。そんなわけで、ここでは wxD の使い方を紹介していきます。 他に その他に完成度の高いGUIライブラリとしては、 DFL: Windows専用。 Entice Designer というGUIビルダー付き。開発は長期間活発。 完成度も高く、マルチプラットフォームにこだわらないならば、 もっ
09:25 10/12/31 年末まとめ 今年何やったっけ、と日記を読み返していました。何もやってないな…。 Polemy 作りました、くらい。 言語処理系作るのはやっぱり楽しいですね。 汎用言語として使う本格的なものを作ろうとすると懲りすぎて一歩も進まなくなってしまう自分が見えるので、 来年は、そうだなあ、TopCoder/ICPC風コンテストに特化した言語というかC++へのトランスレータ、 くらいに絞って作ってみようかなあ。 書いた記事だと 最短性チェックの話 が自分では割と気に入っています。 これのもっとバグを許容するバージョン作れないか。 読んだ論文で面白かったのは "A Pearl on SAT Solving in Prolog" と "When Simulation Meets Antichains" (PDF) など。 あとは、今年読んで面白かった本ベスト５（順不同）： 『
Welcome to Polemy programming language! Latest Source Code (click "ZIP archive" in the page) Windows Binary 2010-Dec-05 Documentation (in Japanese) is here: Reference Manual Slides (PPTX, PDF) at metaprogramming_meeting Source code is managed on fossil SCM. The repository URL is: http://www.kmonos.net/repos/polemy.
22:27 10/10/06 ICFP 2010 International Conference on Functional Programming に行ってきました。 Haskell や OCaml や Scheme や Erlang 等々「関数型プログラミング言語」の研究の国際会議です。 延々と twitter で実況つぶやきしてたのを ICFP 2010 実況など にまとめましたので、どんな発表があったのか興味のある方は、そちらをどうぞ。 自分にとって特に面白かった！というベスト３は、この三つかなあ。 VeriML: typed computation of logical terms inside a language with effects 「証明を書けるプログラミング言語」は素晴らしいのですけども、 そんなに大変でないように思える証明でも、書くと、想像以上に長くなってしまう
22:56 10/09/04 階乗を求める 去年聞いた中で、私が一番感動した式の話。 k! = limn→∞ nk / nCk kの階乗は、「nのk乗 ÷ n個のものからk個選ぶ組み合わせの数」という式で n を無限に大きくしていったときの収束先、である。 特に難しい証明が要るとかではなくて、nCk = n(n-1)(n-2)...(n-k+1) / k! であることを使うと、 limn→∞ nk / nCk = limn→∞ nk k! / n(n-1)(n-2)...(n-k+1) で、n が k に比べて十分大きければ n も n-k+1 もほとんど同じ値なので、 分子も分母もだいたい n を k 個かけているわけでして、 その部分が相殺して、k! が残るという寸法。 （厳密な表現ではないので、気になる人は厳密に証明してください。） 実装 と、この式自体はそんなに不思議ではないのです
abstract 必要なヘッダ <boost/property_tree/ptree.hpp> (メイン) <boost/property_tree/xml_parser.hpp> (XML読み書き) <boost/property_tree/json_parser.hpp> (JSON読み書き) <boost/property_tree/ini_parser.hpp> (INI読み書き) <boost/property_tree/info_parser.hpp> (INFO読み書き) ... 出来ること 汎用木構造型コンフィグ管理 リファレンス en sample サンプルの動作確認バージョン [GCC4.4/1.42.0] [VC9/1.42.0] #include <iostream> #include <string> #include <boost/foreach.hpp> #i
sample サンプルの動作確認バージョン [GCC4.4/1.41.0] [VC9/1.41.0] #include <iostream> #include <boost/format.hpp> using namespace std; int main() { // %1%が一番目のパラメータ、%2%が二番目のに置き換わります。 cout << boost::format("%1% %2%") % "hello" % 100 << endl; // printfと同じ書式もOK。 // %05d:0埋めで5桁の整数 %x:16進表記 %f:浮動小数点数 %%:%そのもの cout << boost::format("%05d %x %f %%") % 200 % 255 % 3.33 << endl; // さらに、%2%と%1%を逆順に使うことも cout << boost::for
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%)となることがわかります
21:54 10/06/30 行列と項書換 "Termination of String Rewriting with Matrix Interpretations" という論文を読みました。 これは何かというとつまり、 ICFPコンテストの元ネタとして 紹介 されていた論文です。 れ い 年、 冗談９割で、主催者の専門分野にちなんだ問題が出るに違いない！と叫んでいるのですが、 本当に来るとは思わなかった…。 さて。項書き換え (term rewriting) と呼ばれる研究分野がありまして、 例えばこんな問題を調べています。 文字列に対して、「以下の操作のどれかを好きに選ぶ ＆ 実行する」を繰り返します。 abc という部分文字列を de に書き換える （abc ⇒ de と書きます） ef ⇒ g fgh ⇒ ij どんな文字列からスタートしても、最後には、どの規則も使えない状態 （つ
Phobos は、D言語のコンパイラに付属する標準ランタイムライブラリです。 PhobosのWiki も合わせてご覧下さい。 設計方針 Phobosのどのモジュールも、 できる限り次の目標に適合するように書かれています。 ここに上げる項目は要求ではなく、あくまで目標です。 Dは宗教ではなくプログラミング言語ですから、時には、 定めたゴールが矛盾していたり非生産的になる場合があることを認識しています。 そして、 そんな時でもプログラマは仕事を進めないといけません。 マシン・OS 非依存なインターフェイス 移植性のないコードを理由もなく書くのは避けよう、 という標語は広く受け入れられています。これはしかし、 OSの一般的でない機能へのアクセスを防ぐべき、 と解釈するのは間違いです。 簡単な処理は簡単に byteの配列をファイルに書き出す、 と言ったよく使う簡単な処理は、 簡単なコードで書けるべ
23:41 10/05/27 mm.exe いつものようにチェスでもするかと、 Windows Vista のスタートメニューの「ゲーム」フォルダを開いてみると Stream: Dark Messiah Might and Magic :Single Player という見知らぬタイトルのアイコンが転がっていました。 こんなゲーム入れた覚えないので、 これはゲームの振りして起動させようとするトロイの木馬か何か入れてしまったか…と青くなりながら調べてみると、 こんな2chでの書き込みが引っかかりました。 【DMMM】 Dark Messiah of Might and Magic その7 147 ：UnnamedPlayer：2010/05/23(日) 01:37:15 ID:V/DFzC7D 先ほど知らないうちにWindows 7 (64bit)のゲームフォルダに Stream: Dark
A. 不要です。もちろん連絡して下さっても構いません。 自分の作ったソフトが広まっていくのを知るのは嬉しいことです。
20分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ イ ミ ュ ー タ ブ ル デ ー タ 構 造 は 遅 い Immutable Object だけで作るデータ構造 この本の 内 容を 全速力で 布教する お題：キュー (Queue) • FIFO (First-In First-Out) • pushBack(e) でデータeを入れる • popFront() で取り出せる • 入れた順に出てくる • 以上 破壊的キュー Immutable Object でない 打倒すべき目標 代 入 手続き型でよくある interface Queue<E> { void pushBack(E e); E popFront(); } よくある実装 1 2 3 ・ 4 ・
00:46 10/04/23 EDBT/ICDT 2010 先月 EDBT/ICDT 2010 という学会に行ってきたのですが、それについて何も書いてなかったので今頃書きます。 自分より一ヶ月後に同じローザンヌに行って噴火に巻き込まれて帰国まで延びてしまっているみずしまさんがお帰りになるよりは早く書かないと的気分がなきにしもあらずです。 データベースの会議なんですが、 こちらの分野は SIGMOD/PODS の流れで、 実装寄りの会議と理論よりの会議を合わせて共同開催するブームらしい。 参加者としては、色んな幅広いトークが聴けるのは単純に楽しいので、もっと広まると面白そうだなあと感じました。 プログラミング言語で言うと PLDI/POPL とするみたいなものでしょうか。 それが良いかどうか判断できるほどPLDIの方の雰囲気を知らないのでわかりませんが。 オートマトン方面だと CIAA/DL
20:19 10/03/06 PPL 2010 参加記 第12回プログラミングおよびプログラミング言語ワークショップ に行ってました。 お茶大のshift/reset推進委員会に対抗できる勢いでtree transducer勢が活躍していて素晴らしいことです。 それはともかく、面白かった発表をいくつかメモ。 『極性をもたないセッション型システム』。 セッション型（…とは何かはご本人のブログの解説をどうぞ）の既存の型システムは、チャンネルの自由な受け渡しを禁止した制約のあるものか、 極性という概念を入れてややこしくしたものか、どちらかだったそうなのだけど、そういう制限を無くせました！ という結果だそうな。個人的に面白いなーと思ったのは、型システムの健全性 （＝「型チェック通ったプログラムは実行時型エラーを起こさない」）の証明のために、 よくある type preservation (式eに型
sample サンプルの動作確認バージョン [GCC4.4/1.43.0] [VC10/1.43.0] #include <vector> #include <iostream> #include <boost/intrusive_ptr.hpp> using namespace std; namespace my { class SharedObject { private: SharedObject() : ref_count(1) {} public: static SharedObject* create() { return new SharedObject; } int AddRef() { return ++ref_count; } int Release() { if( 0 == --ref_count ) { delete this; return 0; } return
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 =
Books 理論計算機科学事典 (5.4 MSO 論理とMSO 変換) 純粋関数型データ構造 (Japanese Translation of "Purely Functional Data Structures" by C. Okasaki) Google Maps API 徹底活用ガイド Boost C++ Libraries プログラミング Papers Papers on the same line of research are colored by the same color. See also DBLP / GoogleScholar / MS-AcademicSearch / CSAuthors. Unpublished Drafts and Preprints [arXiv] Quick Brown Fox in Formal Languages K. Inaba [P
17:31 10/01/26 言語雑談会 言語雑談会 なるものに行ってきました。 自分は主に最近のD言語の話題 [PDF] [PPTX] についてと、 最近読んだ Pattern Calculus がイマイチ心に響かなかったという話と、 これも最近読んだ Prolog で SAT ソルバ という論文が格好良すぎて卒倒しそうです、などの話題を雑談していました。 SAT の話をしていてふと突然気づいたんですが、私が今までSATソルバに落としてみたことのある問題は、 すべて割と簡単に CNF（SATソルバがそのまま食べてくれる綺麗な形式の論理式） ができあがる問題だったようです、数独とか。 任意の命題論理式をCNFに変換できる指数爆発しない方法をそういえば知らないぞ俺！としゃべってたら soutaro さんが素晴らしい解説 をして下さいました。ありがたや。 あと shinhさんの 「コンピュータ
13:54 09/12/31 年末まとめ 今年何をやったことや読んだものを振り返ろうと思います。 恒例のゲーム報告から行くと、 万歩 と 深遠HA クリアしました！ その後他のダンジョンには潜ってないけど、何かまたそろそろ始めようかな…。 ／ プログラミング関係は、ハッカソン的なもので 何個か 小ネタ を仕上げただけで、 ちゃんとしたものは作ってないですね。困った困った…。 どっちかというと、勉強会的なイベントで発表するネタを考える方が多かった。 特にFLTV での "真・自然言語プログラミング" の発表内容は割と個人的に会心の出来なのですが、多くの方に好評いただけたので嬉しいです。 なんだかもう、しばらくの間は、私はそういうキャラということでいいのではないかと思い始めてきました。 ものを作ることに全力をかけている人は多いけれど、 「一見難しく見えることをいかに簡単に噛み砕いて見せるか」を
sample サンプルの動作確認バージョン [GCC4/1.39.0] [VC8/1.39.0] #include <iostream> #include <string> #include <boost/asio.hpp> using namespace std; using namespace boost::asio; int main() { // www.boost.org の http サービスに接続 ip::tcp::iostream s( "www.boost.org", "http" ); // 送信 s << "GET / HTTP/1.0\r\n"; s << "Host: www.boost.org\r\n"; s << "\r\n"; s << flush; // バッファに溜めずに確実にネットワーク送信 // 受信 string line; while( getl
21:23 09/11/29 ドラクエ３ ドラゴンクエスト III モバイル版 が配信開始されたと聞いてはプレイせずにはいられない、ということで、さっきクリア。 内容は 「SFC版のベタ移植 - すごろく場 + AI戦闘」 ですね。 すごろく場が減った分、限定アイテムが他の場所に移動 （パワーベルト・ドラゴンテイル・ドラゴンローブ・グリンガムのムチが小さなメダル賞品に。 光のドレスがゾーマ城の宝箱に。雷神の剣も宝箱だった気がする。あと、小さなメダルの総数が110枚で変化無しらしいので、 すごろく場にあった分が通常マップに押し出されて、ところてん式に押された炎のブーメランもメダル賞品化）。 不思議なボレロと女神の指輪は見てない。なくなった？ AIは、マヌーサ/ラリホー/マホトーン辺りを効く相手にだけ積極的に使ってくれるので参考になる＆便利。 勇者もAI駆動にできるモードが欲しかった 細かいと
01:29 09/10/28 七不思議HA 七不思議ハードオオイカリパッチ深遠100F到達しました。 やった！ （→ リプレイファイル） サブ剣に 日本刀[封必－脱封守]+17。盾は深層で[潰][爆][祓]を順次追い出して左のスクリーンショットが最終形。 [冷]も消してよかったな。保存の壺フィーバーが来たのでなんとかクリアできた感じでした。 普通の引きだと70F前後で大抵力尽きる。 普通にバランスのとれてるノーマル版に、 ・シレンで言うところのカンガルー３種を投入し ・主人公LVアップ時のHPと攻撃力の上昇量を減らし ・床落ちアイテム数を減らし敵のドロップ率も減らし、 たらどうなるでしょうかというパッチ。このゲーム4倍速まで上がるのでオオイカリ状態がより一層ヤバい。 代わりに幾つかの印の効果が強化されてて、レアアイテム出現率がやや上がっているので、 その辺りを鍵に頑張ることになります。 ト
次のページ
このページを最初にブックマークしてみませんか？
『Kazuhiro Inaba』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
