Javaで破壊的クイックソート
後輩のレポートを僕が解いてしまうと勉強にならないと思って我慢していましたが、レポート内容はクイックソートではなくてそれを利用してSuffixArrayを作ることらしいです。帰りの電車で作ったのでとりあえず貼っておきます。皮の部分は「QuickSort祭り(一人)」を参照。
後輩のレポートにはin placeでvec[i]をvec[pivotPos]の手前に持ってくるためにpivotPos～i-1のすべてを一つ右にずらしていたのですけど、単に「iをバックアップし、pivotPos+1をiに書き、pivotPosをpivotPos+1に書いてpivotPosにバックアップしたiを戻す」でもいいような気がします。
むう、10000件のソートで、非破壊的ソートが32ミリ秒なのに、この破壊的ソートは3515ミリ秒かかって100倍遅い。Vectorである必要性がないので最初に配列に変換してみたけども、それでも351ミリ秒なので10倍遅い。上の段落で書いた高速化を入れて47ミリ秒なので1.5倍遅い。どういうことかな…。
非破壊的ソートではNlogNのメモリを消費して1回の分割でN回読んでN回書いているけど、破壊的ソートではNのメモリを消費して、約1/2の確率で起きる値の移動で3回ずつ読み書きするのでだいたい1.5N回の読み書きを行うと。ソートの対象が十分に小さければ、メモリの確保が大した問題にならないので破壊的ソートに約1.5倍の時間がかかるというわけですかな。で、メモリの確保に苦労するような巨大なリストをソートする場合には破壊的ソートの方が早いかというと…うーん、ひとかたまりの配列として保持しづらいし、何度も同じ所を読むからキャッシュに期待できないし…。
いや、待てよ、上の計算は正しくないか。非破壊的ソートの方はVectorを使っているから、Vectorを使った破壊的ソートと使わない破壊的ソートの比程度のオーバーヘッドがあるはず。だから非破壊的ソートと破壊的ソートの比は1.5倍どころじゃない。
private static Vectorsort(Vector vec) { partialSort(vec, 0, vec.size()); return vec; } private static void partialSort(Vector vec, int start, int end){ if(end - start < 2){ return; } Integer pivot = vec.get(start); int pivotPos = start; for(int i = start + 1; i < end; i++){ Integer v = vec.get(i); if(v < pivot){ // vをpivotの前に移動 for(int j = i; j > pivotPos; j--){ vec.set(j, vec.get(j - 1)); } vec.set(pivotPos, v); pivotPos++; } } partialSort(vec, start, pivotPos); partialSort(vec, pivotPos + 1, end); }
