수업 속도를 향상시키는 방법은 무엇입니까?

Question

나는 이것을 실행하고 있으며 나는 충분히 빨리 달리지 않을 것이라고 말하고있다. 이 러닝 클래스의 속도를 높이는 좋은 방법은 무엇입니까? 중첩 된 while 루프를 변경해야한다고 생각합니다. 그것이 내가 생각할 수있는 유일한 것입니다. if 문은 모두 선형이어야합니다 ...

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.*; 

public class QSortLab { 

    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 
    } 
} 

Answer 1

중첩 된 while 루프를 변경해야한다는 것은 무엇을 의미합니까? 빠른 정렬은 이러한 기능으로 정의됩니다. 제거가 제대로 작동하지 않습니다.

기본적으로 최적화는 primitives vs objects이 다른 경향이 있다는 것을 알아야합니다. 예 : primitives on stack/heap 스택을 작게 유지하려면 & 힙 저장 객체는 refs able to be on stack입니다.

그럼 몇 가지 물건을 테스트 할 수

• 원시적 빠른 정렬 빠른 정렬 (같은 코드 위와하지만, 정수 클래스)
• 원래는
• 원래 코드를 게시 정수 (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 

를 (I 단순히 비 프리미티브 대 프리미티브를 사용하여 큰 DIFF를 보여줍니다 코드의 일부 지점에서 권투있을 수 있지만 잘하면 중요한 명소;) -이 경우 편집하십시오). '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) 

각각이 비교에 사용되는 다음과 같은 네 가지 방법 서명을 참조하십시오.

그런 다음

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--;

마지막으로 quicksort의 이러한 4 가지 변형이 실제로 목적을 달성했는지 확인하기 위해 동일한 생성 된 콘텐츠의 유효성을 확인하는 isSorted() 메소드를 추가했으며 각 메소드에 따라 정렬되었습니다. 4 가지 종류.

결론적으로 필자의 편집 내용은 시간당/나노초를 절약 할 수 있었지만 Integer 테스트와 동일한 시간을 달성 할 수 없었습니다. 다행히도 나는 무엇이든을 놓치지 않았으며 필요한 경우 편집을 환영합니다. 건배

Answer 2

글쎄, 내 컴퓨터의 타이머가 끔찍하기 때문에 이것이 어떤 차이가 있는지 테스트 할 수는 없지만,이 알 고의 작업 대부분이 스왑 기능으로 수행된다고 생각합니다. 그것을보다 효율적으로 만드는 방법, 아마도 함수 호출/리턴 자체가 사이클을 소모 할 수 있으며, 함수가 호출 될 때마다 임시 변수를 만들 때 사이클이 필요하므로 스왑 작업이 줄을 서서. 나는 내 컴퓨터에서 테스트 할 때 nanotimer 결과 +/- 20 % 나 프로그램

public class QSort2 { 

static int findpivot(Comparable[] A, int i, int j) { 
    return (i + j)/2; 
} 

static Comparable 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 
    temp = A[pivotindex]; 
    A[pivotindex] = A[j]; 
    A[j] = temp; 
    int k = partition(A, i, j - 1, A[j]); 
    //swap(A, k, j);      // Put pivot in place 
    temp = A[k]; 
    A[k] = A[j]; 
    A[j] = temp; 
    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 
      temp = A[left]; 
      A[left] = A[right]; 
      A[right] = temp; 
     } 
    } 
    return left;   // Return first position in right partition 
} 

} 당신이 ** 확인하지 않는 한