自動微分 ≪フォワード・モード≫ - d.y.d.
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. ランダム生成に興味があります。 パズルゲームを作りました。 さて、手強い難易度の面データを無限にランダム生成するにはどうすればいいだろう。 プログラミングコンテストの問題を作りました。 さて、自動チェック用のテストデータをランダム生成するにはどうすればいいだろう。 適当なランダム生成では、簡単なケースばっかり作られてしまい 嘘解法 に突
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%)となることがわかります
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
