ソート・ルーチン

(2) シェル・ソート

前回、比較的単純なソート・ルーチンについて説明しました。この章からは、前回のものに比べて "圧倒的に" 早いソートルーチンについて紹介したいと思います。まずは「シェル・ソート」から紹介します。


1) シェル・ソート(Shell Sort)

「シェル・ソート(Shell Sort)」は、前回紹介した「挿入ソート」を改良したアルゴリズムです。まずは、シェル・ソートの処理の流れを以下に示します。

  1. 適当な「飛び幅」を設定し、配列中の要素をその「飛び幅」ごとに抽出して「群」を作る (但し、実際に各群毎にデータを移動させるわけではない)
  2. 各群をそれぞれ「挿入ソート」で並べ替える
  3. 「飛び幅」を適当に減らしながら、上記操作を繰り返す
  4. 「飛び幅」を 1 として処理を行った時点でソートは完了する

要は、適当な数だけスキップさせながらソートを行うわけですが、最終的には「挿入ソート」と同じ処理をすることになるので正しくソートできることは理解できると思います。通常の「挿入ソート」を行う前に余計な処理を行っている分かえって遅くなるように感じますが、以下の理由によりこの方が速く処理できます。

「挿入ソート」の特徴としては、以下の二点が挙げられます。

  1. ソート時間は、データ数の二乗に比例する
  2. ある程度ソートされたデータ列に対しては高速にソートできる

一番目の特徴は、裏を返せば要素数が半分になるとソート時間は 1 / 4 に短縮され、1 / 3 になれば 1 / 9 ... とデータ数が減少するに従い処理時間は急激に短くなることを意味します。
二番目の特徴も、前回のテスト結果で示したように、ソート済のデータ列に対しては処理時間はゼロに近い値だったことから理解できると思います。
先ほど示した処理を行ったとき、序盤では「飛び幅」の値が大きいため各群のデータ数は非常に少なくなります。よって一番目の特徴から、各群をソートする時間は全体をソートする時間に比べて圧倒的に短くなると考えられます。処理が終盤に近づくと、各群のデータ数は多くなりますが、そのデータ列は前からの処理によって比較的ソートされた状態になっているので、二番目の特徴から、ここでも処理時間は短くなると想像できます。この組み合わせが「シェル・ソート」の早さの秘密です。

このアルゴリズムは、「ドナルド・L・シェル (Donald L. Shell)」によって考案されたため「シェル・ソート(Shell Sort)」と名付けられています。

シェル・ソートを使い、8 個の要素を飛び幅 4, 2, 1 で処理した場合の様子を下図に示します。

表 1-1. シェル・ソートによる並べ替えの例
初期状態5145116739812875
飛び幅 4 で分割5139
4581
1128
6775
各群をソート3951
4581
1128
6775
飛び幅 2 で分割39115128
45678175
各群をソート11283951
45677581
飛び幅 1 で分割1145286739755181
各群をソート1128394551677581

シェル・ソートのサンプル・プログラムを以下に示します。

