理論的計算量の見積もりに関して - その1

計算量の見積り方法はアルゴリズム分野において重要な意味を持っている。同様のことを行う場合、より計算量が小さいアルゴリズムを選択することでより効率的に処理を終える事ができる。しかしながら、実際にソフトウェアを書くことを想定すると、計算量でつく優劣が計算機上の性能の優劣と必ずしも一致しない場合も少なくない。

例を挙げて説明していく。

1. Sorting
アルゴリズム分野にいる人であれば QuickSort は平均では θ(nlogn) だが、最悪時 O(n^2) となってしまうという共通知識が存在する。特に O(n^2) になってしまうときはすでに並び替えが終わっている(昇順 or 降順)場合である。そのため、並び替えが終わったデータ列に対して QuickSort を行うと非常に遅いとされてきた。

QuickSort のプログラムを組んだことのある方は当たり前のことと知っておられるかと思うが、実際、実行時間はそうならない。

ex. 58M のデータの並び替え
環境: Intel Xeon X5460 3.16GHz / GCC 4.1.2

未ソートデータ列に対する QuickSort(K&R) : 8.57s
ソート済データ列に対する QuickSort(K&R) : 5.21s

このようにソート済みの方が実行時間が短い。sorting における計算量では比較回数を基準に見積もっているため、このような現象が起きる。比較演算に比べ swap 演算はコストが非常に大きい。

struct aline_t {
  int tail, head, length;
};

static __inline__ void swap(int i, int j, aline_t *a) {
  aline_t t = a[j];
  a[j] = a[i];
  a[i] = t;
}

void kr_qsort(int left, int right, aline_t *a) {
  int i, m;
  if (left >= right || right == -1) return;
  swap(left, left + (right - left)/2, a);
  m = left;
  for (i = left+1; i  right; i++) {
    if (a[i].head  a[left].head) {
      swap(++m, i, a);
    }
  }
  swap(left, m, a);
  kr_qsort(left, m-1, a);
  kr_qsort(m+1, right, a);
}