サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
災害への備え
www.kmonos.net
22:22 21/11/20 ボレロ村上(村上原野)さんと constexpr のこと 去る2020年2月、縄文陶芸家にしてC++プログラマという希有な二つの顔を持つ人物がこの世を去りました。 ボレロ村上 (村上原野) 氏です。 正直なところ、陶芸家としての彼の側面については私はほとんど何も知らないに等しいです。 残された作品を見て何かを語れるほど芸術に通じているわけでもありません。 いつか機会があれば見に行こうと思っていた村上さんの作品を目にする最初の機会も、 昨年訪れた追悼展になってしまいました。 ただ、それでも私は、彼自身の登壇発表の資料 であったり、 そして何よりも縄文・陶芸に造詣の深い方々の記された幾つかの文章によって、 彼が一体何を成し遂げたのか、成し遂げようとしていたのかに触れることができています。 この夏にはクラウドファンディングで 作品集 も出版され、誰でも手にとって縄文
22:43 21/11/09 ヒープソートが好きである ranha さんが、 Approaching Heapsort via Lazy Mergesort という記事を公開していらして、 遅延評価の言語で書くマージソートの計算過程で何が起きているかを見ていくと、 だんだんヒープソートが見えてきた…!という大変面白い記事なのですが、 その話の枕に「稲葉さんというヒープソート大好き人間がいるがいったいどこが良いのか」 という形で私が登場していたので、 思わず何故私がヒープソートが好きであるかをしたためた長文をTwitterのDMで ranhaさんに送りつけてしまいましたという経緯があります。 元ネタの @pi8027 さんの発表 が公になったのに合わせてranhaさんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっか
21:24 18/06/02 TRICK 2018 (FINAL) 3連覇! 世界の Rubyist が集う RubyKaigi というイベントに時々併設される、 TRICK というコンテストがあります。 「一番変なRubyプログラムを書いたヤツが勝ち」というコンテストです。 前々回(Rubyでいろは歌)、 そして 前回(Rubyで円周率覚え歌) と、なんとも驚いたことに私が2回続けて優勝していたのですが、今年が第3回。 やりました。3連覇を達成しました!今回のネタは… 予約語テーブル Ruby の言語仕様のページに、 予約語の一覧を表にしたものがあるんですよ。これです。 これの真似をして予約語を並べてみました、というのが今回の作品です。 alias BEGIN for unless def class super true or return defined? next break wh
21:30 16/01/28 2015年に読んだ面白論文紹介場所参加記事です。 例によって、2015年に発表された論文とは限りません。私が去年読んだ中からの選抜です。 また例によって、人類の科学史における重要性とかそういったことに興味はないので、 単純に自分にとって読んで面白かった、これを読む前と後では物事の考え方が変わったなあ、 と思った論文を選んでいます。 ☆ Newtonian Program Analysis ☆ Quick Detection of High-degree Entities in Large Directed Networks ☆ An Axiomatic Characterization of the Hirsch-Index の3本立てです。 Newtonian Program Analysis In Journal of the ACM, 2010. [著者
21:26 15/12/11 円周率おぼえ歌 in Ruby 円周率 π = 3.14159265... を語呂合わせで 「産医師異国に向こう…」 として覚えるみたいなのありますよね。 英語では Piphilology と言って、たとえば、こんなの。 How I wish I could recollect pi easily today... 長さ 3 の単語 (How)、長さ 1 の単語 (I)、長さ 4 の単語 (wish)、… という列で数字の列を覚えたりするそうです。 この方式だとゼロの桁の表現に困りそうですが、ゼロの所には巧みに句読点などの記号を配したり、 あるいはもう少し単純に、長さ 10 の単語を当てて表すのだそうな。 と、いうわけで。 in Ruby 長さ 3 のトークン、長さ 1 のトークン、長さ 4 のトークン、 長さ 5 のトークン、長さ 9 のトークン、長さ 2
23:10 15/08/12 ICFP Contest 2015 今年も ICFP Programming Contest に参加していました。 今年はチーム名 "Natsubate!" で @nya3jp, @phoenixstarhiro, @chunjp, @gusmachine, @riesz と私の6人チーム。 チームのレポジトリは https://github.com/nya3jp/icfpc2015。 使用言語は C++ (メインのソルバー) Python (ソルバー群の制御や諸々のスクリプト) JavaScript (可視化や人間用UI)。 公式の スコア表 曰く予選ラウンドの順位は6位とのことです。 今年の問題は、基本的にはテトリスのAIを書けという問題でした。ただし 1ブロックが正方形ではなく正六角形の六角テトリス。 4つ繋がりのミノに留まらず、かなり好き勝手な形の塊が
18:26 15/01/07 本: 2014年マイベスト12 去年読んで面白かった本の紹介タイムです。 マンガも技術書も小説もごたまぜです。 あと例によって自分が読んだ基準なので、 もっと昔に出版された本も混ざっています。むしろそちらの方が多いですね。 ベスト12なのは何故かというと10に絞りきれなかったからです。 レストー夫人 ベスト10に絞るのは悩んだけれどベスト1ならすぐに決まりました。 クラスの出し物の劇を練習する生徒達を描いた連作短編集…と設定を書いても特色はまったく伝わらないですね…。 なんだろう、自分は割となんでもホイホイ感動しちゃうタイプだと思うんですけど、 中でも弱点として、明確に登場人物一人のセリフなのに、 そこまでの物語の積み重ねを考えると幾人もの言葉として読めてしまう、 みたいなシーンが好きすぎて。 この短編集もどのお話も良いのだけど、 特に「度を過ぎて無口すぎる子
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]の位置にあった、 ということを意味しています。(上のソート
21:15 14/07/28 ICFPコンテスト2014 今年も ICFPプログラミングコンテスト に参加していました。72時間耐久好きな言語で好きにやれコンテスト。今年の課題は SECDマシン で動くパックマンAIと、簡単な仮想のアセンブラ言語255命令以内で動くパックマンの敵モンスターAI を作れ、という課題でした。 パックマン側とモンスター側を入れ替えて戦って対戦してスコア勝負というトーナメント。 今年は @phoenixstarhiro と @fuqinho の3人チームで参加しました。 コンテスト中に使っていたレポジトリは https://github.com/fuqinho/icfpc2014 です。言語は基本的に C++。 やったこと(自分視点) -3:00 ~ 0:00: 会社の出張が入ってしまったので羽田空港まで歩き旅。 1:00 ~ 3:00: 空港について問題を読んだ
20:43 13/12/31 本 今年読んで面白かった本ベスト20。 自分が今年読んだ基準なので遙か昔に出版された本も多数含みます。 しかもジャンル分けもせず適当に混ざっています。 ここ数年読書メーターでまとめてたんですけど今年ないみたいだし、 本棚機能もログインしていないと見られないようになってしまったみたいだし、 こちらで。 カクリヨの短い歌 和歌を詠むとその歌に応じた異能が発動するという能力バトルもの…というと情緒が飛んでしまいますかね。 読み終わったときはそうでもなかったのだけど、後からじわじわ来て、気づいたらこの話のことばかり考えるようになっていました。なんというか、歌を、この歌に込められた思いはこう…等々ロジカルな解題として語ってしまうのは勿体ないと思うんですよ。たとえば一面の桜吹雪、たとえば夜咲く紫陽花の花、その景色をただ再現するだけ、その具象が聴き手に何かを感じさせたならそ
17:55 13/08/12 ICFPコンテストでした ICFP プログラミングコンテスト が終わりました。 今年は @nya3jp @phoenixstarhiro @dmikurube @kinaba の 4 人チームで参戦していました。 C++ で計算バックエンド、 Python でサーバーとのやりとりと計算モジュールをつないで答えを送りまくる最上位のロジックとフロントエンド、 という構成でした。 簡単なまとめ 今年の問題は、 『サーバーに1400個くらいプログラムが置いてあります。 プログラムは 64bit 整数を 1 個受け取って、 何か計算して 64bit 整数を 1 個返す関数です。 サーバーは、プログラムの番号と引数を指定すると実行して結果を返してくれます。 どういうプログラムが置いてあるのか、できるだけ沢山当ててみなさい!』 という問題。 当てた個数が多ければ多いほど好ス
01:19 13/07/06 ソートキラー改 ここまでのあらすじ: → ソートの実装を渡すと、 自動でその実装の苦手な入力を作ってくれる ソートキラーを作りました。 → でも遅い。元々のソート処理が O(f(n)) として O(n2 f(n)) 時間かかる。 → あっ O(n3 + f(n)) になった! …という最後のステップを、コードは書いたのだけど説明どこにも書いてなかったのでメモ書きです。 本当にメモ書きであんまりわかりやすく書いてないので、気になる人だけ読んで下さい。 あと、特にたいしたことではないのでアルゴリズム得意な人には自明だと思われます。 説明 古いバージョンも新しいバージョンも、やっていることの流れは、こうです。 要素xは要素yより {小さい,大きい,わからない} の3状態を記録した n×n の表を準備。 初期値は "わからない"。 ソート関数に「xはyより小さいですか
22:41 13/06/01 TRICK 2013 @ RubyKaigi いろは歌。 in Ruby. !@THEqQUICKbBROWNfFXjJMPSvVLAZYDGgkyz&[%r{\"}mosx,4>6]|?'while(putc 3_0-~$.+=9/2^5;)<18*7and:`# ということで、ASCII の制御文字じゃない部分、' ' (0x20) から '~' (0x7E) まで95文字をちょうど一回ずつ使って、 その95文字をちょうど一回ずつ標準出力に書くプログラムです。Ruby会議に合わせて開かれた TRICK 2013 という、プログラムの"お前はなにをやっているんだ度"を競うコンテストに出してみたら優勝してしまいました。 やった! 簡単な解説 「各文字を1回しか使わない」 という制約が真っ先に効いてくるのは、 これすなわち、 1個の変数を1度しか使えない、 とい
23:00 13/03/07 2012年に読んだ面白論文紹介場所 参加記事です。3本立てです。 ☆ 「博士の愛した数当て」 ☆ 「It's not Automatic.」 ☆ 「47」 博士の愛した数当て まず1本目は、STACS'12 から "Playing Mastermind With Constant-Size Memory"。 ぼくの記憶は 1ターンしか もたない ヒット&ブローあるいはマスターマインドというゲームがあります。 私が遊んだことがあるバージョンは 出題者が、0-9の数字を4桁並べた数を頭に思い浮かべる。 回答者が、その数を当てようとする。0-9の数字を4桁並べた数を「これですか?」と出題者に質問 桁も値もあってる数字が x 個、場所が違うけど値はあってる数字が y 個あったら「x ヒット y ブロー」と返事 以下繰り返し。4ヒットになったらお終い。 こういうルールで
(source) (日本語解説)
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した!!」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
19:39 12/09/01 クイックソート殺し こういう系統の話。 Quicksort Killer (kazoo04さん) qsortを撃墜し(最悪ケースを与え)てみた。 (qnighyさん) A Killer Adversary for Quicksort (shinhさんの解説) Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (徳丸さんの解説) ただのクイックソートは要素数 N の配列をソートするのに最悪 N2 オーダの時間がかかってしまう、 そしてそれは pivot を偏って選びまくってしまった時に発生する、というのはよく知られた話だと思います。 といっても、広く使われている言語/ライブラリのソート関数はその辺り気をつけられていて、最悪時も O(N log N) になるアルゴリズムで実装されている…と思い込んでいたのですが(例えば C++ の
23:04 12/07/16 ICFP Contest 2012 この連休は、毎年恒例 ICFP Programming Contest に出ていました。 ソースコード置き場。 今回のお題は Boulder Dash っぽいゲームのAI書けというものでした。ただしダイヤモンドではなく「λ」を回収します。 見た瞬間に、えっ無理だろそんなの、と思って思わず旅に出たくなってしまったりしていましたが、 やってみるとそれなりに手はあって、結局3日間ちまちまと改善を続けていました。 と言っても結局パッと思いつくことしかできていない…。 基本的に貪欲アルゴリズム。(幅優先探索で)一番近いλに向かって直行、を繰り返す。 ただし岩の下にあるものを取ると盤面を崩壊させる恐れがあるので、そこだけ微妙に距離をおく たどり着けるλも出口もなくなったら、土をどけたり岩を押したり色々してみる。 が基本方針で、ただしこれ
20:25 12/02/10 TLE 2k12 優勝しました。 TLE とは何かというと、毎年この時期に、インドの IIIT-H 大学 の学祭の一環として(たぶん)開催されてるC言語ショートコーディングコンテストです。 過去の感想 → '09, '10, '11。 コードというのは時間をかけて睨んでいればいつの間にか短くなるものなので、 平日で忙しそうなライバル達を横目に代休とって丸一日コードを睨む、 という富豪的作戦が功を奏しました。 ⇒ 提出したソースコード 問題はまだオープンになってないようですが、だいたいこんなの。例年とあまり変化なかった(ので少し拍子抜け)。 BST: 二分探索木に指定の入力値列を突っ込んだ最終状態を表示する COMPOSITE: 自分自身のソースコードのうち素数じゃない位置にある文字だけ表示する変種Quine HASHING: 入力された文字列のバイト値の総和を
23:21 11/12/22 今年読んだ面白コンピュータサイエンス論文紹介カレンダー 第 n (1<n) 週目モードです。 ☆ 「難しい問題」 ☆ 「名のない関数」 ☆ 「演算のせいしつ」 「難しい問題」 [5] R. Impagliazzo and L. A. Levin. "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random." FOCS 1990. ランダム生成に興味があります。 パズルゲームを作りました。 さて、手強い難易度の面データを無限にランダム生成するにはどうすればいいだろう。 プログラミングコンテストの問題を作りました。 さて、自動チェック用のテストデータをランダム生成するにはどうすればいいだろう。 適当なランダム生成では、簡単なケースばっかり作られてしまい 嘘解法 に突
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 という2人対戦ゲー
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位でした。無念…。終了1時間前には3位だったんですよ!(言い訳) 問題はこちら です。 自分のソースコードは sub/TLE11 こんな感じでした。 以下、ネタバレ感想など。 短いコードが知りたい方は 優勝者の解説 をご覧あれ。 COUNTI 自然数 i が入力されたら、「自分のソースコードの i バイト目に出てくる文字は、 自分のソースコードの中に、何回出現するか」を出力しよう。できるだけ短いコードで。 基本的にゴルフ大会なので、どの問題も短く書ければ短いほど点数が高いです。 main(){...いつでも4を表示するコード...}//どの文字も4文字ずつになるよう足りない字をここで補充 というのを即座に思いついて、submit 開始直後に投入。 したら、主催者さんがこれでは面白くないなーと
09:25 10/12/31 年末まとめ 今年何やったっけ、と日記を読み返していました。何もやってないな…。 Polemy 作りました、くらい。 言語処理系作るのはやっぱり楽しいですね。 汎用言語として使う本格的なものを作ろうとすると懲りすぎて一歩も進まなくなってしまう自分が見えるので、 来年は、そうだなあ、TopCoder/ICPC風コンテストに特化した言語というかC++へのトランスレータ、 くらいに絞って作ってみようかなあ。 書いた記事だと 最短性チェックの話 が自分では割と気に入っています。 これのもっとバグを許容するバージョン作れないか。 読んだ論文で面白かったのは "A Pearl on SAT Solving in Prolog" と "When Simulation Meets Antichains" (PDF) など。 あとは、今年読んで面白かった本ベスト5(順不同): 『
22:27 10/10/06 ICFP 2010 International Conference on Functional Programming に行ってきました。 Haskell や OCaml や Scheme や Erlang 等々「関数型プログラミング言語」の研究の国際会議です。 延々と twitter で実況つぶやきしてたのを ICFP 2010 実況など にまとめましたので、どんな発表があったのか興味のある方は、そちらをどうぞ。 自分にとって特に面白かった!というベスト3は、この三つかなあ。 VeriML: typed computation of logical terms inside a language with effects 「証明を書けるプログラミング言語」は素晴らしいのですけども、 そんなに大変でないように思える証明でも、書くと、想像以上に長くなってしまう
次のページ
このページを最初にブックマークしてみませんか?
『www.kmonos.net』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く