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

自己組織化検索

一般的に、'検索'すなわちある要素の集合の中から特定の条件を満足する要素を探し出す処理はアプリケーションの中で比較的頻繁に行われます。したがって検索のスピードはアプリケーションのパフォーマンスに大きな影響を与えます。

検索の条件にある一定の制限を与えることで検索に要する時間を劇的に短縮することが可能です。
たとえば要素に大小関係を定義することができるなら、標準C++ライブラリが提供するsetやmapを要素の集合に利用すれば、検索に要する時間を集合中の要素数のlogに比例する程度に抑えることができます。要素の集合を要素の大小関係に基づいて昇順/降順に並べておくことで2分検索(binary-seach)を行う事ができるからです。

しかし上記のように要素の大小関係を定義できない、あるいは要素の大小関係が検索時間の短縮に何の意味も与えないこともしばしばです。
たとえば文字列の集合の中から特定の単語を含む文字列を探し出す、いわゆる'全文検索'の場合、検索の対象となる文字列をその大小関係に基づいて並べて置いても、それによって検索時間を短縮することはできません。文字列の大小関係は検索対象である単語(部分文字列)を含むか否かとはまったく関係がなく、検索対象の絞り込みの手がかりを与えてはくれないからです。
結局のところ集合内の各要素に対しひとつずつ条件を満足するかを調べることになります。

n個の要素からなる順序集合a[0..n-1]から特定の条件を満たす要素を見つけだすとき、検索対象の絞り込みの手がかりがなにもないのであれば、順に並んだ要素の列に対し、先頭の要素から順に検索するしかありません。このことは順序集合の末尾に近い位置に置かれた要素ほど、その検索には時間を要することを意味します。逆に、順序集合の先頭に近い位置に置かれた要素ほど、その検索は高速です。

ということは、検索条件にバラツキがあるなら、頻繁に用いられる検索条件を満足する要素を順序集合の先頭に近い位置に置くことで、'統計的'に検索時間を短縮できることになります。

'自己組織化検索'とは、順序集合から特定の要素を検索した後、検索によって見つかった要素をより前方(順序集合の先頭に近い位置)にズラす処理を行います。そうすれば、次回おなじ要素を検索するときに要する時間はより短くなります。

検索によって見つかった要素をより前方にズラすからくりをいくつか考えてみました。

find_and_swap_previous : ひとつ前の要素と入れ替える
順序集合[first,last)からある要素を検索し、位置pointで見つかったとき、*pointと*(point-1)とを入れ替えます。これによって検索時間が少しずつ短くなります。
find_and_rotate : 順序集合の先頭に持ってくる(1)
[1]の方法では大きな性能向上は望めません。そこで、順序集合の先頭(first)から見つかった位置まで[first,point+1)を回転します。すなわち検索によって見つかった要素が常に順序集合の先頭に位置するように移動します。
find_and_rotate_container : 順序集合の先頭に持ってくる(2)
[2]ではfirstからpointまでの要素を順にコピーしなければなりませんから、順序集合の末尾にある要素を先頭に移動するのにかなりの時間を要します。しかし順序集合が線形リストであった場合は集合からpointを削除し、先頭に挿入することで実現できます。

以下のコードは上記3つのアルゴリズムを実装し、実行時間を計測するプログラムです。

筆者の環境(Windows2000, Microsoft visual C++ 6.0)では以下のような結果が得られました:

algorithm	time [ms]
std::find	8112
find_and_swap_previous	7731
find_and_rotate	90
find_and_rotate_container	70

ご覧の通り、裸の順次検索(std::find)に比べ、自己組織化検索はより速いことが確認できます。

ただし、自己組織化検索は検索対象に十分な偏りがない場合、要素の移動が頻繁に行われるため、結果的に順次検索より遅くなることも起こり得ます。

また、find_and_rotate_containerは順序集合が線形リストであった場合にのみ効果を発揮します。これがたとえばvectorであったとき、順次検索より遅くなることもあるでしょう。ぜひお試しください。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <windows.h> // GetTickCount

/*
 * 自己組織化検索 self-organizing-search
 * その1 : ひとつ手前の要素と交換
 */
template<typename ForwardIterator, typename T>
ForwardIterator
find_and_swap_previous(ForwardIterator first, ForwardIterator last, const T& value) {
  ForwardIterator found = std::find(first, last, value);
  if ( found != last && found != first ) {
    ForwardIterator swap = found; --swap;
    std::iter_swap(found,swap);
    return swap;
  }
  return found;
}

template<typename ForwardIterator, typename Predicate>
ForwardIterator
find_and_swap_previous_if(ForwardIterator first, ForwardIterator last, Predicate pred) {
  ForwardIterator found = std::find_if(first, last, pred);
  if ( found != last && found != first ) {
    ForwardIterator swap = found; --swap;
    std::iter_swap(found,swap);
    return swap;
  }
  return found;
}

