Quick Sort

第 14 章でみたように, quick sort は, アルゴリズムのお しまいの部分で, 分割された二つの配列を引数として自分自身を呼び出すとい う再帰的アルゴリズムとなっている. この部分で, 自分で計算する代わりに, server を起動して計算を任せる, という(とても安直な)分散計算を試してみ よう.

注意 : ちょっと考えれば, 「親」は, 配列を二つに分けることしかしておら ず, 肝腎の整列は「子」に全部任せて待つだけということが分かる. 通信はそ れなりにコストがかかるし, server の立ち上げはとてもコストがかかるので, こんなことをしても効率向上は望めないが, こんなことが簡単に実行できると いう例として紹介している.

#define LevelMax 2
Proc1 = -1$
Proc2 = -1$
def quickSort(A,P,Q,Level) {
   extern Proc1, Proc2;
   if (Q-P < 1) return A;
   print("Level=",0); print(Level);
   Mp = idiv(P+Q,2);
   M = A[Mp];
   B = P; E = Q;
   while (1) {
     while (A[B] < M) B++;
     while (A[E] > M && B <= E) E--;
     if (B >= E) break;
     else {
       Tmp = A[B];
       A[B] = A[E];
       A[E] = Tmp;
       E--;
     }
  }
  if (E < P) E = P;
/* -------------------------- */
  if (Level < LevelMax) {
    if (Proc1 == -1) {
      Proc1 = ox_launch();
    }
    if (Proc2 == -1) {
      Proc2 = ox_launch();
    }
    ox_rpc(Proc1,"quickSort",A,P,E,Level+1);
    ox_rpc(Proc2,"quickSort",A,E+1,Q,Level+1);
    if (E-P < Q-E) {
       A1 = ox_pop_local(Proc1);
       A2 = ox_pop_local(Proc2);
    }else{
       A2 = ox_pop_local(Proc2);
       A1 = ox_pop_local(Proc1);
    }
    for (I=P; I<=E; I++) {
       A[I] = A1[I];
    }
    for (I=E+1; I<=Q; I++) {
       A[I] = A2[I];
    }
    return(A);
/* -------------------------- */
  }else{
    quickSort(A,P,E,Level+1);
    quickSort(A,E+1,Q,Level+1);
    return(A);
  }
}
end$

このプログラムは第 14 章のものとほとんど同じで, 異なる のは /* -------------------------- */ ではさまれた部分のみである. このプログラムでは, ox_launch() により動的に ox_asir を 起動しているので, 起動時にこの関数が定義されるように, .asirrc に 書いておく必要がある. たとえば, この関数が含まれるファイルを /home/noro/asir/d_qsort とすれば, .asirrc に

load("/home/noro/asir/d_qsort")$

を追加しておけばよい. この関数では, 際限なく server が生成されるのを防 ぐために, 再帰の段数が LevelMax という定数を越えたら自プロセス内で再帰 するようにしてある. また, 一旦 server が生成されたらその識別番号を覚えて おき, 無駄に server を生成しないようにもしてある. (いくら効率無視でも このような工夫は必要. 特に段数の制限は重要. さもないと計算機自体がストップ してしまうこともあり得る. )