読者です 読者をやめる 読者になる 読者になる

プログラミング

lazy in Scala macro

めも lazy は macro 展開前に部分的に desugar される。ここからいくらか実装を察することができる。 展開前 lazy val a = 10 展開後 { lazy <artifact> var a$lzy: Int = _; <stable> <accessor> lazy def a: Int = { a$lzy = 10; a$lzy }; () }</accessor></stable></artifact>

ATS2

homebrew をなんとなく見てたら最近有名になりつつある ATS2 (ats2-postiats) があったので入れてみた。が、チュートリアルの通りに hello world をコンパイルしてみようとしたところ lib64 がないと言われた。なので以下のようにシンボリックリンク貼って解…

Scalac の最適化オプション

scalac は -optimise をつけるとより効率のよいバイトコードを吐きます。(安定性にちょっと不安があるけど…) ところで最適化オプションにはその他に -Yhoge 系のが 5 個あって、これと -optimise と両方つけるとより速くなるのかなんなのかググっても、マニ…

Java 8 の Stream

Java 8 の Stream を試しててアレ?と思った話。

P vs. NP

きたまさによると *1 P=NP らしいですし、未来のわたさんによると*2 G○○gle も P=NP であることを示し、多項式時間アルゴリズムを隠し持っているらしいです。 一方で、P/=NP でも実用上は多項式時間と同等となるような底のすごく小さい指数時間アルゴリズム…

Haskell 小ネタ: 中置