/*
 * 自己組織化検索 self-organizing-search
 * その2 : 先頭の要素との間でrotate
 */
template<typename ForwardIterator, typename T>
ForwardIterator
find_and_rotate(ForwardIterator first, ForwardIterator last, const T& value) {
  ForwardIterator found = std::find(first, last, value);
  if ( found != last && found != first ) {
    ForwardIterator limit = found; ++limit;
    std::rotate(first, found, limit);
    return first;
  }
  return found;
}

template<typename ForwardIterator, typename Predicate>
ForwardIterator
find_and_rotate_if(ForwardIterator first, ForwardIterator last, Predicate pred) {
  ForwardIterator found = std::find_if(first, last, pred);
  if ( found != last && found != first ) {
    ForwardIterator limit = found; ++limit;
    std::rotate(first, found, limit);
    return first;
  }
  return found;
}

/*
 * 自己組織化検索 self-organizing-search
 * その2 : 先頭の要素との間でrotate
 */
template<typename Container, typename T>
Container::iterator
find_and_rotate_container(Container& container, Container::iterator first, Container::iterator last, const T& value) {
  Container::iterator found = std::find(first, last, value);
  if ( found != last && found != first ) {
    Container::value_type value = *found;
    container.erase(found);
    container.insert(container.begin(), value);
    return container.begin();
  }
  return found;
}

template<typename Container, typename Predicate>
Container::iterator
find_and_rotate_container_if(Container& container, Container::iterator first, Container::iterator last, Predicate pred) {
  Container::iterator found = std::find_if(first, last, pred);
  if ( found != last && found != first ) {
    Container::value_type value = *found;
    container.erase(found);
    container.insert(container.begin(), value);
    return container.begin();
  }
  return found;
}

#define for if(false);else for

int main() {

  typedef int item;
  typedef std::list<item> container;

  const size_t N = 10000;
  const size_t M = 5;
  /*
   * 検索対象
   */
  container c;
  container::iterator it;
  for ( int i = 0; i < N; ++i ) c.push_back(i);

  /*
   * 偏りのある検索対象群
   */
  item target[N];
  for ( int i = 0; i < N; ++i ) target[i] = N - (i % 100) -1;
  std::random_shuffle(target, target+N);

  unsigned long tt;

  /* 通常の線形検索
   */
  tt = ::GetTickCount();
  for ( int j = 0; j < M; ++j )
  for ( int i = 0; i < N; ++i ) {
    it = std::find(c.begin(), c.end(), target[i]);
    if ( it == c.end() || *it != target[i] )  {
      std::cout << "BAD!!\n";
      return 1;
    }
  }
  std::cout << "std::find : " << ( GetTickCount() - tt ) << "[ms]\n";

 /* 自己組織化検索 self-organizing-search
  * その1 : ひとつ手前の要素と交換 */
  tt = ::GetTickCount();
  for ( int j = 0; j < M; ++j )
  for ( int i = 0; i < N; ++i ) {
    it = find_and_swap_previous(c.begin(), c.end(), target[i]);
    if ( it == c.end() || *it != target[i] )  {
      std::cout << "BAD!!\n";
      return 1;
    }
  }
  std::cout << "find_and_swap_previous : " << ( GetTickCount() - tt ) << "[ms]\n";

  c.clear();
  for ( int i = 0; i < N; ++i ) c.push_back(i);

 /* 自己組織化検索 self-organizing-search
  * その2 : 先頭の要素との間でrotate */
  tt = ::GetTickCount();
  for ( int j = 0; j < M; ++j )
  for ( int i = 0; i < N; ++i ) {
    it = find_and_rotate(c.begin(), c.end(), target[i]);
    if ( it == c.end() || *it != target[i] )  {
      std::cout << "BAD!!\n";
      return 1;
    }
  }
  std::cout << "find_and_rotate : " << ( GetTickCount() - tt ) << "[ms]\n";

  c.clear();
  for ( int i = 0; i < N; ++i ) c.push_back(i);

#if 1
 /* 自己組織化検索 self-organizing-search
  * その2 : 先頭の要素との間でrotate */
  tt = ::GetTickCount();
  for ( int j = 0; j < M; ++j )
  for ( int i = 0; i < N; ++i ) {
    it = find_and_rotate_container(c, c.begin(), c.end(), target[i]);
    if ( it == c.end() || *it != target[i] )  {
      std::cout << "BAD!!\n";
      return 1;
    }
  }
  std::cout << "find_and_rotate_container : " << ( GetTickCount() - tt ) << "[ms]\n";
#endif

  return 0;
}

επιστημη 2006-04-05