5
は、私は/デモ異なるソートアルゴリズムを評価するために、いくつかのJavaクラスを書きました。しかし、私はデモクラスを実行すると混乱してしまいました。あなたは私に説明を与えることができることを願っています。 （この質問は宿題ではありません。）同じコード、同じ入力は、時々高速で実行し、時には遅く、なぜ？
まず、私はこの質問に関連するいくつかのコードをリストします。
AbstractDemo
public abstract class AbstractDemo {
protected final int BIG_ARRAY_SIZE = 20000;
protected final int SMALL_ARRAY_SIZE = 14;
protected Stopwatch stopwatch = new Stopwatch();
public final void doDemo() {
prepareDemo();
specificDemo();
}
protected abstract void prepareDemo();
protected abstract void specificDemo();
protected final void printInfo(final String text) {
System.out.println(text);
}
}
SortingDemo
public class SortingDemo extends AbstractDemo {
private static final String FMT = "%-10s| %-21s| %7s ms.";
private static final String SPL = AlgUtil.lineSeparator('-', 45);
private static final String SPLT = AlgUtil.lineSeparator('=', 45);
private int[] data;
private final List<Sorting> demoList = new LinkedList<Sorting>();
@Override
protected void specificDemo() {
int[] testData;
//*** this comment is interesting!!! for (int x = 1; x < 6; x++) {
printInfo(String.format("Sorting %7s elements", data.length));
printInfo(SPLT);
for (final Sorting sort : demoList) {
// here I made a copy of the original Array, avoid to sort an already sorted array.
testData = new int[data.length];
System.arraycopy(data, 0, testData, 0, data.length);
stopwatch.start();
// sort
sort.sort(testData);
stopwatch.stop();
printInfo(String.format(FMT, sort.getBigO(), sort.getClass().getSimpleName(), stopwatch.read()));
printInfo(SPL);
testData = null;
stopwatch.reset();
}
//}
}
@Override
protected void prepareDemo() {
data = AlgUtil.getRandomIntArray(BIG_ARRAY_SIZE, BIG_ARRAY_SIZE * 5, false);
demoList.add(new InsertionSort());
demoList.add(new SelectionSort());
demoList.add(new BubbleSort());
demoList.add(new MergeSort()); //here is interesting too
demoList.add(new OptimizedMergeSort());
}
public static void main(final String[] args) {
final AbstractDemo sortingDemo = new SortingDemo();
sortingDemo.doDemo();
}
}
ストップウォッチ
public class Stopwatch {
private boolean running;
private long startTime;
private long elapsedMillisec;
public void start() {
if (!running) {
this.startTime = System.currentTimeMillis();
running = true;
} else {
throw new IllegalStateException("the stopwatch is already running");
}
}
public void stop() {
if (running) {
elapsedMillisec = System.currentTimeMillis() - startTime;
running = false;
} else {
throw new IllegalStateException("the stopwatch is not running");
}
}
public void reset() {
elapsedMillisec = 0;
}
public long read() {
if (running) {
elapsedMillisec = System.currentTimeMillis() - startTime;
}
return this.elapsedMillisec;
}
}
方法は、あなたが見ることができるランダム配列
public static int[] getRandomIntArray(final int len, final int max, boolean allowNegative) {
final int[] intArray = new int[len];
final Random rand = new Random();
rand.setSeed(20100102);
if (!allowNegative) {
if (max <= 0) {
throw new IllegalArgumentException("max must be possitive if allowNegative false");
}
for (int i = 0; i < intArray.length; i++) {
intArray[i] = rand.nextInt(max);
}
} else {
int n;
int i = 0;
while (i < len) {
n = rand.nextInt();
if (n < max) {
intArray[i] = n;
i++;
}
}
}
return intArray;
}
を生成するために、私は20000個の要素を持つint配列を生成します。私はgetRandomIntArrayメソッドで固定されたシードを持っているので、私はいつも同じ配列を呼び出しています。
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 101 ms.
---------------------------------------------
O(n^2) | SelectionSort | 667 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1320 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 39 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 11 ms.
---------------------------------------------
がOKになります。クラスSortingDemoは、私はこのクラスを実行する場合、私は出力を得た、主な方法があります。今私は混乱させた何かが来る。私はSortingDemoにdemoList.add（）シーケンスを変更した場合は、言う：
demoList.add(new InsertionSort());
demoList.add(new SelectionSort());
demoList.add(new BubbleSort());
// OptimizedMergeSort before Mergesort
demoList.add(new OptimizedMergeSort());
demoList.add(new MergeSort());
は、私が得た：
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 103 ms.
---------------------------------------------
O(n^2) | SelectionSort | 676 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1313 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 41 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 14 ms.
---------------------------------------------
出力は最初の実行と異なっている理由は？ OptimizedMergeSortは...通常のマージソートよりも長い
を取って、私はSortingDemoでfor (int x=1; x<6; x++)行のコメントを解除した場合、（同じ配列で5回テストを実行します）私が得た：他のソーティングのために
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 101 ms.
---------------------------------------------
O(n^2) | SelectionSort | 668 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1311 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 37 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 10 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 94 ms.
---------------------------------------------
O(n^2) | SelectionSort | 665 ms.
---------------------------------------------
O(n^2) | BubbleSort | 1308 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 5 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 7 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 116 ms.
---------------------------------------------
O(n^2) | SelectionSort | 318 ms.
---------------------------------------------
O(n^2) | BubbleSort | 969 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 5 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 10 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 116 ms.
---------------------------------------------
O(n^2) | SelectionSort | 319 ms.
---------------------------------------------
O(n^2) | BubbleSort | 964 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 5 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 5 ms.
---------------------------------------------
Sorting 20000 elements
=============================================
O(n^2) | InsertionSort | 116 ms.
---------------------------------------------
O(n^2) | SelectionSort | 320 ms.
---------------------------------------------
O(n^2) | BubbleSort | 963 ms.
---------------------------------------------
O(?) | OptimizedMergeSort | 4 ms.
---------------------------------------------
O(nlog(n))| MergeSort | 6 ms.
---------------------------------------------
、結果のルックスを合理的。 mergeSortの場合、最初の実行には後で行うよりもずっと長い時間がかかったのはなぜですか？ 37ms：OptimizedMergeSortの場合は4ms。
私はいつか同じメソッド呼び出しは、いつか短い時間に時間がかかる理由を最適化/マージソートの実装が間違っていた場合でも、出力は、同じに保つべきであるかと思いますは情報としては、これらすべての*ソートクラスは、スーパー抽象クラスのソートを拡張します。それは抽象メソッドを持っていますvoid sort(int[] data)
MergeSortはmergeSortingメソッドとmerge（）メソッドを持っています。 OptimizedMergeSortはMergeSortを拡張し、mergeSorting()メソッドをオーバーライドします（配列のサイズが< = 7の場合、insertionSortを実行するので）MergeSortクラスのmerge()メソッドを再利用します。この長いテキストとコードを通じて読み取るための
感謝。皆さんから私に説明をしていただければ幸いです。
すべてのテストは、Eclipseのlinuxで行われました。
MergeSortとOptimizedMergeSortの共有コードはありますか？もしそうなら、あなたはjitコンパイルの影響を見ているでしょう。 Javaでの正確なマイクロベンチマークの作成は非常に難しく（ジットのため）、対象に多くの記事があります。コメントのために – jtahlborn
@minitech thx私はランダムが結果に影響しないと思う。 prepareDemoは一度だけ呼び出されたためです。どんな種類のランダムであっても、それはすべての種類に対して同じ配列です。 – Kent
@jtahlbornはい、私が質問に書いたように、OptimzedMSはMSのサブクラスであり、（MSクラスで保護された）マージメソッドを共有しています。ジットヒントのおかげで、私はそれを検索して読む – Kent