/*
  ShellSort : シェル・ソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void ShellSort( Ran first, Ran last, Less less )
{
  // 反復子の要素の型
  typedef typename Ran::value_type value_type;
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  for ( difference_type gap = ( last - first ) / 2 ; gap > 0 ; gap /= 2 ) {
    for ( difference_type i = 0 ; i < gap ; ++i ) {
      for ( Ran e = first + gap + i ; e < last ; e += gap ) {
        value_type v = *e;     // 未ソート列の先頭の要素を取得
        bool inserted = false; // v が挿入されたか
        for ( Ran s = e - gap ; s >= first ; s -= gap ) {
          if ( less( v, *s ) ) {
            *(s + gap) = *s;
          } else {
            *(s + gap) = v;
            inserted = true;
            break;
          }
        }
        // v が未挿入の場合は先頭に要素を代入
        if ( ! inserted ) *( first + i ) = v;
      }
    }
  }
}

飛び幅が変数 gap となっている以外、最も内側にある二重ループ処理の内容は「挿入ソート」と全く同じです。その外側のループで変数 i の値をゼロから gap - 1 まで増加させているところが、飛び幅で分割した各群ごとの「挿入ソート」処理を行っている部分です。一番外側のループでは飛び幅の大きさが 1 になるまで gap の大きさを半分にしています。よって、最終的には飛び幅 1 での処理、すなわち「挿入ソート」と全く同じ処理が行われることになります。なお、このサンプル・プログラムでは gap の初期値をデータ列の大きさの半分にしています。


2) コム・ソート

ソート済みの配列に対する処理が速いアルゴリズムとしては「挿入ソート」だけでなく「(改良版)バブル・ソート」に代表される「交換ソート」も該当します。従って、「シェル・ソート」と同様な考え方を「交換ソート」に対して適用しても、処理は高速になることが期待できます。「バブル・ソート」に対して「シェル・ソート」と同じ手法を用いたアルゴリズムを「コム(櫛)・ソート(Comb Sort)」と言います。このアルゴリズムは、1980 年に「Włodzimierz Dobosiewicz」によって最初に考案されましたが、このときはあまり注目されなかったようです。その後、「Stephen Lacey」と「Richard Box」によって「Byte Magazine」の 1991 年 4 月号で再び発案され、それから一般に知られるようになりました。

処理の流れはシェル・ソートと変わらず、内側の処理が「挿入ソート」から「バブル・ソート」に変化しただけです。コム・ソートのサンプル・プログラムを以下に示します。

/*
  CombSort : コム・ソートによるソート・ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void CombSort( Ran first, Ran last, Less less )
{
  // 最後に要素を交換した位置(後ろ側を指す)
  Ran sorted;

  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  for ( difference_type gap = ( last - first ) / 2 ; gap > 0 ; gap /= 2 ) {
    for ( difference_type i = 0 ; i < gap ; ++i ) {
      for ( Ran e = last ; e > first ; e = sorted ) {
        sorted = first; // 先頭の位置で sorted を初期化
        for ( Ran s = first + gap + i ; s < e ; s += gap ) {
          if ( less( *s, *(s - gap) ) ) {
            swap( s - gap, s );
            sorted = s;
          }
        }
        // 一度も交換がなければ終了
        if ( sorted == first ) break;
      }
    }
  }
}

「交換ソート」の中で、ソート済み配列に対して処理が速いアルゴリズムには他に「シェーカー・ソート」「奇偶転置ソート」「ノーム・ソート」が挙げられます。これらに対しても同様の変更を行った場合のサンプル・プログラムを併せて示しておきます。

/*
  CombSort_Shaker : コム・ソートによるソート・ルーチン(シェーカー・ソート版)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void CombSort_Shaker( Ran first, Ran last, Less less )
{
  --last;

  // 最後に要素を交換した位置(後ろ側を指す)
  Ran sorted;

  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  for ( difference_type gap = ( last - first + 1 ) / 2 ; gap > 0 ; gap /= 2 ) {
    for ( difference_type i = 0 ; i < gap ; ++i ) {
      Ran s = sorted = first + i; // 開始位置 + i で s と sorted を初期化
      Ran e = last;               // 末尾位置で e を初期化

      while ( e > s ) {
        /* 配列先頭からバブル・ソート */
        for ( Ran r = s + gap ; r <= e ; r += gap ) {
          if ( less( *r, *( r - gap ) ) ) {
            swap( r - gap, r );
            sorted = r;
          }
        }
        if ( sorted == s )
          break;
        else
          e = sorted;

        /* 配列末尾からバブル・ソート */
        for ( Ran r = e ; r > s ; r -= gap ) {
          if ( less( *r, *( r - gap ) ) ) {
            swap( r - gap, r );
            sorted = r;
          }
        }
        if ( sorted == e )
          break;
        else
          s = sorted;
      }
    }
  }
}

/*
  CombSort_OddEven : コム・ソートによるソート・ルーチン(奇偶転置ソート版)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void CombSort_OddEven( Ran first, Ran last, Less less )
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  for ( difference_type gap = ( last - first ) / 2 ; gap > 0 ; gap /= 2 ) {
    for ( difference_type i = 0 ; i < gap ; ++i ) {
      bool sorted = false; // ソートが完了したか
      while ( ! sorted ) {
        sorted = true;
        /* 偶・奇ペアでのソート */
        for ( Ran r = first + gap + i ; r < last ; r += gap * 2 ) {
          if ( less( *r, *(r - gap) ) ) {
            swap( r - gap, r );
            sorted = false;
          }
        }

        /* 奇・偶ペアでのソート */
        for ( Ran r = first + gap * 2 + i ; r < last ; r += gap * 2 ) {
          if ( less( *r, *(r - gap) ) ) {
            swap( r - gap, r );
            sorted = false;
          }
        }
      }
    }
  }
}

