第８話 グループ分け
郵政省が民営化される前の話ですから、
今から１０数年前の頃でしょうか。
私の記憶によるものですから、
確かな話しではありませんが、
郵便物をグループに分けてから分類するようにしたら、
仕分けの速度がアップして、
郵便物を早く配達できるようになった、
と郵政省が発表していました。
全部をまとめて分類するのではなく、
機械的にいくつかのグループに分けてから、
届け先を仕分けすると早くなったというわけです。
このアイデアを並び換えに採用できないでしょうか。
データを複数のグループに分け、
その中で並び換えをしてから、
全体を並び換えたら、
並び換えのスピードアップが図れないでしょうか。
6 8 3 4 8 2
を例にして思考実験してみましょう。
以下、青は比較、薄茶は交換、緑は何もしないを表し、
丸数字はステップ数を示します。
緑は何もしないを表していますので、ステップ数としてはカウントしません。
6 8 3 4 8 2
を
6 8 3
と
4 8 2
のグループに分けてから並び換えをします。
前半グループ 6 8 3 の並び換え
1巡目
6 8 3 ①
6 8 3
6 8 3 ②
6 3 8 ③
２巡目
6 3 8 ④
3 6 8 ⑤
3 6 8 ⑥
3 6 8
３巡目
3 6 8 ⑦
3 6 8
3 6 8 ⑧
3 6 8
交換が１回も発生せず、前半グループの並び換え成功
後半グループ 4 8 2 の並び換え
1巡目
4 8 2 ①
4 8 2
4 8 2 ②
4 2 8 ③
２巡目
4 2 8 ④
2 4 8 ⑤
2 4 8 ⑥
2 4 8
３巡目
2 4 8 ⑦
2 4 8
2 4 8 ⑧
2 4 8
交換が発生せずに、後半グループの並び換えに成功。
この２つはそれぞれのスレッドに並行処理させますので、
グループ別のステップ数は多い方を数えれば良いわけです。、
今の事例では両方とも同じ８ですから、８です。
前半と後半を合体した 3 6 8 2 4 8 の並び換え
１巡目
3 6 8 2 4 8 ⑨
3 6 8 2 4 8
3 6 8 2 4 8 ⑩
3 6 8 2 4 8
3 6 8 2 4 8 ⑪
3 6 2 8 4 8 ⑫
3 6 2 8 4 8 ⑬
3 6 2 4 8 8 ⑭
3 6 2 4 8 8
２巡目
3 6 2 4 8 8 ⑮
3 6 2 4 8 8
3 6 2 4 8 8 ⑯
3 2 6 4 8 8 ⑰
3 2 6 4 8 8 ⑱
3 2 4 6 8 8 ⑲
3 2 4 6 8 8 ⑳
3 2 4 6 8 8
3 2 4 6 8 8 繪�
3 2 4 6 8 8
３巡目
3 2 4 6 8 8 繪�
2 3 4 6 8 8 繪�
2 3 4 6 8 8 繪�
2 3 4 6 8 8 繪�
2 3 4 6 8 8
2 3 4 6 8 8 繪�
2 3 4 6 8 8
2 3 4 6 8 8 繪�
2 3 4 6 8 8
４巡目
2 3 4 6 8 8 繪�
2 3 4 6 8 8
2 3 4 6 8 8 繪�
2 3 4 6 8 8
2 3 4 6 8 8 繪�
2 3 4 6 8 8
2 3 4 6 8 8 繪�
2 3 4 6 8 8
2 3 4 6 8 8 繪�
2 3 4 6 8 8
交換が発生せず、４巡目で終了
全体のステップ数は３２回でした。
グループ分けしない場合のステップ数は果たしてどうでしょうか。