要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分
新しい数値設定や実装方法を提案するものではありません。 衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。 前提知識 本記事では簡単のため、アルファベットの集合を $\Sigma = \{0,1,\ldots,\sigma-1\}$ とします。英子文字であれば、ASCII コードによりアルファベットを $128$ 未満の整数に対応させたり、それをずらして $26$ 未満の整数に対応させることで、アルファベットを整数と見なせます。 Rolling Hash とは Rolling Hash は、文字列 $S = S_0,S_1,S_2,\ldots$ を次のようにHash化する手法です： 【Rolling Hash】 法 $m$, 基数 $r$ を何らかの方法でとる。 文字列 $S = S_0,S_1,S_2,\ldots$ の Hash値 を$\mathrm{h
高速なハッシュテーブルを設計する | POSTD https://t.co/QdhusBEp6k @POSTDccより これ、読み物としてかなり面白かった 特に設計の方針が
いまどきの将棋ソフトを使っていると、「HASH 50%」などと表示されている。これはHASH利用率と呼ばれる。この数字が大きくなってくると探索の効率が悪くなる。要するに潤沢にメモリがある場合に比べると弱くなる。これは、どれくらいの値までであるなら適切なのか？HASH利用率が99%にならない限りHASHには余裕があるものなのか？HASHはどういう仕組みになっているのか？HASH利用率が50%の状況で、ハッシュ衝突はしているのか？など、わりとソフトを長年使っていても知らない人が多いのでここに原理から詳しく説明した決定版的な記事を書く。 ShogiGUIや将棋神やねうら王に表示されている「HASH」とは何ですか？ 一度探索した局面を保存しておく表です。 この表に登録するときにハッシュ(hash)という値を使って登録するため、ハッシュテーブル(hash table)と呼ばれます。これを略して(値と
りんごさん方式の記事 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい？ multisetのハッシュ、0になりやすいなぁと思ったけど0になる確率がat most n/modなのか。 記事での根付き木のハッシュの取り方を日本語にまとめておきます。 根付き木のハッシュ まず、深さ i に対応する乱数 を [0,mod) から取っておきます。 深さ i の頂点 v について、v 以下の部分木のハッシュは「( + 子のハッシュ)の積」として計算します。 特に、葉のハッシュ値は 1 です。 詳細は実際に記事を読んで下さい。 僕は根付き木のハッシュをどのように取っていたかの話と、それは良くなかったという話と、ならどうすれば良かったかの話をします。 計算法 まず素数p,modを用意する。 ある頂点以下の部分木ハッシュ値は
この記事は特に高速なハッシュアルゴリズムをまとめた資料です。 暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。 MurmurHash 2008年に”Austin Appleby”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。MurmurHash3 は現在のバージョンで、32ビットまたは128ビットのハッシュを生成する。MurmurHash2 は古いバージョンで、32ビットまたは64ビットのハッシュを生成する。64ビットのハッシュ値生成するソースには2つの変種がある。64ビットプロセッサ用に最適化された用の MurmurHash64A と32ビットプロセッサ用に最適化された Mu
C++11 で追加された std::unordered_map は、連想配列を扱うことができる。 以前からある std::map では、キーとして扱えることができるのは 順序関係が定義されたオブジェクトのみである。一方、 std::unordered_map では順序関係が定義されていキーを使うことができ、純粋な連想配列（ハッシュテーブル）として使うことができる。 ただし、 std::unordered_map のキーはハッシュ値へ変換できる必要がある。多くの標準型のように std::hash() でハッシュ値への変換が定義されている型はそのままキーに使うことができるが、自分で定義した型など変換が定義されていない型をキーとして使用する場合はハッシュ計算を行う関数を自分で用意する必要がある。 このハッシュ関数を定義するには、 std::hash() を特殊化する方法と、関数オブジェクトを作成
NLPだとstd::mapとtr1::unordered_mapなら後者を使うことになることが多いと思うけど、あれこれ混乱してきたのでメモる。NLPerなら押さえておくべき常識のはず。。。 それぞれの特徴 データ構造 std::map tr1::unordered_map 実装 赤黒木 ハッシュテーブル find log n Average case: O(1), Worset case: O(n) insert log n Average case: O(1), Worset case: O(n) delete log n Average case: O(1), Worset case: O(n) メリット キーでソート済みなことが保障されているので、ある範囲でiterationさせたいとき、deleteするなどの操作を効率的に行うことができる バケット数を最初にきちんと設定しておけば大
最小完全ハッシュ函数 ハッシュ函数のうち、可逆で、かつ、生成するハッシュ値の値域が最小である函数のことを、最小完全ハッシュ函数と言います。 その作り方を解説していきたいと思います。
今回は、局面の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
Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures [1]) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
中国人科学者のチームが今年、電子メールやウェブ上のデジタル署名の作成／確認に広く利用されている技術の欠陥を発表し、データセキュリティ業界に衝撃を与えた。 現在米国政府は、この問題の解決策を模索している。 10年前に発明されたこの「Secure Hash Algorithm（SHA-1）」と呼ばれるアルゴリズムは、連邦政府の正式な標準で、最近のウェブブラウザやオペレーティングシステム（OS）にはいずれもこのアルゴリズムが組み込まれている。SHA-1に何らかの変更を加えるには多大なコストと時間がかかる--そして、米政府が選択を誤れば、SHA-1の後継規格は10年も持たずに消滅することになるだろう。 「われわれは、国民をどの方向に導くかについて早急に決断を下す必要がある」と語るのは、米連邦標準技術局（National Institute of Standards and Technology：N
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