/*
  CombSort_Gnome : コム・ソートによるソート・ルーチン(ノーム・ソート版)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
*/
template<class Ran, class Less> void CombSort_Gnome( Ran first, Ran last, Less less )
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  for ( difference_type gap = ( last - first ) / 2 ; gap > 0 ; gap /= 2 ) {
    for ( difference_type i = 0 ; i < gap ; ++i ) {
      for ( Ran r = first + gap + i ; r < last ; r += gap ) {
        do {
          if ( ! less( *r, *( r - gap ) ) ) break;
          swap( r - gap, r );
          r -= gap;
        } while ( r >= first + gap );
      }
    }
  }
}

飛び幅が可変となることで多少の変更はされているものの、前回の内容をほとんど流用して作成することができます。


3) シェル・ソートの高速化

シェル・ソートやコム・ソートは、すでに今まで紹介したソートルーチンよりも圧倒的に速く処理することができるようになっています。しかし、パラメータを最適化することによって、さらに高速化を図ることができます。

シェル・ソートやコム・ソートの処理速度は、飛び幅 gap の取り方に大きく左右されることは容易に想像できます。例えば、ループ処理の中で gap の値が常に偶数になると、シェル・ソートが高速で処理できる条件の一つである「ソート済みのデータ列に対しては高速にソートできる」という状態を欠いてしまう場合があります。gap の値が常に偶数なら、分割された各群はソートされたデータ列が交互に並んだ状態になり、(ある程度ソートされた傾向にはあるものの) 順位の異なる要素のペアが比較的多くなる可能性が大きくなります。その様子を以下の例で示します。

表 3-1. 偶数の飛び幅による群の分かれ方
飛び幅 4 で分割8 (A)4 (B)6 (C)2 (D)7 (A)3 (B)5 (C)1 (D)
73518462
飛び幅 2 で分割7 (A)3 (B)5 (A)1 (B)8 (A)4 (B)6 (A)2 (B)
51627384
飛び幅 1 で分割5 (A)1 (A)6 (A)2 (A)7 (A)3 (A)8 (A)4 (A)
12345678

上記の中で、数値が実際のデータ、()内はそれぞれの飛び幅で分割したときの各群を表しています。このときの、シェル・ソートとコム・ソートの比較・交換回数を調べると、次のような結果になります。

表 3-2. 各ソートの交換・比較回数
比較回数交換回数
シェル・ソート3020
挿入ソート2020
コム・ソート4120
バブル・ソート2820

この例の場合、群に分けてソートしても交換回数は変わらないだけでなく、比較回数はかえって増加しています。この例ではわざと交換回数が多くなるようにデータ列を作ったので実際にはもう少し交換回数は減ることになると思いますが、gap の値が常に偶数となるとこのような場合もあることを想定することが必要です。

飛び幅の初期値や更新の変更は、今まで作成したサンプル・プログラムの最初のループ処理を以下のようにすれば可能です。

for ( difference_type gap = ( last - first ) / init ; gap > 0 ; gap /= step ) {
  :

init は飛び幅 gap の初期値を決定するときのパラメータで、データ列の長さ / init が飛び幅の初期値となります。stepgap を更新するときに利用するパラメータで、一回のループ処理が完了するごとに gapstep で除算します。従って、先に示したサンプル・プログラムでは init = 2, step = 2 となります。
飛び幅の決め方は他にも考えられるので、全てのソート処理プログラムをその度に変更するのは大変な作業になります。そこで、ソート・ルーチンを関数オブジェクトの形にして、飛び幅を計算した後でその関数オブジェクトを呼び出して処理する方式にします。そのためのプログラムを以下に示します。

/*
  GapSort : 飛び幅を指定したソート用関数オブジェクト
*/
template<class Ran, class Less> class GapSort
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

public:

  /*
    飛び幅指定版ソート関数

    Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
    Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
    difference_type gap : 飛び幅
  */
  virtual void operator()( Ran first, Ran last, Less less, difference_type gap ) const = 0;
};

/*
  GapTest : 飛び幅テスト用ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
  unsigned int init : gap の初期化用パラメータ
  unsigned int step : gap の更新用パラメータ
  const GapSort<Ran,Less>& func : ソート・ルーチン
*/
template<class Ran, class Less> void GapTest( Ran first, Ran last, Less less, unsigned int init, unsigned int step, const GapSort<Ran,Less>& func )
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  if ( init == 0 || step == 0 ) return;

  difference_type gap = ( last - first ) / init;
  if ( gap == 0 ) gap = 1;
  for ( ; ; ) {
    func( first, last, less, gap );
    if ( gap == 1 ) break;
    gap /= step;
    if ( gap == 0 ) gap = 1;
  }

}

