![](https://cdn-ak-scissors.b.st-hatena.com/image/square/e9c1a624cc017b7e4a144ae35d96bf6afb736768/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9V2Fsa2VyJTI3cyUyMEFsaWFzJTIwTWV0aG9kJUUzJTgxJUFFJUU3JUFFJUIxJUUzJTgxJUFFJUU0JUJEJTlDJUUzJTgyJThBJUU2JTk2JUI5JUUzJTgxJUFFJUUzJTgyJThGJUUzJTgxJThCJUUzJTgyJThBJUUzJTgyJTg0JUUzJTgxJTk5JUUzJTgxJTg0JUU4JUFBJUFDJUU2JTk4JThFJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWNsaXA9ZWxsaXBzaXMmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz0yZmNmMmJiZjAwM2NkNjljZDQ0NjNmZTM3NTFjM2EzMQ%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTYxNiZ0eHQ9JTQwa2FpdHlvMjU2JnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz04ZjVhM2QxZWZkZjExODlmNTNmYzZkOTQzNzFmMjRhNw%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D27282c1c936882735be858b0859d6ea4)
エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント1件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Walker's Alias Methodの箱の作り方のわかりやすい説明 - Qiita
はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5... はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5]という配列が与えられた時、確率10%で0、40%で1、50%で2というインデックスを返すような関数が欲しい。 普通に考えると部分和をとって乱数を一度振り、どの場所が選択されたか二分探索で調べる、というアルゴリズムが思いつくが、これは要素数Nに対して$O(\log(N))$の手間がかかる。logの手間というのは無視できることが多いが、この関数呼び出しが頻繁にある場合には無視できないコストになる。 さて、こんな用途のためにWalker's Alias Methodというアルゴリズムがある。この手法は一度$O(N)$の手間で配列を作ってしまえば、後は$O(1)$でインデックスを選ぶことができる。 例えば重みとして[3, 6, 9, 1, 2, 3, 7, 7, 4, 8]という10個の要素を
2019/07/12 リンク