株式会社エス・スリー・フォー

stx::basic_symbol<T>

より速い検索を行なうには…

STLが提供するset(multiset)/map(multimep)は要素の大小関係に基づいてコンテナ内の要素を2進木上に配置します。このとき、挿入/削除/検索に要する時間計算量は(コンテナ内の要素数をNとして)logNです。

以下に示すコードは、int/stringをキーとするmapの検索に要する時間を計測するものです。

#include <windows.h>
#include <iostream>
#include <string>
#include <map>

using namespace std;

const int N = 1000;

int                int_table[N];
string             string_table[N];

void init() {
  char buf[32];
  string key;
  for ( int i = 0; i < N; ++i ) {
    int_table[i] = i;
    sprintf(buf,"string as comparison key:%d",i);
    string_table[i] = buf;
  }
}

template<class Container, class T>
long trial(Container& container, const T* table, int repeat) {
  int i;
  // table[0..N-1]をcontainerに挿入する。
  for (i = 0; i < N; ++i)
    container[table[i]] = i;

  // table[0..N-1]をcontainerから検索し、その処理時間を求める。
  long t = GetTickCount();
  while ( repeat-- )
    for ( i = 0; i < N; ++i)
      container.find(table[i]);
  return GetTickCount() - t;
}

int main() {

  map<int,int>           intmap;
  map<string,int>        strmap;

  init();

  cout << "intmap " << trial(intmap, int_table,    100) << " [ms]\n";
  cout << "strmap " << trial(strmap, string_table, 100) << " [ms]\n";

  return 0;
}

このように、同じmapであっても、intとstringでは処理速度に大きな差があることがわかります。stringをキーとするmapはなぜこんなに遅いのでしょう。

それは、stringの比較に要する時間がintに比べ非常に大きいからです。

2つのstring a, bを比較するには、 (i = 0 を初期値として)a[i]とb[i]を比較します。このとき a[i] != b[i] であればその時点で大小の判断が完了しますが、a[i] == b[i]であったときは、さらにその次の文字a[i+1]とb[i+1]について比較しなければなりません。

すなわち、文字列の比較は、比較される文字列が長いほど時間がかかることになります。上の例のように末尾だけが異なるような文字列ではその傾向が顕著です。

このように、大小の比較に時間のかかる要素をキーとするsetやmapはかなり遅いものとなります。もし要素の大小比較が瞬時にして完了するなら、set/mapからの要素の挿入/削除/検索スピードを劇的に改善できそうです。

たとえば文字列に対しユニークな数値を与える、すなわち文字列から数値への変換が定義できれば、set<string> は set<int> と同程度のスピードが見込めることでしょう。ただしこの変換を行なうとset内ではもはや文字列の大小関係に基づいた要素管理は行なわれませんから、コンテナ内の要素の格納順は予測できないものとなります。

文字列から数値への変換の最も高速なものはポインタです。すなわち、set<string>の代わりにset<string*>を使えば、set<int>並みのスピードが期待できます。

set<string*> spset;
string value = "apple";
spset.insert(&value);
...
set<string*>::iterator it = spset.find(&value);
...

しかしこれでは問題が発生します。

set<string*> spset;
string value = "apple";
spset.insert(&value);
...
string key = "apple";
set<string*>::iterator it = spset.find(&key);
...

上記のコードにおいてkeyとvalueの値は等しい(“apple”)のですが、ポインタ値は異なるので、set<string*>からvalueを検索できません。等しい要素からは等しい数値(ポインタ値)を対応付けなければなりません。

それを実現するのがbasic_symbolなのです。

ソースコード

#include <set>
#include <string>

namespace stx {

  template<class Key, class Comp =std::less<Key> >
  class basic_symbol {
  public:
    typedef unsigned long            hash_type;
    typedef Key                      key_type;

    basic_symbol()
      { k = &(*key_pool().insert(key_type()).first); }
    basic_symbol(const key_type& key)
      { k = &(*key_pool().insert(key).first); }
    basic_symbol(const basic_symbol& sym)
      : k(sym.k) {}

