確率的データ構造・ブルームフィルタについてのまとめ - kakts-log
概要 特定のデータが、ある集合やリストに含まれるかどうかを判定するために線形探索や二分探索などいくつかのサーチアルゴリズムが使われますが、 本稿ではメモリの使用効率、探索の際の計算量が優れているブルームフィルタを用いたアルゴリズムについてまとめます。 ブルームフィルタとは ブルームフィルタとは確率的データ構造の一種で、あるデータが集合に属するかどうかを判定する際に使われます。 特徴としては、メモリの空間消費が少なくすみ、非常に効率的にデータの存在判定ができます。 デメリットとしては、false-positive(偽陽性)によるデータの誤判定の可能性があり、集合に存在しないデータを存在すると誤判定してしまう場合があります。このような誤判定が許されないような状況においては、ブルームフィルタは使えません。 逆に、false-negative(偽陰性)による誤判定はないため、データは実際にあるのに
バケットソート - Wikipedia
バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。 概念[編集] バケットソートの概念 整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。 安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す
なぜｄｐ「やるだけ」なのか ～動的計画法について考える その１～ - kuuso1のブログ
これは、Competitive Programming Advent Calendar 2016の17日目の記事です。 競技プログラミング（以下，競プロ）においてよく出題される動的計画法（Dynamic programming，通称dp）について，「dpやるだけ」という表現を稀に見かけます．競プロを始めた人のうち，多くの人が（少なくとも自分にとっては）最初の壁のうちの一つと言ってもいいdpというジャンルがなぜ「やるだけ」などというパワーワードを伴ってしまうのか．今回はそういうところから，ふわっと動的計画法について考えてみようと思います．どちらかといえばテクニック的な内容というよりは自分がdpの問題に触れるときに意識しているようなことを書いているだけなので，参考になったりならなかったりすると思いますがご容赦のほど． 動的計画法とは 動的計画法 wikipedia によると「対象となる問題を複
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
回文に親しもう - pixiv inside [archive]
こちらは ピクシブ株式会社 Advent Calendar 2014 の12月22日の記事です。 こんにちは、おはようございます、こんばんは、エンジニアのneo-nanikakaです。 他のエンジニアの皆さんが、Webサービスやってる会社っぽいエントリーを書いていますが、空気を読まずにWebっぽくないエントリーを書きます。趣味なんだから、仕方ないね。でもこういうのが許されるのは大変良い社風だと思います（唐突なヨイショ）。 回文について もしかしたら、回文（かいぶん）という言葉を聞いても何のことやらと思う方もいるかもしれません。回文とは、「しんぶんし」「私、負けましたわ」のように、上から読んでも下から読んでも意味が通る言葉や文を使った言葉遊びです。「山本山」も漢字のままなら回文です。西尾維新さんも「NISIO ISIN」とローマ字表記すれば回文です。 回文の言葉遊びは日本語に限った話ではなく
![回文に親しもう - pixiv inside [archive]](https://cdn-ak-scissors.b.st-hatena.com/image/square/649650be00c35aecad2db1e7f5abf8372cc4f08e/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F11696248318756278971%2F8454420450077730553%2F1419241303)
B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
Ｎ進数計算およびエンコード／デコードのロジック - clock-up-blog
※なんだか思ったよりも長くなってしまったので、電車の移動時間とかそういう隙間時間の時間潰しにでもご活用いただければと思います。 前書き 今更ですが情報基礎に立ち返り、進数計算について改めて書き起こしてみようと思います。 近年の情報技術はまだまだ発展途上ではありながらもその進歩は目覚ましく、進数計算程度の話であれば、そのロジックはいくらでも探せば転がっていますし、そもそもロジックを意識することなくライブラリ利用により「一般的な生産行為」は済ませられることが多く、そしてそのような選択がほとんどの場合の最適解です。 ただ、あまりにもライブラリ機能に依存するばかりにロジックの理解が疎かになる傾向が広く見られます。プログラムを日々組んでいる方であれば一度は意識したことのある世界だと思いますが、一度通過したきりで忘れがちな世界でもあります。このあたりの理解がおぼろげな方は、是非教養のひとつとして再度意
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
Luhnアルゴリズム - Wikipedia
Luhnアルゴリズム（Luhn algorithm, ルーン・アルゴリズム）は、様々な識別番号の認証に使われている単純なチェックサム方式。MOD-10アルゴリズムとも。クレジットカード番号、IMEI番号、en:National Provider Identifier（アメリカでの医療機関の識別番号）、カナダ社会保険番号（Social Insurance Number）などで使われている。IBMの科学者 ハンス・ピーター・ルーン（英語版） が1954年1月6日に特許を申請し、1960年8月23日に発効した[1]。 アルゴリズムはパブリックドメインになっており、今日では広く利用されている。ISO/IEC 7812-1[2] に詳細に記されている。暗号学的ハッシュ関数としては使えない。 記入ミスやタイプミスを検出するためのもので、クレジットマスターによる悪意ある攻撃を防ぐものではない。多くのクレ
ページ置換アルゴリズム - Wikipedia
ページ置換アルゴリズム（ページちかんアルゴリズム）とは、仮想記憶管理としてページング方式を使用するコンピュータのオペレーティングシステムにおいて、空き物理ページが少ない状態で新たなページを割り当てなければならないときにどのページを「ページアウト（スワップアウト）」するかを決定する方法を意味する。これはページフォールトが発生したときに使用可能なフリーなページが存在しないときに発生する。厳密には発生条件はシステムの種類や設定によって異なるが、フリーなページが全く無い場合か、あらかじめ設定したしきい値よりもフリーなページ数が少ないときに発生する。 以前にページアウトすべきページとして選択され置換されたページに再度アクセスが発生したら、そのページをページインする必要がある。そして、これにはI/Oの完了を待たなければならない。この、ページインを待つ時間の累計が小さいほどページ置換アルゴリズムが優秀で
探索 - Wikipedia
探索（たんさく、英: search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。 何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。 一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（英: search）も参照。 概要[編集] 探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。 まず解くべき問題を状態（英: state）と状態変化（行動、英: action）に分ける。 最初に与えられる状態を初期状態（英: initial state）といい、目的とする状態は最終状態（ゴール、英: final state, goal）と呼ばれる。 初期状態から最終状態に至る、状態及び
山登り法 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "山登り法" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2018年1月） 山登り法（やまのぼりほう、英: hill climbing, HC）は、評価関数の極値を探索する探索アルゴリズム。最も代表的な局所探索法として知られている。最良優先探索は過去の解を管理するが、探索対象を現在の解だけに制限したものである。評価関数を使用する探索アルゴリズムとしては最も単純。 概要[編集] 山登り法とは「現在の解の近傍の内で最も成績の良い解」を近傍解として選び、「現在の解より近傍解の成績の方が良い場合」に近傍解と現在の解を入れ換える局所探索法の方法。極
焼きなまし法 - Wikipedia
この項目では、確率的メタアルゴリズムについて説明しています。金属の熱処理については「焼きなまし」をご覧ください。 焼きなまし法（やきなましほう、英: Simulated Annealing、SAと略記、疑似アニーリング法、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案し[1]、1985年に V. Cerny が再発見した[2]。 その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエ
MinHash - Wikipedia
In computer science and data mining, MinHash (or the min-wise independent permutations locality sensitive hashing scheme) is a technique for quickly estimating how similar two sets are. The scheme was invented by Andrei Broder (1997),[1] and initially used in the AltaVista search engine to detect duplicate web pages and eliminate them from search results.[2] It has also been applied in large-scale
Rubyでb-Bit MinHashを実装してみた。 - タチコマ好きなエンジニアのブログ
昨日に引き続き、SmartNews開発者ブログの「b-Bit MinHashによる高速かつ省スペースな類似度判定」を参考に、Rubyでb-Bit MinHashを実装してみた。 ビット数は1、ハッシュ関数の個数は128で計算させている。 ただし、1ビット値は最初から50％の確率で衝突するので、単に一致した回数をkで割っただけでは、真のJaccard係数が0の場合でも0.5くらいの推定値が出てきてしまいます。 とのことなので、一致数をハッシュ関数の個数で割った値から0.5を引いて2倍したものを表示させてみた。（calc_jaccardのコメントを外すと表示される） だいたい0.4に近い値が出るので多分合っているはず。 ベンチマーク的にはMinHashと大差がなかったけれど、popcountの処理をきちんと実装すれば速くなるかもしれない。 ソースコード require 'murmurhash3
b-Bit MinHashによる高速かつ省スペースな類似度判定 - SmartNews Engineering Blog
ゴクロの浜本です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリー
局所性鋭敏型ハッシュ - Wikipedia
局所性鋭敏型ハッシュ（きょくしょせいえいびんがたハッシュ、英語: locality sensitive hashing）とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。 定義[編集] 局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間と閾値、近似因子によって定義される。LSH族[1][2]は2点について次の2つの性質、 ならばとなる確率は以上である。 ならばとなる確率は以下である。 を満たす関数により与えられる族であり，はから一様乱数にしたがって選択される。このときは2点の
fast sqrt
高速根号計算 (fast sqrt algorithm) 概要: C言語のsqrt(float)より精度は若干劣るものの，2倍以上速いsqrtのalgorithm． ググって見つけた物が，非常に面白かったのでまとめておく．精度より速度が求められる場面で活躍する． 参考文献 [1] David Eberly, Fast Inverse Square Root (Revisited), http://www.geometrictools.com/Documentation/ FastInverseSqrt.pdf, 1/2002-. 実装 //---Algorithm float(IEEE754)用------ inline float t_sqrtF( const float& x ) { float xHalf = 0.5f * x; int tmp = 0x5F3759DF
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
Difference bloom filters and FM-sketches