はてなブックマーク

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さんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっか

22:43 21/11/09 ヒープソートが好きである ranha さんが、 Approaching Heapsort via Lazy Mergesort という記事を公開していらして、 遅延評価の言語で書くマージソートの計算過程で何が起きているかを見ていくと、 だんだんヒープソートが見えてきた…！という大変面白い記事なのですが、 その話の枕に「稲葉さんというヒープソート大好き人間がいるがいったいどこが良いのか」 という形で私が登場していたので、 思わず何故私がヒープソートが好きであるかをしたためた長文をTwitterのDMで ranhaさんに送りつけてしまいましたという経緯があります。 元ネタの @pi8027 さんの発表 が公になったのに合わせてranhaさんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっか

21:24 18/06/02 TRICK 2018 (FINAL) ３連覇！ 世界の Rubyist が集う RubyKaigi というイベントに時々併設される、 TRICK というコンテストがあります。 「一番変なRubyプログラムを書いたヤツが勝ち」というコンテストです。 前々回（Rubyでいろは歌）、 そして 前回（Rubyで円周率覚え歌） と、なんとも驚いたことに私が２回続けて優勝していたのですが、今年が第３回。 やりました。３連覇を達成しました！今回のネタは… 予約語テーブル 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 の３本立てです。 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

18:26 15/01/07 本: 2014年マイベスト12 去年読んで面白かった本の紹介タイムです。 マンガも技術書も小説もごたまぜです。 あと例によって自分が読んだ基準なので、 もっと昔に出版された本も混ざっています。むしろそちらの方が多いですね。 ベスト12なのは何故かというと10に絞りきれなかったからです。 レストー夫人 ベスト10に絞るのは悩んだけれどベスト1ならすぐに決まりました。 クラスの出し物の劇を練習する生徒達を描いた連作短編集…と設定を書いても特色はまったく伝わらないですね…。 なんだろう、自分は割となんでもホイホイ感動しちゃうタイプだと思うんですけど、 中でも弱点として、明確に登場人物一人のセリフなのに、 そこまでの物語の積み重ねを考えると幾人もの言葉として読めてしまう、 みたいなシーンが好きすぎて。 この短編集もどのお話も良いのだけど、 特に「度を過ぎて無口すぎる子

21:15 14/07/28 ICFPコンテスト2014 今年も ICFPプログラミングコンテスト に参加していました。72時間耐久好きな言語で好きにやれコンテスト。今年の課題は SECDマシン で動くパックマンAIと、簡単な仮想のアセンブラ言語255命令以内で動くパックマンの敵モンスターAI を作れ、という課題でした。 パックマン側とモンスター側を入れ替えて戦って対戦してスコア勝負というトーナメント。 今年は @phoenixstarhiro と @fuqinho の３人チームで参加しました。 コンテスト中に使っていたレポジトリは https://github.com/fuqinho/icfpc2014 です。言語は基本的に C++。 やったこと（自分視点） -3:00 ～ 0:00: 会社の出張が入ってしまったので羽田空港まで歩き旅。 1:00 ～ 3:00: 空港について問題を読んだ

何度も訊かれる質問が増えてきので、 FAQ を用意しました。 D 1.0 FAQ C++ FAQ D 2.0 FAQ D 2.0 と D 1.0 の違いは？ 「シンプルな言語」はどこに行っちゃったの 他にどんなクールな機能が D 2.0 には予定されてるんだい？ 僕が提案した最高の機能が無視されているのはなぜですか！ なぜ const や immutable なんてものが必要？ なぜ const や immutable なんていう 名前 なの？ immutable と マルチコア の関係を正確に述べてください OK、スレッド間の安全なデータ共有におけるimmutableの利点はわかった。でもそういう意味での情報量のないconstがなんで必要なの？ なぜ D 2.0 では immutable 文字列が好まれるのか？ D 2.0 に貢献したいです。どうすればいいでしょうか？ なぜ case r

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 という、プログラムの"お前はなにをやっているんだ度"を競うコンテストに出してみたら優勝してしまいました。 やった！ 簡単な解説 「各文字を１回しか使わない」 という制約が真っ先に効いてくるのは、 これすなわち、 １個の変数を１度しか使えない、 とい

