Bep: 最小完全ハッシュ関数を用いた連想配列
Bepという連想配列のライブラリを公開しました。BSDライセンスです．
キーは文字列限定で，前もって大量のキーと値のペアが前もって分かっている場合（１千万個とか）、使ってもらえるよう最適化しています。（一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています）
特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです．今のところ１千万キーぐらいで動作するのは確認しています．１キーあたり必要な作業領域量は大体3bit + キー自体の長さになります．
最小完全ハッシュ関数の構築自体も面白い問題です．最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました．3-ハイパーグラフの頂点割り当て問題を解くことで完全ハッシュ関数を作ってます．
各キー３つのハッシュ値、a,b,cを独立に計算し、その３つのハッシュ値を頂点として持つ枝を作ります．で、この頂点、枝からなるグラフを作ります．このグラフが閉路を持たない場合、各キーに枝中の一つの頂点を他のキーと重複しないように割り当てていくことができます．でこの頂点番号をハッシュ値として使います．
Botelho, F.C., Pagh, R. and Ziviani, N. "Simple and Space-Efficient Minimal Perfect Hash Functions" 10th International Workshop on Algorithms and Data Structures (WADS07) August 2007, 139-150
（これ(pdf)を使いました）．
あと中でいろいろチューニングしてます。
コンパイルできない、結果間違ってる、バグってる、使いづらいとかありましたら連絡ください。できるだけ改善するようにします。よろしくお願いします。
txも地味にアップデートしてます。こちらもいろいろ使ってもらっているようです。
Comments
前いってた自作DBで使う予定のハッシュをC#で実装してます。特徴は
重複を許し、Interlockedクラスを使ってロックフリーでマルチスレッド対応、削除、更新は考慮しない。
読み込み、書き込みともに並列化できますが、大容量になるとcpu固有のキャッシュではなく共有メモリをアクセスするので並列度が下がります。
Interlockedの実装のようなコンペアアンドスワップ、コンペアアンドアッド、セットアンドテスト(だっけ？)を利用するとかなり軽く作れますね。スピンロックするときは特に最適です。
ついでにマルチスレッドクイックソート作ってみました。確かに並列化できてパフォーマンスあがりましたが上位の大きな分割はマルチスレッドできないのでここが並列度を上げれない原因です。何とか分割処理をInterlocked使って並列にやってみましたがオーバヘッドの方が大きくうまくいきませんでした。
Posted by: 和 | 2007.11.03 at 09:19 AM
まだokaさんの最小完全ハッシュ見てませんが、高速に出来るのであれば理解してDB用に実装してみたいと思います。
Posted by: 和 | 2007.11.03 at 10:12 AM
ぜひよろしければソースコードとかサンプルコードを公開していただけると勉強できるので教えてください。
マルチスレッドになってさらに局所性（しかも4kBとか8kBとかのオーダー）が求められるのはアルゴリズム考える側としても面白い問題ですね。
Posted by: oka | 2007.11.04 at 12:16 PM
ごめんなさい。今度こそ大丈夫です。これ以前のコードを削除してもらえませんか？
探索テスト用のスレッドを作って並列化していないのが原因でした。やはりきれいに2倍にはならないですがそこそこ早くなります。
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.Diagnostics;
struct 構造体 {
public Double キー;
public Double データ;
}
unsafe class 並列ハッシュ{
public static int CPU数=1;//Environment.ProcessorCount;//で実CPU数になる
static int ハッシュ要素数_;
static 構造体* pデータ配列;
static Int64* pハッシュ配列;
delegate void ハッシュ配列null初期化delegate(int ハッシュ開始,int ハッシュ終了);
private static void ハッシュ配列null初期化(int ハッシュ開始,int ハッシュ終了) {
Int64* ppハッシュ配列=(Int64*)pハッシュ配列;
for(int a=ハッシュ開始;aキー==キー) return pデータ;
ハッシュ値=(ハッシュ値+1)%ハッシュ要素数_;
if(ハッシュ値==開始ハッシュ値) return null;
}
}
private static void データ配列から重複有りハッシュ配列作成(int データ開始,int データ終了) {
for(int a=データ開始;aキー==キー) {
if(Interlocked.CompareExchange(ref pハッシュ配列[ハッシュ値],unchecked((Int64)0xFFFFFFFFFFFFFFFF),pハッシュ)==pハッシュ) {
return p構造体;
}
}
}
ハッシュ値=(ハッシュ値+1)%ハッシュ要素数_;
if(ハッシュ値==開始ハッシュ値) return null;
}
}
}
unsafe class A {
const int データ数 =1000000;
const int ハッシュ要素数=1100000;
static 構造体[] データ配列=new 構造体[データ数];
static Int64[] ハッシュ配列=new Int64[ハッシュ要素数];
delegate void 探索delegate(int 開始,int 終了);
static void 重複無し探索(int 開始,int 終了) {
for(int a=開始;aキー==キー);
Debug.Assert(pデータ->データ==pデータ->キー*2);
}
}
static void 重複有り探索(int 開始,int 終了) {
for(int a=開始;aキー==キー);
Debug.Assert(pデータ->データ==pデータ->キー*2);
}
}
static void Main() {
TimeSpan 重複無し初期化時間,重複無し検索時間;
{
for(int a=0;a<データ数;a++) {
データ配列[a].キー=(Double)a;
データ配列[a].データ=データ配列[a].キー*2;
}
fixed(構造体* pデータ配列_=&データ配列[0]) {
fixed(Int64* pハッシュ配列_=&ハッシュ配列[0]) {
DateTime t1=DateTime.Now;
並列ハッシュ.データ配列から重複無しハッシュ配列作成(pハッシュ配列_,ハッシュ要素数,pデータ配列_,データ数);
重複無し初期化時間=DateTime.Now.Subtract(t1);
DateTime t2=DateTime.Now;
探索delegate T=new 探索delegate(重複無し探索);
IAsyncResult[] IAsyncResults=new IAsyncResult[並列ハッシュ.CPU数-1];
for(int a=0;a<並列ハッシュ.CPU数-1;a++) {
IAsyncResults[a]=T.BeginInvoke(データ数*a/並列ハッシュ.CPU数,データ数*(a+1)/並列ハッシュ.CPU数,null,null);
}
重複無し探索(データ数*(並列ハッシュ.CPU数-1)/並列ハッシュ.CPU数,データ数*並列ハッシュ.CPU数/並列ハッシュ.CPU数);
for(int a=0;a<並列ハッシュ.CPU数-1;a++) {
T.EndInvoke(IAsyncResults[a]);
}
重複無し検索時間=DateTime.Now.Subtract(t2);
}
}
}
TimeSpan 重複有り初期化時間,重複有り検索時間;
{
for(int a=0;a<データ数;a++) {
データ配列[a].キー=(Double)a/4;
データ配列[a].データ=データ配列[a].キー*2;
}
fixed(構造体* pデータ配列_=&データ配列[0]) {
fixed(Int64* pハッシュ配列_=&ハッシュ配列[0]) {
DateTime t1=DateTime.Now;
並列ハッシュ.データ配列から重複有りハッシュ配列作成(pハッシュ配列_,ハッシュ要素数,pデータ配列_,データ数);
重複有り初期化時間=DateTime.Now.Subtract(t1);
DateTime t2=DateTime.Now;
探索delegate T=new 探索delegate(重複有り探索);
IAsyncResult[] IAsyncResults=new IAsyncResult[並列ハッシュ.CPU数-1];
for(int a=0;a<並列ハッシュ.CPU数-1;a++) {
IAsyncResults[a]=T.BeginInvoke(データ数*a/並列ハッシュ.CPU数,データ数*(a+1)/並列ハッシュ.CPU数,null,null);
}
重複有り探索(データ数*(並列ハッシュ.CPU数-1)/並列ハッシュ.CPU数,データ数*並列ハッシュ.CPU数/並列ハッシュ.CPU数);
for(int a=0;a<並列ハッシュ.CPU数-1;a++) {
T.EndInvoke(IAsyncResults[a]);
}
重複有り検索時間=DateTime.Now.Subtract(t2);
}
}
}
}
}
Posted by: 和 | 2007.11.04 at 11:34 PM
あれー中括弧とかが消えてしまう…。
Posted by: 和 | 2007.11.05 at 12:16 PM
うむむ。ここのコメントにソースは書きづらいですねぇ。まぁ気持ちが分かるので大丈夫ですよ。
見慣れない予約語がいろいろある・・
Posted by: oka | 2007.11.05 at 11:05 PM