GapSort 型の関数オブジェクトは、仮想関数 operator()を持つインターフェースになります。ソート対象となるデータ列の先頭 first と末尾の次の位置 last、要素比較用の関数オブジェクト less の他に、飛び幅を表す gap を引数として受け取り、指定された飛び幅でデータを分割してソート処理を行うようにしておきます。あとは、この関数オブジェクトを gap を更新しながら呼び出し、gap が 1 になったところで処理を完了します。

シェル・ソートに対して GapSort 型の関数オブジェクトに変更したものを以下に示します。

/*
  GapTest_Shell : シェル・ソート テスト・ルーチン用クラス
*/
template<class Ran, class Less> class GapSort_Shell : public GapSort<Ran,Less>
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;
  // 反復子の要素の型
  typedef typename Ran::value_type value_type;

public:

  void operator()( Ran first, Ran last, Less less, difference_type gap ) const
  {
    for ( difference_type i = 0 ; i < gap ; ++i ) {
      for ( Ran e = first + gap + i ; e < last ; e += gap ) {
        value_type v = *e;     // 未ソート列の先頭の要素を取得
        bool inserted = false; // v が挿入されたか
        for ( Ran s = e - gap ; s >= first ; s -= gap ) {
          if ( less( v, *s ) ) {
            *(s + gap) = *s;
          } else {
            *(s + gap) = v;
            inserted = true;
            break;
          }
        }
        // v が未挿入の場合は先頭に要素を代入
        if ( ! inserted ) *( first + i ) = v;
      }
    }
  }
};

元のプログラムから gap を更新するループより内側の部分を抽出しただけなので非常に簡単に変更することができます。他のプログラムに対しても同様な処理で対応することができます。


まずは、各ソートに対して飛び幅 step とその初期値 init の値を変化させたときの処理時間の様子を以下に示します。データは乱数列でそのサイズは 64000 としています。また、各条件での処理は 20 回行い、その平均と標準偏差を表に示しています。標準偏差を見ると分かるように、挿入ソートから派生したシェル・ソートは、交換ソートから派生した他のソート法に比べるとバラツキが非常に大きいことが分かります。これは、シェル・ソートの処理時間がデータの並び方に大きく依存する傾向が他のソート法よりも強いことを示しています。また、処理時間も交換ソートの方がかなり速く、特にノーム・ソートは最速という結果となりました。

表 3-3. 各ソートの処理時間の飛び幅・初期値に対する変化 (乱数)
シェル・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.1380.0840.2040.1290.2480.1320.2680.1600.3710.0750.246
40.1320.1190.2160.1470.2810.1980.3950.2610.3400.1210.273
80.1440.0780.2420.1490.3210.0930.3190.0760.2870.1350.262
160.1910.0980.2730.1460.2330.1120.3710.0880.4220.2340.298
320.2720.1580.3050.1010.3310.2030.3570.1310.4110.0550.335
平均0.175-0.248-0.283-0.342-0.366-0.283
コム・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.0340.0060.0510.0040.0620.0030.1620.0660.1830.0200.099
40.0370.0040.0460.0060.1050.0300.1520.0650.1760.0130.103
80.0430.0230.0670.0400.1090.0120.1320.0060.1800.0090.107
160.0340.0020.0430.0020.0630.0060.1320.0080.2400.0130.102
320.0350.0030.0510.0030.0750.0080.1320.0090.2530.0270.109
平均0.037-0.052-0.083-0.142-0.206-0.104
シェーカー・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.0220.0050.0250.0020.0280.0040.0540.0050.0640.0050.039
40.0210.0020.0230.0020.0340.0070.0410.0030.0670.0030.037
80.0220.0050.0240.0020.0460.0040.0530.0040.0720.0070.044
160.0210.0010.0230.0030.0280.0010.0570.0040.0960.0050.045
320.0220.0020.0250.0030.0330.0020.0550.0040.0940.0060.046
平均0.022-0.024-0.034-0.052-0.079-0.042
奇偶転置ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.0310.0060.0440.0060.0530.0050.1250.0290.1490.0340.081
40.0310.0040.0380.0050.0580.0090.0780.0060.1460.0100.070
80.0310.0040.0440.0050.0940.0120.1280.0400.1570.0350.091
160.0310.0030.0380.0050.0520.0050.1150.0090.1810.0100.084
320.0320.0040.0450.0070.0610.0060.1390.0430.1660.0100.089
平均0.031-0.042-0.064-0.117-0.160-0.083
ノーム・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.0180.0040.0220.0050.0250.0050.0340.0060.0440.0050.029
40.0170.0020.0170.0020.0220.0040.0260.0020.0500.0090.027
80.0180.0030.0190.0040.0400.0050.0350.0050.0390.0030.030
160.0170.0020.0170.0020.0200.0030.0440.0040.0560.0040.031
320.0180.0020.0200.0030.0210.0010.0330.0040.0590.0040.030
平均0.018-0.019-0.026-0.035-0.050-0.029