(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++ の

Cute Algorithms! 稲葉 一浩 at #spro12 SLOWEST SORT まずは準備運動です！ Thanks to: @y_benjo @rng_58 @hos_lyric @oxy @xhl_kogitsune @args1234 アルゴリズムと言えば！ ソート！ Radix Sort Merge Sort Bubble Sort Heap Sort Insertion Sort Quick Sort Shell Sort ソートと言えば！ Radix Sort Merge Sort Bubble Sort Heap Sort Insertion Sort Quick Sort Shell Sort O(n log n) ! では、逆に・・・ ソートの「遅さの限界」は？ 一番たくさん大小比較を実行するソート法は？ 最遅ソート!? 「最も遅い」ソート法は？ • よくある

23:04 12/07/16 ICFP Contest 2012 この連休は、毎年恒例 ICFP Programming Contest に出ていました。 ソースコード置き場。 今回のお題は Boulder Dash っぽいゲームのAI書けというものでした。ただしダイヤモンドではなく「λ」を回収します。 見た瞬間に、えっ無理だろそんなの、と思って思わず旅に出たくなってしまったりしていましたが、 やってみるとそれなりに手はあって、結局３日間ちまちまと改善を続けていました。 と言っても結局パッと思いつくことしかできていない…。 基本的に貪欲アルゴリズム。（幅優先探索で）一番近いλに向かって直行、を繰り返す。 ただし岩の下にあるものを取ると盤面を崩壊させる恐れがあるので、そこだけ微妙に距離をおく たどり着けるλも出口もなくなったら、土をどけたり岩を押したり色々してみる。 が基本方針で、ただしこれ

データ構造やインターフェイスを調べるときには、 どのデータが不変でどのデータが可変で、変更を行う可能性があるのは誰か、 といった情報が簡単にわかると非常に便利です。 そしてこれは、言語の型システムの助けによって実現することができます。 データは const あるいは immutable とマーク付けすることができ、 デフォルトでは変更可能 (mutable) となっています。 immutable は、 一度構築されたら決して変更されることのないデータに適用します。 immutable なデータ値は、 プログラムの実行中一貫して同じ値であり続けます。 immutable なデータは ROM (Read Only Memory) や、ハードウェアによって読み取り専用とされたメモリページに配置することができます。 immutable なデータは決して変更されないので、 さまざまなプログラム最適化

競技プログラマ向け 形式言語理論 入門 稲葉 一浩 JOI 春合宿 2012 文字列やツリーやグラフの 集合 について考える分野 「形式言語理論」とは 文字列やツリーやグラフの 集合 を、どうやって表現するか について考える分野 「形式言語理論」とは 文字列やツリーやグラフの 集合 を、どうやって表現するか について考える分野 「形式言語理論」とは 今日は 文字列の集合だけ 扱います 文字列やツリーやグラフの 集合 を、表現するデータ構造 について考える分野 「形式言語理論」とは #include <set> #include <string> std::set<std::string> ？ 文字列やツリーやグラフの 無限かもしれない集合 の、有限のメモリでの表現 について考える分野 「形式言語理論」とは {“”, “a”, “aa”, “aaa”, “aaaa”, ...} 「長さが

www.kmonos.net Python と プログラミングコンテスト 稲葉 一浩 (k.inaba) http://www.kmonos.net/ www.kmonos.net 超特急自己紹介  言語ラブ（浮気性）  C++, JavaScript, D, Java, PHP, OCaml, Icon, Haskell, Erlang, Ruby, Python, …  「みんなのPython」  で Python はじめました  柴田さんありがとうございます  つまり超初心者(Python歴3ヶ月)  ”ビギナーのPython体験記” www.kmonos.net プログラミングコンテスト？  めちゃくちゃ色々種類があります  今日は特に 短時間で“Algorithm Quiz”を解くコンテスト Google Code Jam ACM/ICPC Sphere

20:25 12/02/10 TLE 2k12 優勝しました。 TLE とは何かというと、毎年この時期に、インドの IIIT-H 大学 の学祭の一環として（たぶん）開催されてるC言語ショートコーディングコンテストです。 過去の感想 → '09, '10, '11。 コードというのは時間をかけて睨んでいればいつの間にか短くなるものなので、 平日で忙しそうなライバル達を横目に代休とって丸一日コードを睨む、 という富豪的作戦が功を奏しました。 ⇒ 提出したソースコード 問題はまだオープンになってないようですが、だいたいこんなの。例年とあまり変化なかった（ので少し拍子抜け）。 BST: 二分探索木に指定の入力値列を突っ込んだ最終状態を表示する COMPOSITE: 自分自身のソースコードのうち素数じゃない位置にある文字だけ表示する変種Quine HASHING: 入力された文字列のバイト値の総和を

スタートC language面白論文紹介&読み会 発表者: kinaba 面白い論文が 見つからなかった ので 捏造 Towards Higher-Order Syntax of C Programming Language なぜか。 Cの文法は文脈自由ではないと言われる なぜか。 Cの文法は文脈自由ではないと言われる FILE *fp; width * height; n = (size_t)*ptr; f = (m) * a; strdup(*argv)[9]; byte (*bufs)[9]; puts(str); clock_t (t); すごくどうでもいいんですけど、いろいろ面白いですね。 (a(*)(b))*c; (a)*b*c; (a*)b*c; (a*b)*c; (a*b*c); a(*b)*c; a(*b*c); a*(b)*c; a*(b*)c; a*(b*c); a*