最近同期とした話。 Haskell では任意の関数をバッククォート(`)で囲むことで中置の演算子にできる。例えば、 div 6 2 は、 6 `div` 2 のように書ける。 では、引数が3個以上あったらどうなるだろうか? 例えば、 foldr (+) 0 [1,2] はどのように書けるのだ…

実用のための身も蓋もない shift/reset

まず、answer type modification のことは忘れてください。次に実行モデルを思い浮かべて monad を作りましょう。unit と bind が必要です。(3/12追記: monad 則にも注意しましょう)最後に reflect = λm. shift (λk. bind (m, k)) reify = reset . unit とい…

行の移動の追跡

diff/patch ってリファクタリングとかで行を入れ替えたり、コピペしたりすると追跡できなくなりますよね。それに対応するツールってないのでしょうか。 Comparison of file comparison tools - Wikipedia, the free encyclopedia を見ると一応検出用ツールは…

三角形の5心 (メモ)

めもめも 基本的には頂点ベクトルの重み付き平均なので重みだけ 重心: 1 内心: 対辺の長さ 傍心(3個): 対辺の長さ (ただし外分の要領で1つの符号を反転) 外心: sin(2 * 角度) 垂心: tan(角度)

プログラムの意味

プログラムの操作的意味論だとプログラムの各種構造を数学の領域に移す関数を定義して、それを利用して数学的意味を決める。それは元のプログラムの構造と一貫性を持っているはずなので多分準同型写像になっていて、これを使って、最適化したプログラム同値…

ダウンロード時間の推定

ダウンロード予想時間というのはもう少しまともに見積もれないものなのだろうか。瞬間速度だと某IEみたいにはっきりしろよとなるし、累積転送量を使うとバースト時に影響されてだんだん時間が伸びていくとかなってしまう。 きっと、何とかフィルタとか使うん…

過学習への対処 (てきとーなイメージ)

機械学習をするとき少ないデータ数ではよくわからない部分、というのは往々にして存在する。このとき、「わからん、困った」とか言うのがゼロ頻度問題だし、そんなこと気にせず突っ走ってアグレッシブな推定をする困ったさんが過学習である。ような気がする…

shift/reset

shift/reset で遊ぶなら, お茶むる (OchaCaml = CamlLight + shift/reset) とか Scala + Continuation Plugin とかがあるらしい. お茶むるはちょっと古くてビルドがちょっとうまく行かないかもしれないので気をつけよう. 最初にパッチを nkf に通した方が無…

Centralization と ClassLoader

Centralization とは, 複数プロセスが協調して動くアプリケーションをモデル検査にかけたいときに, それぞれのプロセスを1スレッドとして1つのアプリケーションに押しこむことで, 検証可能にする技法のこと. 当然ながら内部実装が見えているときに限る. 例え…

MAG 2.11

その筋では有名だけど幾分古い MAG System というものがある. http://www.cs.ox.ac.uk/research/pdt/progtools/mag/ にサイトの残骸がある. Haskell で書かれているが, GHC 5 向けなのですでにビルドできない. ちなみに日本製としてその筋で有名な Yicho も…

foldr と foldl の違い

foldr とは cons リスト上の fold であり, foldl とは snoc リスト上の fold を cons リスト上でシミュレートしたものである. よって foldr の方が美しい. 終わり. ではなくてもう少しきちんと説明する.

自明なプログラム

簡単なプログラム、あるいはもっと強く、自明なプログラムと、最適化されたプログラムとを比較して最適化されたプログラムの正しさを検証しようという話が時々ある。それはもっともなことだと思う。 が、よく考えると自明なプログラムって何だよ?という話に…

MapReduce と map 関数と reduce 関数を組み合わせたパターンの違い

なんでこんなめんどくさいタイトルになるのかといえば, それはすべて某 G が紛らわしいフレームワーク名をつけたからです. すべて某 G が悪い. それはさておき, map 関数とか reduce 関数というのはリストに関数を適用する高階関数である. map 関数 とは, 1…

拡大グラフ上のダイクストラ

ACM-ICPC に Traveling by Stagecoach Traveling by Stagecoach という問題がある. 大雑把に言うと, 入力として道路網のグラフが与えられるので, 最短路を求めよ, という問題なのだが, 一捻りして馬車券という要素が加えられている. 要するに最短路を求める…

メタメタ

メタプログラミングとは何か? という話が最近身近で話題になった. 大体, プログラミングの上に載っている高次の何かっぽいことである気がする. その時の結論としては, 自己言及的なプログラミングという話になったが, それはオートプログラミングとでも呼ぶ…

Algorithm Short Course 「探索」

これは2008年11月頃に某所で内輪向けに発行した冊子に掲載したものを転載したものです。

集約される式と展開される式

普通の式は関数からなる. 関数は複数の引数を取り, 1 個の返り値に集約する. しかし, 逆があってもいいのではないか. すなわち, ただ 1 個の種を取り, 複数の返り値に展開していくのである. 一見普通の式であるが, 引数のように見えるところは返り値を渡す先…

多倍長整数の符号化としての UTF-8

UTF-8 は Unicode で使われる 0 から 0x10FFFF までの正の整数を 1 ~ 4 byte の符号で表現する可変長の符号化方式である. その気になれば, 無限に大きい正の数を表現できるように拡張することもできる. 多倍長整数の符号化方式として捉えたときにどうなるか…

学会タイマー

学会タイマーの実装方法は2種類ある. 1秒待って経過時間を加算して画面を更新するということを繰り返す 経過時間の更新と画面の更新は特に同期せず, 適宜開始時刻から引き算する ちょっと考えればわかるが, 1 の方法はアウトである. 更新にかかる時間の分だ…

ゆる募

【緩募】各種中間言語用VMの性能比較 (オーバーヘッドの大きさ、あるいは JIT の賢さ、SIMD系命令への対応など) ってどこかにありませんか?— えおもると寝坊と昼夜逆転さん (@eomole) 2013年5月10日

Java の配列の長さ

問 Java の配列は 231-1 より長いものを作れないというのは、知られていないが案外深刻な問題である。こんなに要素が多いものは作らないと思うかもしれないが、内部で配列を使っているものは少なくない。 String のような文字列、 ArrayList あるいは HashMa…

2分探索したいけれど上限が見積もれないとき

問 2分探索は答えを確実に含むような十分広い区間から初めて、区間を半分にしていくことにより、対数時間で答えの存在範囲を絞り込む方法である。整数値であれば、区間が1になるまで続けることで誤差なしで求めることもできる。しかし、このままでは初期区間…

Calling Brainf*ck

Brainf*ck のループが常々鬱陶しいと思っていたので [, ] を置き換えてみた. 記号 値 実行内容 @ 0 何もせず次へ進む. 0 以外 i 番目の @ ならば i 番目の ^ の直後にジャンプする. ^ 0 i 番目の ^ ならば i-1 番目の @ の直後にジャンプする. 0 以外 i 番目…

誕生日ネタ

適当なことをつぶやいたら問題を作られてしまいました. https://twitter.com/#!/miracjp/status/146070398730121216 https://twitter.com/#!/peria/status/146075492351606784 これを求めるプログラムを書いてみてくださいな.

バグのないプログラムを作るための技術

2015/12/10 追記: バグを本気で無くしたい方はこんな良く辺鄙なブログなんて見ずにソフトウェアエンジニアリング系の国際学会に行くなり、そこの論文を読むなりするといいと思います。ICSEなんかは日本語の勉強会資料もあってとっつきやすいでしょう。バグの…

Dijkstra's Algorithm

こんな世界になっていたのですね。 あきばやべぇ。 Dijkstra のアルゴリズム - (iwi) { 反省します - TopCoder部

Dijkstra's Algorithm

最近 Dijkstra's Algorithm の話があったので, ちょっと思い出したことを徒然と. この algorithm では, 次に始点から一番近い頂点を探すときに heap を使うことが多いかと思います. しかし, priority_queue とか PriorityQueue には, すでに heap に入ってい…

計算と記述の順序

Java には計算の記述に次のようなスタイルがありますよね. y = fn(…(f1(f0(x)))…); y = x.f0().f1().….fn();プログラムの計算順序をメソッド名のトークンの順序と関連付けて考えると, 上は逆向き, 下は同じ向きになっていると思います. 左から右に流れる自然…

高校振り分けアルゴリズム

自分が入学した年まで、母校とライバル校は一括で募集を行っていて、合格者は何らかの方法で半分ずつ振り分けられていました。高校の目の前に住んでいるのにもう一方に入れられてしまった!といった数々の不条理を生んだこの制度ですが、その当時はライバル…

TODO

練習とか勉強とか以外のTODO 自動リスト 自分専用クライアント PDFとかPPTとか管理用ツールの類 別に作らなくてもいいけど今要りそうなもの。

点を円で囲む方法のあれこれ

2013/5/8 不正確な点もあるので、そのうち書き直します 2014/10/15 警告文追加しましたMM56の問題でこんなものがありました。 平面上のすべての点をM個以下の円で覆い、それらの半径の2乗和を最小化せよ 細かい条件は省略していますが、これの厳密解を求める…

キューとスタック

数日前回転寿司に行った。ところが、混雑のためまともなネタがウニしか回っていなかった。仕方なく注文をしたが、一部しか出てこない。実は、注文の処理方法がキュー(FIFO)だと思っていたのに、スタック(FILO)だったらしい。食べ終わった頃に一度に出てきて…