下図は、表の結果をグラフにしたものです。各ソート法に対し、上側は init の推移を各 step ごとにラインで表したもの、下側は逆に、step の推移を各 init ごとにラインで表したものになります。グラフを見ると、どのソート法に対しても、step が大きくなるに従って処理時間が増える傾向が見られます。step が大きくなると、処理の開始から各群のデータ数は大きくなりますが、逆に gap は小さくなる分ループ回数は減ります。この結果を見る限りは、step は小さい方が処理時間を短くすることができそうです。しかし、init については step のような傾向は見られません。

グラフ 3-1. 各ソートの飛び幅・初期値に対する処理時間の推移 (乱数)
シェル・ソートコム・ソート
シェル・ソート コム・ソート
シェーカー・ソート奇偶転置ソート
シェーカー・ソート 奇偶転置ソート
ノーム・ソート
ノーム・ソート

乱数列ではなく逆ソート済みのデータに対して処理をすると、シェル・ソートは処理時間が急激に長くなりますが、そのバラツキは比較的小さくなります。また、交換ソートから派生したソート法の場合は逆に処理時間が短くなります。前回の動作テストでも、ノーム・ソート以外の交換ソートは逆ソート済みデータに対する処理時間が乱数列の半分程度になっていましたが、今回はノーム・ソートも含め、一桁分短縮するという結果になっています。下表は、逆ソート済みのデータを使う以外は乱数列の時と全く同じ条件で処理を行った結果です。

表 3-4. 各ソートの処理時間の飛び幅・初期値に対する変化 (逆ソート)
シェル・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init21.4640.1231.3630.0541.3770.0561.4690.1211.2910.0961.393
41.3480.0201.5400.0211.5010.0341.4550.0231.3840.0161.446
81.3330.0191.2770.0101.3140.0201.2270.0201.3590.0161.302
161.3510.0171.5470.0171.3260.0561.3640.0221.4390.0101.405
321.3320.0171.2680.0131.4770.0151.3370.0141.1970.0111.322
平均1.365-1.399-1.399-1.370-1.334-1.374
コム・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.00440.00110.00480.00220.00590.00100.00860.00190.01240.00160.0072
40.00450.00190.00370.00030.00680.00360.00880.00130.01180.00180.0071
80.00380.00030.00410.00070.00560.00110.00940.00150.01020.00120.0066
160.00420.00030.00490.00130.00620.00120.00760.00070.01120.00170.0068
320.00600.00170.00530.00080.00690.00170.00850.00220.01290.00120.0079
平均0.0046-0.0046-0.0063-0.0086-0.0117-0.0071
シェーカー・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.00410.00150.00430.00170.00600.00230.00810.00200.01300.00410.0071
40.00380.00160.00450.00210.00590.00170.01270.00310.02100.00310.0096
80.00630.00290.00430.00200.00600.00220.00940.00220.00990.00160.0072
160.00490.00170.00450.00120.00600.00190.00800.00230.01150.00540.0070
320.00560.00130.00550.00170.00620.00140.00790.00210.01300.00320.0076
平均0.0050-0.0046-0.0060-0.0092-0.0137-0.0077
奇偶転置ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.00520.00110.00460.00190.00490.00100.00540.00130.01120.00240.0063
40.00490.00170.00450.00120.00600.00190.00800.00230.01150.00540.0070
80.01360.00590.00770.00270.00490.00150.00730.00170.00770.00200.0082
160.00600.00160.00520.00230.00550.00140.00630.00110.00740.00150.0061
320.00600.00080.00510.00060.00580.00110.00610.00170.01160.00170.0069
平均0.0071-0.0053-0.0063-0.0075-0.0117-0.0076
ノーム・ソート
step2481632平均
平均標準偏差平均標準偏差平均標準偏差平均標準偏差平均標準偏差
init20.00400.00050.00410.00100.00710.00220.00970.00140.01230.00100.0075
40.00380.00050.00340.00040.00630.00060.00930.00120.01140.00210.0068
80.00470.00190.00420.00040.00630.00050.01020.00150.01140.00110.0074
160.00600.00080.00620.00140.00800.00170.01050.00210.01370.00290.0089
320.00810.00170.00790.00160.00950.00130.01170.00190.01630.00230.0107
平均0.0053-0.0052-0.0075-0.0103-0.0130-0.0083