    basic_symbol& operator=(const basic_symbol& sym)
      { k = sym.k; return *this; }
    basic_symbol& operator=(const key_type& key)
      { k = &(*key_pool().insert(key).first); return *this; }

    const key_type& key() const  { return *k; }
    hash_type hash() const       { return hash_type(k); }
  
  private: 
    typedef std::set<key_type, Comp> pool_allocator;
    static pool_allocator& key_pool();
    const key_type* k;

  };

  template<class Key, class Comp>
  basic_symbol<Key,Comp>::pool_allocator& 
  basic_symbol<Key,Comp>::key_pool() {
    static pool_allocator pool;
    return pool;
  }

  template<class K, class C>
  inline bool operator==(const basic_symbol<K,C>& x, const basic_symbol<K,C>& y)
      { return x.hash() == y.hash(); }

  template<class K, class C>
  inline bool operator!=(const basic_symbol<K,C>& x, const basic_symbol<K,C>& y)
      { return x.hash() != y.hash(); }

  template<class K, class C>
  inline bool operator<(const basic_symbol<K,C>& x, const basic_symbol<K,C>& y)
      { return x.hash() < y.hash(); }

  template<class K, class C>
  inline bool operator<=(const basic_symbol<K,C>& x, const basic_symbol<K,C>& y)
      { return x.hash() <= y.hash(); }

  template<class K, class C>
  inline bool operator>(const basic_symbol<K,C>& x, const basic_symbol<K,C>& y)
      { return x.hash() > y.hash(); }

  template<class K, class C>
  inline bool operator>=(const basic_symbol<K,C>& x, const basic_symbol<K,C>& y)
      { return x.hash() >= y.hash(); }

  typedef basic_symbol<std::string>  string_symbol;
  typedef basic_symbol<std::wstring> wstring_symbol;

}

basic_symbolのからくり

basic_symbol<T>はその内部にset<T>のインスタンス’pool’をstaticメンバとして持っており、これが生成されたすべてのsymbolを抱き込んでいます。

symbolが生成されるとき、同じsymbolが既にpool内にあればそのsymbolのポインタを返します。そうでなければ新たに生成してpoolに登録し、そのポインタを返します。

こうすることでstring_symbol x("apple") と string_symbol y("apple")は同じ値(ポインタ値)を持つわけです。

コンストラクタ

basic_symbol()

key_type()を基にsymbolを生成します(したがってkey_typeはデフォルトコンストラクタが定義されていなければなりません)。

basic_symbol(const key_type& key)

keyに基づいてユニークな値を持つsymbolを生成します。

basic_symbol(const basic_symbol& sym)

symの持つsymbol値(ポインタ値)がコピーされます。

コピー演算子

basic_symbol& operator=(const basic_symbol& sym)

symの持つsymbol値(ポインタ値)がコピーされます。

basic_symbol& operator=(const key_type& key)

keyに基づいてユニークな値を持つsymbolがセットされます。

key / hash

const key_type& key() const

symbol値に対応するkey_typeを返します。

hash_type hash() const

symbol値を返します。

サンプルコード

冒頭に示したコードをbasic_symbolで書き換えてみました。

#include <windows.h>
#include <iostream>
#include <string>
#include <stx/symbol>
#include <map>

using namespace std;

const int N = 1000;

string             string_table[N];
stx::string_symbol symbol_table[N]; 

void init() {
  char buf[32];
  string key;
  for ( int i = 0; i < N; ++i ) {
    sprintf(buf,"string as comparison key:%d",i);
    string_table[i] = buf;
    symbol_table[i] = stx::string_symbol(buf);
  }
}

template<class Container, class T>
long trial(Container& container, const T* table, int repeat) {
  // ...省略...
}

int main() {

  map<std::string,int>        strmap;
  map<stx::string_symbol,int> symmap;

  init();

  cout << "strmap " << trial(strmap, string_table, 100) << " [ms]\n";
  cout << "symmap " << trial(symmap, symbol_table, 100) << " [ms]\n";

  return 0;
}

…効果は歴然ですね。