就職活動中の1年弱前のどこかで、イノポリスでコースを修了した後、雇用主の1人がそのような割り当てを与えました。
1億の数字があり、それぞれ0〜10億です。
昇順でソートする必要があります。
最初は、プログラムが誤ってそれらを埋めてから、ソートします。
キャッチは、同じタスクが私たちのコースの他の卒業生に与えられたことでした。 タスクは、Skypeインタビューの後、1日間家に与えられました。
クラス11のレベルでのソートの実装はここでは機能しないことがすぐに明らかになりました。
単純なものから複雑なものに移行し、最初に通常のクイックソートを実装しました
/** * */ public class QuickSort extends AbstractQuickSort { public void sort(int[] a) { sort(a, 0, a.length - 1); } private void sort(int[] a, int lo, int hi) { if(hi <= lo) return; // int j = partition(a, lo, hi); // / sort(a, lo, j - 1); sort(a, j + 1, hi); } }
次に、ForkJoinPoolを使用してアルゴリズムを並列化します
/** * fork join */ public class ParallelQuickSort extends AbstractQuickSort { public void sort(int[] a) { ForkJoinPool.commonPool().invoke(new SortAction(a, 0, a.length - 1)); } /** * ForkJoinTask */ private class SortAction extends RecursiveAction{ private final int bubbleBlock = 16; int[] a; int lo; int hi; SortAction(int[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; } @Override protected void compute() { if(hi <= lo) return; if ((hi - lo) > bubbleBlock) { // int j = partition(a, lo, hi); // / invokeAll(new SortAction(a, lo, j - 1), new SortAction(a, j + 1, hi)); }else{ // bubbleSort(a, lo, hi + 1); } } /** * , */ private void bubbleSort(int[] a, int lo, int hi){ for (int i = lo; i < hi; i++) { for (int j = i; j < hi; j++) { if (a[i] > a[j]) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } } } }
ソリューションの品質を確認するために、取得したアルゴリズムとStream APIの並べ替えを比較します。 秒単位の時間が表示されます。 i7-7700 3.6GHz、16GB、4コア
| アルゴリズム | 私のクイックソート | ストリームAPI |
|---|---|---|
| 普通 | 11.64 | 10,2 |
| 平行 | 5.02 | 3.9 |
Stream APIのネイティブ実装と比較して、私のソリューションの生産性が低いことは驚くことではありません。 主なことは、順序が同じであるということです。タスクを完了し、並列化後に速度が向上しました。
インタビュアーは肯定的なフィードバックを与えました。 しかし、その会社で就職したことはありませんでした。別の会社で傍受され、同時に面接を受けたからです。
1） gitへのリンク
2） 彼が基本的なアルゴリズムを取り入れた本
アップデート1
この記事のメンバーは、クイックソート自体ではなく、主にForkJoinPoolの実装について話しています。
更新2
カウントによる並べ替えのファンの場合、4GBメモリヒープの割り当て時間は約13秒です。 これは、ソート自体を考慮に入れていない場合でも、提示されたオプションのいずれよりも悪いです。