二分探索よりお得なオンライン価格戦略 - 麻辣坊主
オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です． 出典は R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.1 です． この記事自体は Haifeng Xu 先生の講義スライド の第 1 回をかなり参考にしてます． ゲーム理論と機械学習の様々な興味深いトピックが網羅されていておすすめです． 問題設定 戦略の評価尺度：リグレット 自明な $\mathrm{O}(N)$ リグレット戦略 二分探索による $\mathrm{O}(\log N)$ リグレット戦略 二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略 まとめ 問題設定 あなたは A さんに $N$ 個のリンゴ を，$1$ 日
ネットワークフロー問題たちの関係を俯瞰する - 私と理論
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
Pythonを書き始める前に見るべきTips - Qiita
Pythonを使ってこの方さまざまな点につまずいたが、ここではそんなトラップを回避して快適なPython Lifeを送っていただくべく、書き始める前に知っておけばよかったというTipsをまとめておく。 Python2系と3系について Pythonには2系と3系があり、3系では後方互換性に影響のある変更が入れられている。つまり、Python3のコードはPython2では動かないことがある(逆もしかり)。 Python3ではPython2における様々な点が改善されており、今から使うなら最新版のPython3で行うのが基本だ(下記でも、Python3で改善されるものは明記するようにした)。何より、Python2は2020年1月1日をもってサポートが終了した。よって今からPython2を使う理由はない。未だにPython2を使う者は、小学生にもディスられる。 しかし、世の中にはまだPython3に
JavaScript：float32による小数演算最適化 | 月と燃素と、ひと匙の砂糖
また翻訳です！ Efficient float32 arithmetic in JavaScript コンピュータ上で浮動小数点を表現する方法はいくつか存在する。だいたいのアーキテクチャではIEEE754標準を使っている。この標準では、倍精度浮動小数点(a.k.a. double or float64)を64bitで表し、単精度浮動小数点(a.k.a. float or float32)を32bitで表している。名前が示す通り、float64はfloat32よりもっと正確なんだ。だからパフォーマンスがあんまり重要視されないときは大体こっちを使おうねってアドバイスされる。 でもね、float32を使うことにもこんな利点がある： float32は計算操作をするのにfloat64よりCPUサイクルがしばしば少ない。精度が低いからだ。 float64の計算をfloat32に対して行うには、いくらか
[JavaScript] 非同期処理のコールバック地獄から抜け出す方法 - Qiita
JavaScript (Node.js) で開発する上で避けては通れない 非同期処理、コールバックについて考えてみたい。 自分なりのお勧めの方式を書いてみた。 いろいろなものを試した結果である。 ※この記事でのお勧めの方法は ES2015 (ES6) で実装された generators (yield) の技術を使用しています。 実はまだ Babel(6to5) 等を利用するか Node.js v4～v8 でしか 実質的に使用できない技術だと思います。悪しからず。 (早く全てのブラウザに広く普及する事を祈っています) まだブラウザでは独自ライブラリか Promise (Deferred) 等を使っています。 ※2015/10/15: 記事の内容を npm aa (async-await) に対応させました。 ※2015/04/19: 記事の内容を npm co@4 に対応させました。 ※20
![[JavaScript] 非同期処理のコールバック地獄から抜け出す方法 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/f663d25f2912af4849a690fcc94d049628ce353c/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fqiita-user-contents.imgix.net%252Fhttps%25253A%25252F%25252Fcdn.qiita.com%25252Fassets%25252Fpublic%25252Farticle-ogp-background-afbab5eb44e0b055cce1258705637a91.png%253Fixlib%253Drb-4.0.0%2526w%253D1200%2526blend64%253DaHR0cHM6Ly9xaWl0YS11c2VyLXByb2ZpbGUtaW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRnFpaXRhLWltYWdlLXN0b3JlLnMzLmFtYXpvbmF3cy5jb20lMkYwJTJGMTYxMjglMkZwcm9maWxlLWltYWdlcyUyRjE0NzM2ODE3Nzg_aXhsaWI9cmItNC4wLjAmYXI9MSUzQTEmZml0PWNyb3AmbWFzaz1lbGxpcHNlJmZtPXBuZzMyJnM9MjAwMGE5MTAzMzIyMDk0M2M3ZjQ3NjQ3OTEyM2VmNjM%2526blend-x%253D120%2526blend-y%253D467%2526blend-w%253D82%2526blend-h%253D82%2526blend-mode%253Dnormal%2526s%253D675f62b48b0f92263d3cf310a1ce071a%3Fixlib%3Drb-4.0.0%26w%3D1200%26fm%3Djpg%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk2MCZoPTMyNCZ0eHQ9JTVCSmF2YVNjcmlwdCU1RCUyMCVFOSU5RCU5RSVFNSU5MCU4QyVFNiU5QyU5RiVFNSU4NyVBNiVFNyU5MCU4NiVFMyU4MSVBRSVFMyU4MiVCMyVFMyU4MyVCQyVFMyU4MyVBQiVFMyU4MyU5MCVFMyU4MyU4MyVFMyU4MiVBRiVFNSU5QyVCMCVFNyU4RCU4NCVFMyU4MSU4QiVFMyU4MiU4OSVFNiU4QSU5QyVFMyU4MSU5MSVFNSU4NyVCQSVFMyU4MSU5OSVFNiU5NiVCOSVFNiVCMyU5NSZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTU2JnR4dC1wYWQ9MCZzPTg5MjM0YTRkYmUwOWZlMGEyNDhlODIwNjkwNTRkNjgy%26mark-x%3D120%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTgzOCZoPTU4JnR4dD0lNDBMaWdodFNwZWVkQyZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1wYWQ9MCZzPWFjN2FmMTI0YjNkN2I4NWFjZjAxZjNmODNkMDJiZTE1%26blend-x%3D242%26blend-y%3D480%26blend-w%3D838%26blend-h%3D46%26blend-fit%3Dcrop%26blend-crop%3Dleft%252Cbottom%26blend-mode%3Dnormal%26s%3D3ec0d914b8688b86a6dc14b0b44b43ae)
遅延評価を活用して線形時間でGoogle Code Jam 2014 Round 1AのB問題を解く - tosの日記
公式の解説で，「遅延評価を使ってもできる」と書いてくれなかったので。 注意：この記事は，Google Code Jam 2014 Round 1AのB問題 Full Binary Tree についてのネタバレを含みます。 この問題は木DPをする典型的な問題であり，公式の解説にもあるように， 木を根付き木にした後， 頂点でのスコアを，子のスコアのうち大きい方から2つを用いて計算する ことで解けます。何を根として選ぶかをすべて試すとO(N2)解法となり，すべての根の可能性について同時にDPをする*1とO(N)解法になります。だから，根の選び方によって隣接頂点のうち「親以外が子となる」ので，隣接頂点のスコアのうち大きい方から3つを保存するような構造を持つ――待ってください。 もちろん，降順ソートされたスコアのすべてを計算すると，O(N2)時間かかってしまいます。しかし，先頭3つを結果的に計算でき
プログラマーのための確率プログラミングとベイズ推定
プログラマーのための確率プログラミングとベイズ推定¶PythonとPyMCの使い方¶ベイズ推定(Bayesian method)は，確率推論のためのもっとも適切なアプローチであるにもかかわらず，書籍を読むとページ数も数式も多いので，あまり積極的に読もうとする読者は少ないのが現状である．典型的なベイズ推定の教科書では，最初の3章を使って確率の理論を説明し，それからベイズ推論とは何かを説明する．残念ながら多くのベイズモデルは解析的に解くことが困難であるため，読者が目にするのは簡単で人工的な例題ばかりになってしまう．そのため，ベイス推論と聞いても「だから何？」と思ってしまうのである．実際，著者の私がそう思っていたのだから． 最近の機械学習のコンテストで良い成績を収めることができたので，私はこのトピックを復習しようと思い立った． 私は数学には強い方である．しかしそれでも，例題や説明を読んで頭の中で
foldlを直す - 純粋関数空間
http://www.well-typed.com/blog/90/ foldlに関するこの記事（英文）が面白かったので、勝手翻訳しました。 foldlなんとかなるといいですね。 foldlを直す foldl 関数は壊れている。壊れているとみんなが知っている。 四半世紀近く壊れたままだ。ついにこれを修正する時が来た！ 今日、私はPrelude.foldlをData.List.foldl'として知られる実装で再定義することを提案する。 foldlは壊れている！ 既にご存知だとは思うが、念のため… Haskellerが必ずfoldlではなく、foldrやfoldl'を使うように勧めてくることにお気づきだろうか？ 例えばReal World Haskellでは次のように言っている。 `foldl`のサンクの挙動のため、実アプリではこの関数を使わないようにするのが望ましい。 特に問題がない場合でも
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
