Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の4_C問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#4「探索」は、線形探索、二分探索、ハッシュ（辞書）を学びます。
問題（4_C: Dictionary）
問題はリンク先をご覧ください。
ハッシュについて学びます。
ハッシュについて
まず、単独の vector コンテナを使ったプログラムを紹介します。
- vector コンテナ dict に文字列を格納します。
- 文字列を格納する関数 insert を用意します（8ー11行目）。
このプログラムでは、引数を push_back します。 - 文字列を検索する関数 find を用意します（13ー24行目）。
このプログラムでは、引数があるか vector コンテナを全探索します。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> dict;
void insert(string str)
{
dict.push_back(str);
}
bool find(string str)
{
bool result = false;
for (int i = 0; i < dict.size(); ++i) {
if (dict[i] == str) {
result = true;
break;
}
}
return result;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
string command, str;
cin >> command >> str;
if (command == "insert") {
insert(str);
} else if (command == "find") {
if (find(str)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
}
return 0;
}残念ながら、このプログラムは TLE（Time Limit Exceeded）判定となります。$N = 10^6$ です。仮に文字列を $5 \times 10^5$ 回 insert して、存在しない文字列を $5 \times 10^5$ 回 find すると、全体で $ 2.5 \times 10^{11}$ 回のループが発生して、間に合わなくなります。
単独の vector コンテナに値を格納すると、値が存在しない場合にコンテナを最後まで走査します。複数の vector コンテナに値を分けて格納すると、この問題は解決します。
文字列と格納するコンテナを紐づけるためにハッシュ（ハッシュ値）を使います。Wikipedia の「ハッシュ関数」には、「任意のデータから、別の（多くの場合は短い固定長の）値を得るための操作、または、その様な値を得るための関数のこと」とあります。
この問題では、文字列を 0 から 65535 の値に紐づけるようなハッシュ関数を作ります。
C++ プログラム例（ALDS1 4_C）
最初に紹介したプログラムから以下を変更します（main は同一です）。
- vector コンテナは、65536（=216）個用意します（7、8行目）。
- ハッシュ関数 my_hash は、平均的に散らばるように線形合同法の乱数生成を参考にしました。係数は、英語版 Wikipedia の “Linear congruential generator” で紹介されている3番目の例を採用しました（10ー18行目）。
- 関数 insert では、文字列からハッシュを求めて、ハッシュを添え字とするコンテナに文字列を格納します（20－24行目）。
- 関数 find でも、文字列からハッシュを求めて、該当するコンテナが与えられた文字列を含むか判定します（26－38行目）。
216 個のコンテナに分散して格納します。文字列とコンテナの紐づけが十分に散らばれば、コンテナの要素が平均化されて、結果的に少なくなります。
ハッシュ関数に線形合同法を使いました。しかし、線形合同法を実際の乱数に使うには好ましくない場合があるので注意してください。ハッシュ関数に採用したのは、計算量が少ないためです。
以下が、C++プログラムとなります。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long int ull;
#define M 65536
vector<string> dict[M];
ull my_hash(string str)
{
ull result = 0;
for (int i = 0; i < str.length(); ++i) {
result += 22695477ULL * (ull)str[i] + 1ULL;
}
return result % M;
}
void insert(string str)
{
ull h = my_hash(str);
dict[h].push_back(str);
}
bool find(string str)
{
int h = my_hash(str);
bool result = false;
for (int i = 0; i < dict[h].size(); ++i) {
if (dict[h][i] == str) {
result = true;
break;
}
}
return result;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
string command, str;
cin >> command >> str;
if (command == "insert") {
insert(str);
} else if (command == "find") {
if (find(str)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
}
return 0;
}標準ライブラリ set を使う。
「プログラミング応用」（ITP2）の7_A問題で、標準ライブラリとして実装されている set コンテナ を紹介しました。
set コンテナは、二分木で実装されており、ハッシュを使っているわけではありませんが、今回の問題を解くプログラムをすっきりと書くことができます。set を使ったプログラムは以下となります。
#include <iostream>
#include <string>
#include <set>
using namespace std;
set<string> dict;
void insert(string str)
{
dict.insert(str);
}
bool find(string str)
{
return dict.find(str) != dict.end();
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
string command, str;
cin >> command >> str;
if (command == "insert") {
insert(str);
} else if (command == "find") {
if (find(str)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
}
return 0;
}上記プログラムはどちらも、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
ハッシュを使って、格納するコンテナを分けることにより問題を解くことができました。今回の手法は、「ハッシュテーブル」と呼ばれています。今回の実装では、ハッシュテーブルの先を vector コンテナにしましたが、リストを使う方が一般的かもしれません。
引き続き、ALDS1 の問題を紹介していきます。