グラフにすると、step と処理時間の相関はコム・ソート、シェーカー・ソート、ノーム・ソートで見られ、どの場合もやはり step が大きくなるほど処理時間は長くなる傾向にあります。おもしろいことに、ノーム・ソートでは init に対して処理時間との相関が見られました。シェル・ソートと奇偶転置ソートでは step に対する処理時間の増加は確認できませんでした。通常のデータは乱数列になるため、どのソート法に対しても initstep は小さい方が優位であると考えられます。

グラフ 3-2. 各ソートの飛び幅・初期値に対する処理時間の推移 (逆ソート)
シェル・ソートコム・ソート
シェル・ソート コム・ソート
シェーカー・ソート奇偶転置ソート
シェーカー・ソート 奇偶転置ソート
ノーム・ソート
ノーム・ソート

今までの結果を見る限りでは、initstep は 2 のままにしておいた方が処理時間は短縮できます。そこで今度は、initstep を 1 と 2 の間の値にした場合の処理時間を調べてみます。まず、テスト用の関数を次のように変更します。

/*
  GapTest : 飛び幅テスト用ルーチン(stepを任意の浮動小数点数で指定する)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
  double step : gap の更新用パラメータ
  const GapSort<Ran,Less>& func : ソート・ルーチン
*/
template<class Ran, class Less> void GapTest( Ran first, Ran last, Less less, double step, const GapSort<Ran,Less>& func )
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  if ( step <= 1.0 ) return;

  difference_type gap = (double)( last - first ) / step;
  if ( gap == 0 ) gap = 1;
  for ( ; ; ) {
    func( first, last, less, gap );
    if ( gap == 1 ) break;
    gap = (double)gap / step;
    if ( gap == 0 ) gap = 1;
  }
}

飛び幅の初期設定も更新時も同じ値 step を使います。step が 1 以下になると、gap はいつまで経っても収束しない ( step が 1 より小さければ逆に大きくなる ) ので、あらかじめ step が 1 より大きいかどうかをチェックします。後の処理は整数を使った先の方法とほとんど変わりません。

このテスト用ルーチンを使って step を 1.1 から 2.0 まで 0.1 刻みで変化させたときの処理時間の様子を以下に示します。今回も、テスト回数を 20 回、データは乱数列で大きさを 64000 としています。

表 3-5. 飛び幅が 1.1 から 2.0 の場合の各ソートの処理時間 (乱数)
stepシェル・ソートコム・ソートシェーカー・ソート奇偶転置ソートノーム・ソート
1.1平均0.0880.0420.0380.0440.031
標準偏差0.0260.0030.0040.0030.005
1.2平均0.0900.0300.0270.0320.022
標準偏差0.0330.0050.0040.0060.004
1.3平均0.1080.0270.0240.0260.022
標準偏差0.0720.0040.0050.0050.007
1.4平均0.0790.0250.0230.0240.020
標準偏差0.0390.0020.0040.0040.005
1.5平均0.1020.0250.0220.0240.020
標準偏差0.0670.0050.0050.0050.006
1.6平均0.1060.0240.0220.0240.018
標準偏差0.0880.0040.0050.0040.005
1.7平均0.1440.0230.0220.0250.019
標準偏差0.0940.0030.0050.0050.005
1.8平均0.2110.0260.0230.0240.020
標準偏差0.1710.0030.0050.0050.006
1.9平均0.1400.0250.0230.0240.019
標準偏差0.1040.0040.0050.0040.005
2.0平均0.2280.0330.0280.0300.024
標準偏差0.1720.0030.0030.0050.004
平均0.1300.0280.0250.0280.021

