Alias method - Wikipedia
A diagram of an alias table that represents the probability distribution〈0.25, 0.3, 0.1, 0.2, 0.15〉 In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, published in 1974 by Alastair J. Walker.[1][2] That is, it returns integer values 1 ≤ i ≤ n according to some arbitrary discrete probability distribution pi. The algorithms typic
Walker's Alias Methodの箱の作り方のわかりやすい説明 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5]という配列が与えられた時、確率10%で0、40%で1、50%で2というインデックスを返すような関数が欲しい。 普通に考えると部分和をとって乱数を一度振り、どの場所が選択されたか二分探索で調べる、というアルゴリズムが思いつくが、これは要素数Nに対して$O(\log(N))$の手間がかかる。logの手間というのは無視できることが多いが、この関数呼び出しが頻繁にある場合には無視できないコストになる。 さて、こんな用途のためにWalker'
1次元ランダムウォーク - ei1333の日記
初心者向け 1 次元ランダムウォーク 数直線があって、原点 に点 がある。 時刻が 進むごとに、点 の位置が確率 で 、確率 で 動く。 この確率モデルを (対称な) 次元ランダムウォークと呼ぶ。 パスの個数 横軸を時間軸、縦軸を点 の位置を表すこととすると、以下のような折れ線グラフで表すことができる。 を、原点から点 までのパスの個数（言い換えると、時刻 に位置 に至る経路数）とする。 と から、ランダムウォークで した回数 と した回数 をそれぞれ計算できる。 より、 となる。("45度回転"に相当する) したがって と の偶奇が一致しているとき と二項係数を用いて表せる。 auto L = [&](int t, int x) -> modint { if(t % 2 != abs(x) % 2) { return 0; } else { return beet.C(t, (t + x
C言語による乱数生成
本文章はC言語を用いて様々な確率分布に従う乱数を生成する方法やコードをまとめたものである。rand関数やメルセンヌ・ツイスタの使い方から始まり, 正規分布・指数分布等の様々な確率分布に従う乱数の生成方法について解説する。このページは近江崇宏によって作られました。コードはご自由にお使いになってかまいませんが、バグ等によって生じた損失に対する責任は負いません。 道しるべ: ・Ｃ言語でお手軽に整数の乱数を発生させたい人 ==> C言語のrand関数の使い方 ・メルセンヌ・ツイスタの使い方を知りたい人 ==> メルセンヌ・ツイスタの使い方 ・一様乱数の生成方法を知りたい人 ==> 一様乱数 ・様々な確率分布に従う乱数生成法を知りたい人 ==> 各種の確率分布に従う乱数の生成法 入門編 C言語のrand関数の使い方 メルセンヌ・ツイスタの使い方 乱数生成の基礎 一様乱数 (Uniform Rando
SQL実行時のブルームフィルタ(Bloom Filter)アルゴリズム | フューチャー技術ブログ
1. 初めにDBにおける処理はSQLによって記述しますが、データの取得するために具体的にどのような内部処理を行うかという点までは記述しません。 ここでいう内部処理とは「SQLの書き換え」「インデックスの使用」「結合アルゴリズムの選択」などがDBMSのオプティマイザによって選択されて実施されることを指します。 SQLのパフォーマンスを見るにあたっては上記の内部処理について正しく理解する必要があります。 本Blogでは、重要なアルゴリズムであるにもかかわらず、まとまった情報が少ないSQL実行時におけるブルームフィルタ(Bloom Filter)についてOracleをもとに紹介を行います。 Bloom Filterは結合処理を効率化するために、結合の前段階で利用される技術になります。 公式なドキュメントとしては以下になります。 Oracle Database SQLチューニング・ガイド 12cリ
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
CHAGEの裏側: ブルームフィルタとISONの逆引き高速化 | IIJ Engineers Blog
セキュリティ本部 セキュリティ情報統括室に所属 システム開発者。2000年問題で「2038年問題は定年で対応しなくていい！」とフラグを...。 CHAGE開発者のヒラマツです。 前回（CHAGEの裏側: D3.jsの紹介）同様、CHAGEの紹介と並行して、CHAGEの中が気になる人に、CHAGEで使われている技術をちょっと濃い目に解説するという企画です。 今回は、本編（CHAGE の動き）がISONネタなので、こちらもISONに関係ある話として、ブルームフィルタについて書きます。 ブルームフィルタをざっくり解説してから、ブルームフィルタの具体的な使用例としてISONでの逆引き高速化の方法を紹介していきたいと思います。 目指すのは、ちゃんとした理解ではなく、「ブルームフィルタの雰囲気を知って、利用価値をなんとなく判断できる」ところです。 今回は、以下の知識を前提にしているので、そこはご了承く
テストの実行 - C# を使用した Thompson Sampling
注意 このページにアクセスするには、承認が必要です。 サインインまたはディレクトリの変更を試すことができます。 このページにアクセスするには、承認が必要です。 ディレクトリの変更を試すことができます。 February 2018 Volume 33 Number 2 テストの実行 - C# を使用した Thompson Sampling James McCaffrey Thompson Sampling は、多腕バンディット問題の解を求めるために使用できるアルゴリズムです。用語「多腕バンディット」は、ギャンブルに使われるスロットマシンの俗称が「one-armed bandit (片腕バンディット)」だったことに由来します。 ここに 3 台のスロットマシンがあるとします。3 台のうちの 1 台のハンドルを引くと、誰も知らない何らかの確率分布に従って、掛け金を失うか、1 ドルが払い戻されます。
確率DPを極めよう - 確率と期待値の問題解説
DP tsutaj (@_TTJR_) Hokkaido University B4 February 20, 2018 tsutaj (Hokkaido Univ.) DP February 20, 2018 1 / 54 1 2 ( ) ( ) HSI 3 4 RareItems (Hard) 5 tsutaj (Hokkaido Univ.) DP February 20, 2018 2 / 54 (Dynamic Programming) tsutaj (Hokkaido Univ.) DP February 20, 2018 3 / 54 DP DP DP tsutaj (Hokkaido Univ.) DP February 20, 2018 4 / 54 A P(A) = A : 6 1 5 P(x ≥ 5) = 1+1 6 = 1 3 A P(Ā) = 1 − P(A)
Bloom Filters by Example
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set. The base data structure of a Bloom filter is a Bit Vector. Here's a small one we'll use to
Bloomフィルターについて調べた
Eric Redmond & Jim R. Wilson 著の”Seven Databases in Seven Weeks” を読んでいたところ、Ch.8 Redis の Day2 で書籍名の重複チェックに Bloom Filter という確率的データ構造(アルゴリズム?)が利用されていた。本ではさらっとしか触れられていなかったので調査。 処理の流れ 材料 ビット配列(m ビット) ハッシュ関数(k個。整数1からm のどれかをかえす) 作り方 下ごしらえ ビット配列の各ビットは予め0で初期化しておく。 各初期データをk個のハッシュ関数に食わせ、ハッシュ関数のかえすビットを立てる。 重複チェック 重複チェックしたい入力値をk個のハッシュ関数に食わせる ハッシュ関数のかえすビットがビット配列で立っているかチェック すべてのビットが立っていれば、重複と判定。 一つでも立っていないビットがあれば
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
ソフトウェアのための統計学 – 前編 | POSTD
ソフトウェア開発の原点は可能性の追求であり、不可能を可能にすることです。ひとたび ソフトウェア が開発されると、エンジニアは次に 程度 という課題に向き合うことになります。企業向けのソフトウェアであれば、「速度はどれくらいか」と頻繁に問われ、「信頼性はどの程度か」という点が重視されます。 ソフトウェアのパフォーマンスに関する質問に答え、さらには正しい内容を語る上で欠かせないのが統計学です。 とはいえ、統計学について多くを語れる開発者はそうはいません。まさに数学と同じで、一般的なプロジェクトで統計学が話題に上ることなどないのです。では、新規にコーディングをしたり、古いコードのメンテナンスをしたりする合間に、手が空くのは誰でしょうか？ エンジニアの方は、ぜひ時間を作ってください。近頃は、15分でも貴重な時間と言えるでしょうから、 こちらの記事をブックマークに追加 しておいてもいいでしょう。とに
CodeIQについてのお知らせ
2018年4月25日をもちまして、 『CodeIQ』のプログラミング腕試しサービス、年収確約スカウトサービスは、 ITエンジニアのための年収確約スカウトサービス『moffers by CodeIQ』https://moffers.jp/ へ一本化いたしました。 これまで多くのITエンジニアの方に『CodeIQ』をご利用いただきまして、 改めて心より深く御礼申し上げます。 また、エンジニアのためのWebマガジン「CodeIQ MAGAZINE」は、 リクナビNEXTジャーナル( https://next.rikunabi.com/journal/ )に一部の記事の移行を予定しております。 今後は『moffers by CodeIQ』にて、 ITエンジニアの皆様のより良い転職をサポートするために、より一層努めてまいりますので、 引き続きご愛顧のほど何卒よろしくお願い申し上げます。 また、Cod
Algorithms for calculating variance - Wikipedia
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values. A formula for calculating the variance of an entire population of size N is: Usin
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Ryou Ezoe(江添 亮) on Twitter: "Bloom filterは無偽陰性と低擬陽性の特徴を持つ確率的で空間効率のよいデータ構造だと言われていたが、Coqでの検証により、思っているほど低擬陽性ではないそうだ。 https://t.co/60cL33frBD"
yowa on Twitter: "0.25*(popcount(rand64bit()) - 32) を正規乱数だと言い張るスタイル"
講談社サイエンティフィク on Twitter: "＼50周年！／『データサイエンス入門シリーズ』新刊2冊を抽選で3名に同時プレゼント。応募締切4/21(火) 23:59 『モンテカルロ統計計算』 https://t.co/gpURfqNqME 『データサイエンスのためのデータベ… https://t.co/NGXLQeSRT0"
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
Bloom filter
