高速ハッシュアルゴリズム – YOSBITS
この記事は特に高速なハッシュアルゴリズムをまとめた資料です。 暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。 MurmurHash 2008年に”Austin Appleby”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。MurmurHash3 は現在のバージョンで、32ビットまたは128ビットのハッシュを生成する。MurmurHash2 は古いバージョンで、32ビットまたは64ビットのハッシュを生成する。64ビットのハッシュ値生成するソースには2つの変種がある。64ビットプロセッサ用に最適化された用の MurmurHash64A と32ビットプロセッサ用に最適化された Mu
爆速ナンバーリンクソルバー（1）〜ナンバーリンクと充足可能性問題 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 先ほど、ブラウザで動くナンバーリンクソルバー（http://jkr2255.github.io/js_puzzle_solvers/numberlink.html）を公開しました。それについてまとめようと思ったのですが、1本の記事に書くには長すぎるので、少しずつ分けて書いていこうと考えています。 まずは、問題そのものである「ナンバーリンク」と、それの解法に使った「充足可能性問題」について解説します。 まず、「ナンバーリンク」って？ ナンバーリンクは、数独やクロスワードといった、（もともとは）紙と鉛筆で楽しむ「ペンシルパズル」の一種です。
2-SATと強連結成分分解 - naoya_t@hatenablog
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している） SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。 （2-SATは線形時間で解けるらしい）。 論理和 x ∨ y が論理包含 ¬x⇒y （または ¬y⇒x）に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり 出来上がっ
巡回セールスマンの計算量はO(n)というのはなんとなくわかるのですが動的計画法を使った時はO(n^2×2^n)というのが何故だ... - Yahoo!知恵袋
C言語のプログラムについて質問です。 #include <stdio.h> int main(void) { int i; int v[5]; /*要素に値を代入*/ for(i = -1; i < 5; i++) v[i] = i + 1; /*要素の値を表示*/ for(i = 0; i < 5; i++) printf("v[%d] = %d¥n",i,v[i]); return 0; } 上記プログラムの実行結果は下記のようになります。 v[0] = 0 v[1] = 2 v[2] = 3 v[3] = 4 v[4] = 5 V[0] = 0 のあと、V[1] = 2で 「2」へ一戸飛ばしになる理屈がわからないので 教えていただきたく思います。 wind catさんに質問があります。 この前の件はありがとうございました。 この前頂いたプログラムを試して見たところ、距離に応じ
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。 例題 次の問題を考えてみよう。 N 桁以下の 3 の倍数はいくつあるか。 N が小さければ全列挙できる。i 桁の数がすべて列挙できていれば、その後ろに 0～9 を付け足せば i+1 桁の数をすべて列挙できることを使う。 dp[i] := leading zero を含めて i 桁のすべての非負整数の集合 #include <iostream> #include <string> #include <vector> using namespace std; int modulo(string s, int mod) { int ret = 0; for (char c : s) ret = (ret * 10 + (c - '0'))
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
TopCoder の傾向と対策４（Ｃ＋＋編：数え上げ）
ホームに戻る TopCoder の傾向と対策４（Ｃ＋＋編：数え上げ） ０、はじめに Div2 の hard は数え上げの問題がでます。 単に数え上げという視点で考えてみます。 １、1000000007 で割った余りを答えよ問題対策 TopCoder では整数の６４ビット制限を考慮してくれる。 よって、long long より大きな数値を考えなくても良い。 この数値を超える答えが出る場合には、 答えを 1000000007 で割った余りを答えよ、とされる。 足し算においては足し算を行うごとに % 1000000007 する。 引き算のときは先に引かれる数に 1000000007 を足しておく。 そこから引く数を引いて % 1000000007 する。 こうすると結果がマイナスにならず結果がおかしくならない。 掛け算する場合は足し算と同様である。 A * B をするとき、 A、B それぞれを
Mo's algorithm - ペケンペイのブログ
Mo’s algorithm について説明します。 Mo’s algorithm の動作の様子をアニメーションにしてみました。アニメーションを見れば、計算量解析パートは自明でしょう。IE以外なら見れると思います。 https://pekempey.github.io/mo_algorithm/mo.html Mo’s algorithm とは 区間クエリ系の問題を解くためのアルゴリズム。次のようなクエリに対して有効。 要素が更新されない クエリの先読みが可能 区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる Mo’s algorithm の流れ まず区間を平方分割し、左端をキーにしてクエリをバケットに入れる。その後、各バケット内で右端をキーにしてソートする。 結局のところ上の操作は次の比較関数でソートすること
Codeforces Round #339 (Div. 1) A. Peter and Snow Blower - pekempey's blog
※問題をエスパーしたので問題を勘違いしています。 問題文 codeforces.com 問題概要 点P と 多角形 S が与えられる。 点 P を中心とした円を 2 つ描き、多角形 S がその円の間に挟まれるようにする。 この 2 つの円に囲まれる領域の面積の最小値を求めよ。 解法 点と多角形の距離の最小値・最大値を求めれば面積の最小値が求められる。 点と多角形の距離の最小値は、点と多角形のそれぞれの辺の距離の最小値になる。 そのため、点と線分の距離を求めたい。 点と線分の距離は、点が緑色の領域内部にあるかどうかで求め方が変わる。 以降、直線の単位方向ベクトルを $d=(q-p)/|q-p|$ とする。 緑色の領域の内部にある場合 図でいうと r1 がこのケースになる。これは点と直線の距離を求めればいい。 点と直線の距離は外積を用いて、 $$ | d \times (r-p) | $$ で
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
最小完全ハッシュ函数 - epii's physics notes
最小完全ハッシュ函数 ハッシュ函数のうち、可逆で、かつ、生成するハッシュ値の値域が最小である函数のことを、最小完全ハッシュ函数と言います。 その作り方を解説していきたいと思います。
連載やねうら王miniで遊ぼう！7日目 | やねうら王 公式サイト
今回は、局面のhash値の計算について説明します。 局面に対応するhash値の取り出し 局面に対して、StateInfo::key()からhash値が得られる。 このhash値は、局面に対応する固有の値である。 しかし通例、hash値は64bitしかないので、異なる局面であっても、たまたま同じhash値になることがある。これをhash衝突と言う。 やねうら王miniにはこのhash値を128bitにしたり256bitにしたり出来る無駄機能があるが、その話は次回にしよう。 さて、このkeyを取り出してみよう。その局面固有の内容を格納しておくのはStateInfoであった。Positionクラスのstate()を呼び出すとStateInfoの参照が得られる。StateInfoのkey()を呼び出すとこのhash値が得られる。 実際にやってみよう。 void user_test(Position
ハッシュは頻繁に参照する値を最後に入れると高速 - まめめも
明日から RubyKaigi なので、ちょっとした小ネタを一つ。 例えば、0 から 9999 までをハッシュに順に入れます。 h = {} 10000.times do |n| h[n] = true end このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。 どのくらい高速かというと、 1_000_000_000.times { h } # 40.8 sec (ループ自体の速度) 1_000_000_000.times { h[9999] } # 57.2 sec 1_000_000_000.times { h[0] } # 89.1 sech[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1 なぜこんなことが起きるのか ハ
実験計画法と組合せ最適化 - Qiita
これは、アルゴリズム Advent Calendar 2015の3日目の記事です。 はじめに 実験計画法の簡単な紹介と、その発展として組合せ最適化によるアプローチを紹介します。 背景 センサー情報からある解析をしたいとします。 センサーは、1万円のものと3万円のものがあり、置かないこともあるので、3種類の選択があります。 センサーの設置場所は、20カ所の候補があります。 全センサーの総購入費用は5万円以下に抑えないといけません。 どこにいくらのセンサーを置いたら、効率よく検証できるのかを知りたいものとします。 ケースの例としては、「A地点とB地点に1万円のセンサー、C地点に3万円のセンサーを配置」となります。 用語 下記の用語を使います。 要因：水準を決めたい検討対象。今回は、センサーの配置候補。 水準：要因の取り得る値。今回は、センサーの費用で、0万円、1万円、3万円の3種類。 交互作用
映像Codec屋から見たYJKカラー
色差信号３つのうち１つは、輝度と２つの色差があれば求められるので色差信号は2信号で表現する。 色差の値域は輝度に比べて大きくなるため、色差の値を正規化する表現もある。Yが0.0～1.0の間の値を取るときに色差が-0.5～+0.5の範囲になるように調整するなどである。 輝度・色差信号のメジャーな規格にITU-R BT.601、HDTV用の ITU-R BT.709 勧告がある。JPEGやMPEG形式で用いられるカラー信号である。規格書は次で入手できる。また、最近4K/8K用にITU-R BT.2020が勧告された。 https://www.itu.int/rec/R-REC-BT.601/en https://www.itu.int/rec/R-REC-BT.709/en https://www.itu.int/rec/R-REC-BT.2020/en ITU-R BT.601では、Yと色差
/proc/cpuinfo: 全点対間最短路を高速に求める
フィックスターズは今年も ACM ICPC つくば大会 にスポンサーとして協賛しております。今年はコンテスト後の懇親会でクイズを出題しているのですが、その問題準備の際に作ったはいいものの結局使われなかったコードが大量に出てきてしまったため、それらをまとめて簡単な解説とともに公開いたします。 全点対間最短路問題 全点対間最短路問題はN個の頂点を持つ有向グラフにおける任意の2点間の最短路を求める問題です。密なグラフの全点対間最短路を求めるアルゴリズムとしてワーシャル-フロイド法が広く知られており、以下のような非常にシンプルなコードで求めることができます。 // 入力: A[i][j] = 頂点iと頂点jを結ぶ辺の重み // 出力: A[i][j] = 頂点iから頂点jまでの最短路の重みの総和 for(int k = 0; k < N; ++k) for(int i = 0; i < N; ++
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
n個の球をm個の箱に分ける方法
はてなブックマークにおけるアクセス制御 - 半環構造に基づくモデル化