上の表をグラフにしたのが下図になります。シェル・ソートとそれ以外では、傾向が全く異なるため別のグラフにしています。

グラフ 3-3. 各ソートの飛び幅・初期値に対する処理時間の推移 ( step < 2 )
シェル・ソート
シェル・ソート
その他のソート
その他のソート

シェル・ソートは相変わらずバラツキが大きく、他のソート方法と比べてもかなり処理時間は長い傾向にあります。グラフを見ると、step は小さい方が有利で 1.1 から 1.6 までの範囲が最適値と考えられます。交換ソート群は、あまり step が小さすぎると処理時間が大きくなる傾向が見られるので、1.4 から 1.7 あたりまでが最適値と判断できます。


データ数を 64000 にした場合、init = 2, step = 2 の場合の gap の変化は次のようになります。

64000 → 32000 → 16000 → 8000 → 4000 → 2000 → 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1

最も外側の ( gap を固定したときの ) 処理の回数は 15 回、その中で gap が偶数となるのは 9 回なので、その比率は 0.6 です。データ列の大きさを 65536 としたとき、gap は常に偶数となります。また、一つ減らして 65535 にすると、今度は常に奇数になります。その様子を以下に示します。

65536 → 32768 → 16384 → 8192 → 4096 → 2048 → 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

65535 → 32767 → 16383 → 8191 → 4095 → 2047 → 1023 → 511 → 255 → 127 → 63 → 31 → 15 → 7 → 3 → 1

両者での処理速度の差を調べた結果は次のようになります。いずれも、stepinit は 2 とし、乱数列に対して 20 回のテストを行ったときの平均と標準偏差を示しています。

表 3-6. gap が常に奇数・偶数の場合のシェル・ソート処理時間の比較
ソート法常に偶数(65536)常に奇数(65535)処理時間の比率
 平均 標準偏差 平均 標準偏差
シェル・ソート0.390.130.150.120.38
コム・ソート0.0720.0070.0280.0050.39
シェーカー・ソート0.0530.0060.0210.0040.40
奇偶転置ソート0.0680.0060.0260.0060.38
ノーム・ソート0.0420.0080.0170.0050.40

結果をみると、どのソート法に対しても、gap が常に奇数になる方が処理時間が倍以上短くなります。よって、gap が奇数になるように操作をすることで、処理時間を短縮させることができることがわかります。強制的に奇数にするには、関数オブジェクト GapSort を呼び出す前に、gap が奇数になるよう以下のコードを追加するだけで実現できます。

if ( ( gap & 1 ) == 0 ) --gap;

強制的に奇数とした場合の処理時間を、上記結果と並べたものを以下に示します。強制的に奇数にした場合の処理は、データの大きさを「常に偶数」と同じ 65536 にしています。

表 3-7. gap が常に奇数になるようにした場合のシェル・ソート処理時間の比較
ソート法常に偶数(65536)常に奇数(65535)強制的に奇数(65536)
 平均 標準偏差 平均 標準偏差 平均 標準偏差
シェル・ソート0.390.130.150.120.120.08
コム・ソート0.0720.0070.0280.0050.0290.007
シェーカー・ソート0.0530.0060.0210.0040.0210.005
奇偶転置ソート0.0680.0060.0260.0060.0260.006
ノーム・ソート0.0420.0080.0170.0050.0180.005

gap を強制的に奇数にすることによって、処理時間が改善されることが上記結果から示されます。


最終的には、以下の条件を最適値としました。

  1. init = step = 1.4 とする。
  2. 更新した gap が偶数だった場合、1 を減じて強制的に奇数とする。

step が小さいということは、各群のデータ数は緩やかに増えていくということになります。その分、群ごとのソートを繰り返す回数は増えますが、群内のデータ数の上昇を抑えたほうが処理時間は早くなるという結果となります。また、gap を奇数にすることで、前回同じ群にあったデータが再び群としてまとめられる量は減るので、結果としてデータがうまくスクランブルされる形になります。このような飛び幅の制御を行うためのサンプル・プログラムを以下に示します。

const double GAP_STEP = 1.4; // step の値

/*
  GapCtrl : 飛び幅制御用ルーチン

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
  const GapSort<Ran,Less>& func : ソート・ルーチン
*/
template<class Ran, class Less> void GapCtrl( Ran first, Ran last, Less less, const GapSort<Ran,Less>& func )
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  difference_type gap = last - first;
  if ( gap <= 1 ) return;

  do {
    gap = (double)gap / GAP_STEP;
    func( first, last, less, gap );
  } while ( gap > 1 );
}

