入れ子のwhileループを変更する必要がありますか？クイックソートは、これらの機能によって定義されます。削除が正常に機能しません。
最適化に関しては、デフォルトではprimitives vs objectsが異なる傾向があることを知っておく必要があります。例えば。 primitives on stack/heapスタックを小さくする&ヒープストアオブジェクトはrefs able to be on stackとなります。
それでは、いくつかのものをテストしてみましょう
- プリミティブクイックソートクイックソート（同じコード上記のように、しかし、Integerクラスで）
- あなたの元には
- あなたの元のコードを掲載整数（from here）
- 投稿されたコード（複数の編集あり）
ここで使用したコード全体です。
import java.util.Random;
public class App {
public static final int ARR_SIZE = 1000;
public static final int TEST_ITERS = 10000;
public static Random RANDOM = new Random();
public static void main(String[] args) {
int[] a = new int[ARR_SIZE];
Integer[] b = new Integer[ARR_SIZE];
Integer[] c = new Integer[ARR_SIZE];
Integer[] d = new Integer[ARR_SIZE];
long sum = 0, start = 0, end = 0;
for (int i = 0; i < TEST_ITERS; ++i) {
for (int j = 0; j < ARR_SIZE; ++j)
a[j] = RANDOM.nextInt();
start = System.nanoTime();
quickSort(a, 0, a.length - 1);
end = System.nanoTime();
sum += (end - start);
}
System.out.println((sum/TEST_ITERS) + " nano, qs avg - 'int'");
sum = 0;
for (int i = 0; i < TEST_ITERS; ++i) {
for (int j = 0; j < ARR_SIZE; ++j)
b[j] = RANDOM.nextInt();
start = System.nanoTime();
quickSort(b, 0, b.length - 1);
end = System.nanoTime();
sum += (end - start);
}
System.out.println((sum/TEST_ITERS) + " nano, qs avg - 'Integer'");
sum = 0;
for (int i = 0; i < TEST_ITERS; ++i) {
for (int j = 0; j < ARR_SIZE; ++j)
c[j] = RANDOM.nextInt();
start = System.nanoTime();
quicksort(c, 0, c.length - 1);
end = System.nanoTime();
sum += (end - start);
}
System.out.println((sum/TEST_ITERS) + " nano, qs avg - 'Comparable' (SO user code)");
sum = 0;
for (int i = 0; i < TEST_ITERS; ++i) {
for (int j = 0; j < ARR_SIZE; ++j)
d[j] = RANDOM.nextInt();
start = System.nanoTime();
qs_quicksort(d, 0, d.length - 1);
end = System.nanoTime();
sum += (end - start);
}
System.out.println((sum/TEST_ITERS) + " nano, qs avg - 'Comparable' (SO user code - edit)");
for (int i = 0; i < ARR_SIZE; ++i) {
final int n = RANDOM.nextInt();
a[i] = n;
b[i] = n;
c[i] = n;
d[i] = n;
}
quickSort(a, 0, a.length - 1);
Integer[] aConv = new Integer[ARR_SIZE];
for (int i = 0; i < ARR_SIZE; ++i)
aConv[i] = a[i];
quickSort(b, 0, b.length - 1);
quicksort(c, 0, c.length - 1);
qs_quicksort(d, 0, d.length - 1);
isSorted(new Integer[][] { aConv, b, c, d });
System.out.println("All properly sorted");
}
public static void isSorted(Integer[][] arrays) {
if (arrays.length != 4) {
System.out.println("error sorting, input arr len");
return;
}
for (int i = 0; i < ARR_SIZE; ++i) {
int val1 = arrays[0][i].compareTo(arrays[1][i]);
int val2 = arrays[1][i].compareTo(arrays[2][i]);
int val3 = arrays[2][i].compareTo(arrays[3][i]);
if (val1 != 0 || val2 != 0 || val3 != 00) {
System.out.printf("Error [i = %d]: a = %d, b = %d, c = %d", i, arrays[0][i], arrays[1][i], arrays[2][i], arrays[3][i]);
break;
}
}
}
public static int partition(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right)/2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
public static void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
public static int partition(Integer[] arr, int left, int right) {
int i = left, j = right;
Integer pivot = arr[(left + right)/2];
while (i <= j) {
while (arr[i].compareTo(pivot) < 0)
i++;
while (arr[j].compareTo(pivot) > 0)
j--;
if (i <= j) {
Integer temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
return i;
}
public static void quickSort(Integer[] arr, int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
static int findpivot(Comparable[] A, int i, int j)
{
return (i+j)/2;
}
static <E> void swap(E[] A, int p1, int p2) {
E temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
static void quicksort(Comparable[] A, int i, int j) { // Quicksort
int pivotindex = findpivot(A, i, j); // Pick a pivot
swap(A, pivotindex, j); // Stick pivot at end
int k = partition(A, i, j-1, A[j]);
swap(A, k, j); // Put pivot in place
if ((k-i) > 1) quicksort(A, i, k-1); // Sort left partition
if ((j-k) > 1) quicksort(A, k+1, j); // Sort right partition
}
static int partition(Comparable[] A, int left, int right, Comparable pivot) {
while (left <= right) { // Move bounds inward until they meet
while (A[left].compareTo(pivot) < 0) left++;
while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--;
if (right > left) swap(A, left, right); // Swap out-of-place values
}
return left; // Return first position in right partition
}
static <E> void qs_swap(E[] A, int p1, int p2) {
E temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
static void qs_quicksort(Comparable[] A, int i, int j) { // Quicksort
int pivotindex = (i+j)/2;
qs_swap(A, pivotindex, j); // Stick pivot at end
int k = qs_partition(A, i, j-1, A[j]);
qs_swap(A, k, j); // Put pivot in place
if ((k-i) > 1) qs_quicksort(A, i, k-1); // Sort left partition
if ((j-k) > 1) qs_quicksort(A, k+1, j); // Sort right partition
}
static int qs_partition(Comparable[] A, int left, int right, Comparable pivot) {
while (left <= right) { // Move bounds inward until they meet
while (A[left].compareTo(pivot) < 0) left++;
while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--;
if (right > left) { qs_swap(A, left, right); // Swap out-of-place values
left++; right--;}
}
return left; // Return first position in right partition
}
}
これは出力を生成します。今すぐ
56910 nano, qs avg - 'int'
69498 nano, qs avg - 'Integer'
76762 nano, qs avg - 'Comparable' (SO user code)
71846 nano, qs avg - 'Comparable' (SO user code - edit)
All properly sorted
、単に非プリミティブ対プリミティブを使用している場合
結果を破壊する「整数」対「intは」偉大な差分を示している（私はコードのいくつかの点で確かにボクシングかもしれないが、うまくいけば重要なスポットではない;） - これを編集してください）。 'int'と 'Integer'は 'int' 'Integer'を除いて同じコードを使用します。 'INT'
public static int partition(int arr[], int left, int right)
public static void quickSort(int arr[], int left, int right)
と '整数'
public static int partition(Integer[] arr, int left, int right)
public static void quickSort(Integer[] arr, int left, int right)
それぞれ、この比較で使用されている以下の4つのメソッドのシグネチャを参照。
はその後
static int findpivot(Comparable[] A, int i, int j)
static <E> void swap(E[] A, int p1, int p2)
static void quicksort(Comparable[] A, int i, int j)
static int partition(Comparable[] A, int left, int right, Comparable pivot)
と修正のもの、
static <E> void qs_swap(E[] A, int p1, int p2)
static void qs_quicksort(Comparable[] A, int i, int j)
static int qs_partition(Comparable[] A, int left, int right, Comparable pivot)
、あなたが投稿元のコードに関連するメソッドのシグネチャがあるあなたが見ることができるように、変更されたコードでは、findpivotを除去しましたquicksortの呼び出し元に直接置き換えられます。また、パーティションメソッドはそれぞれ左と右のカウンタを獲得しました。 left++; right--;
最後に、クイックソートの4つのバリエーションが実際に唯一の目的であったことを確認するために、isSorted（）メソッドを追加して同じ生成コンテンツの妥当性をチェックしました。 4種類。
結論として、私の編集は、ナノ秒の時間の一部を節約したかもしれませんが、Integerテストと同じ時間を達成することはできませんでした。うまくいけば私は何も明らかに欠けていないし、必要に応じて編集が歓迎です。乾杯。
を実行するたびに、パフォーマンスの最適化を行うことはありませんけれども明らかではなかったですパフォーマンス上の問題があり、コードのどの部分にあるのかがわかりません。 –
実行コードをプロファイリングして、ボトルネックがどこにあるか確認しましたか？ – bradimus