DBMの設計と実装 その3 ハッシュロック

今回の設計の要点の一つは、並列性である。ハッシュテーブルを保護するにあたって利用するスロットロック法について考察してみたい。

DBMの設計と実装 その2 APIの草案

DBMのAPIをほぼ決めて文書にまとめた。その解説をしよう。文書はここに置いてある。

DBMの設計と実装 その1 ハッシュ関数

個々のレコードがハッシュテーブル内のどのバケットに属するかはハッシュ関数で決める。入力値の種類によらずハッシュ値がうまいことばらけて衝突が起こりにくい関数が良い。今回は定番のMurmur hashを採用した。Rubyの文字列型のハッシュ関数もこれだ。

DBMの設計と実装 その0 全体の計画

DBMの設計と実装について20回くらいに分けて書いてみる。まずは全体の計画と意気込みから。

3月の生活

3月の生活を振り返ってみる。三月に入るところでちょうど近所のオカメザクラが満開になっていよいよ春本番だなと感じた。

バッチで文字列探索する際の性能

コロナ騒ぎであまり外に出られないこの情勢では、せっかくだから文化系の活動をしようじゃないかと思うわけだ。以前の記事で、息抜きに文字列探索法の比較をしてみた。今回は、バッチ処理の場合の傾向を見てみる。

2月の生活

いろいろゴタゴタしていて書き損ねていたが、2月の生活を綴ってみる。沈丁花の香りがしてきて、春もすぐそこだ、と思いつつ過ごしていた。

文字列探索法の比較

文字列探索のアルゴリズムで有名なものとして、ナイーブな力任せ法とKMP法とBM法とRK法の4つがある。実際問題として多くのケースでは力任せ法が十分に早いし作業空間も最小なので、C++標準ライブラリのstring::findは力任せ法で実装されている。KMP法は理論的な計算量は優れているが処理が複雑になるので現実的には遅く、BM法は前処理の作業空間を多少食う代わりに文字種が多いケースでは早いことが知られている。RK法は多数のパターンを同時に検出したい場合に効率が良い。と、いろんなところに書いてある。でも具体的にどんなデータでどんな違いが出るのか自分でも確かめてみたい。

1月の生活

新型コロナウイルスが世間を賑わせるなか、当家ではインフルエンザが猛威をふるい、下の子と上の子が立て続けに罹患してしまった。同時にかかればまだマシなのだが、ずれてかかるものだから、隔離の都合で生活しづらくて仕方なかった。

ハワイの思い出

年末年始はハワイで過ごしてきた。ハワイ旅行なんてのは、欽ちゃんの仮装大賞で優勝したくらいでないと行けない夢のような話と子供の頃は思っていた。しかし、大人になると意外に行けるもので、今回で3回目だ。出張で貯めたマイルのおかげなんだけど。