4) 動作テスト

上記で決めた飛び幅制御用ルーチンを使って、各ソート法での処理時間を計測した結果を以下に示します。いずれの場合もデータは乱数列で、テストは 20 回行い、その平均と標準偏差を出力しています。

表 4-1. データ数に対する処理時間の推移
データ数8000160003200064000128000
 平均 標準偏差 平均 標準偏差 平均 標準偏差 平均 標準偏差 平均 標準偏差
シェル・ソート0.00530.00380.0120.0090.0250.0130.130.140.350.42
コム・ソート0.00170.00090.00410.00160.00810.00170.0180.0020.0400.003
シェーカー・ソート0.00260.00260.00380.00210.00690.00080.0160.0020.0350.003
奇偶転置ソート0.00240.00220.00410.00160.00820.00130.0170.0020.0470.006
ノーム・ソート0.00190.00200.00320.00190.00580.00120.0130.0030.0290.004

下図は、表の結果をグラフに表したものです。前回紹介した「遅い」ソート・ルーチンでは処理時間がデータ量の二乗に比例していたのに対して、今回はそれよりも増加が緩やかになっています。

グラフ 4-1. 各ソートのデータ数に対する処理時間の推移
シェル・ソート
シェル・ソート
その他のソート
その他のソート

シェル・ソートに対して近似曲線を y = axb の形で求めると、データ量 N に対して処理時間は N1.6 に比例して増加しています。よって、二乗に比例していた前回のソート・ルーチンと比べると増加量は小さくなっていることになります。交換ソートについてはさらに増加量は小さく、ほぼ N に比例していると見なせるくらいです。

参考文献(Wikipedia)では、シェル・ソートの場合、gap として漸化式 GN+1 = 3GN + 1 の形、つまり 1, 4, 13, 40, 121 ... という整数列を利用すると、データ量 N に対して N1.25 にほぼ比例する処理時間になるとされていました。そこで、gap に対してこの整数列を利用して処理させてみたところ逆に遅くなってしまい、データ量に対しては N1.8 にほぼ比例するという結果となりました。step に対する処理時間の推移から速くはならないことは予想していたものの、もしかしたらデータ量に対する増加率が緩やかになるかもしれないと期待していただけに少し残念な結果となってしまいました。以下に、利用したサンプル・プログラムと処理時間の計測結果を示しておきます。

/*
  GapCtrl_Shell : 飛び幅制御用ルーチン(シェル・ソート用)

  Ran first, last : ランダム・アクセス反復子(ソート開始と終了)
  Less less : 要素比較用関数オブジェクト(boolを返す二項叙述関数)
  const GapSort<Ran,Less>& func : ソート・ルーチン
*/
template<class Ran, class Less> void GapCtrl_Shell( Ran first, Ran last, Less less, const GapSort<Ran,Less>& func )
{
  // 反復子の位置の差
  typedef typename Ran::difference_type difference_type;

  difference_type gap = 1;
  while ( gap < last - first )
    gap = gap * 3 + 1;
  if ( gap == 1 ) return;

  do {
    gap = ( gap - 1 ) / 3;
    func( first, last, less, gap );
  } while ( gap > 1 );
}
 
表 4-2. データ数に対する処理時間の推移 (シェル・ソート)
データ数8000160003200064000128000
 平均 標準偏差 平均 標準偏差 平均 標準偏差 平均 標準偏差 平均 標準偏差
step = 1.40.00530.00380.0120.0090.0250.0130.130.140.350.42
GN+1 = 3GN + 10.00490.00430.0130.0100.0450.0420.180.150.670.70

同じく参考文献(Wikipedia)によれば、コム・ソートの場合の処理時間はデータ数 N に対して N log N に比例するそうです。このとき、データ量が二倍になっても処理時間は二倍をわずかに超える程度にしか増えないと考えてもよく、よほど大きなデータ量にならない限りはほぼ線形に見えることは、先程の結果からも理解できると思います。しかし、gap を決める step の値は、1.4 ではなく 1.3 としています。今回は数値の比較・交換処理でテストを行っており、この条件を変化させれば step の最適値も変わる可能性はあります。


<参考文献>
  1. 「X68000マシン語プログラミング <入門編>」 村田敏幸 著 (ソフトバンク)
  2. Wikipedia

[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system