0

我正在尝试比较 QuickSort 的 java 实现及其混合版本的执行（对小于整数 k 的分区使用 InsertionSort）。我编写了一个测试类来分析算法对某些值 ok k (1 <= k <= 25) 的行为。对于 k 的每个值，该类针对不同大小的输入数组比较两种算法。

我无法为数组大小的某些值运行程序，例如大于 4000 的值。执行达到一些不同的值然后冻结，一段时间后它将完成但我没有计算输出。（我正在使用日食）。
可能是什么问题呢？我希望对从 10 到 10000（至少）的数组大小进行两种算法的比较。
代码如下：

public class Main {

private static final int MAX_K = 25;
private static final int MAX_SIZE = 4500;
private static final int ADD_SIZE = 100;
private static int size = 10;

private static QuickSort qSort;
private static HybridSort hSort;

private static void initArray(int[] A) {
    Random rand = new Random();
    for (int i = 0; i < A.length; i++) {
        // A[i] = (int)(Math.random()*100000);
        A[i] = rand.nextInt();

    }
}

private static int[] A = new int[10];
private static int[] B = new int[10];

public static void main(String[] args) {

    try {

        FileWriter fstream = new FileWriter("out.txt");
        BufferedWriter out = new BufferedWriter(fstream);
        out.write("Init file");

        qSort = new QuickSort();
        hSort = new HybridSort();

        /************************************************/
        /* Comparison */
        /************************************************/

        for (int i = 1; i <= MAX_K; i++) {
            hSort.setK(i);

            int p = 0;
            for (int j = size; j <= MAX_SIZE; j = j + ADD_SIZE) {

                A = new int[j];
                B = new int[j];
                initArray(A);
                initArray(B);

                long sTime = System.nanoTime();
                qSort.quickSort(A, 0, A.length - 1);
                long qDuration = System.nanoTime() - sTime;

                sTime = System.nanoTime();
                hSort.hybridSort(B, 0, B.length - 1);
                long hDuration = System.nanoTime() - sTime;

                out.append(/* "\nA: " +printArray(A)+ */"K: " + i + " A["
                        + j + "]\tQ = " + qDuration + " H = " + hDuration
                        + "\n");

                String h = Long.toString(hDuration);
                String q = Long.toString(qDuration);

                if (h.length() < q.length()) {
                    p++;
                    out.append("\t#OUTPERM for K: "
                            + i
                            + "\t\t"
                            + hDuration
                            + "\t\t < \t\t "
                            + qDuration
                            + "\t\t\t\t| A[]\t\t"
                            + A.length
                            + ((q.length() - h.length()) == 2 ? "\t Magn. 2"
                                    : "") + "\n");
                }
            }
            if (p > 0)
                out.append("#P= " + p + " for K= " + i + "\n\n");
        }
        out.append("Close file");
        out.close();
    } catch (IOException e) {

    }
}

}

算法类：

public class QuickSort {


public void quickSort(int[] A, int left, int right){
    if (left < right) {
        int m = Partition(A, left, right);
        quickSort(A, left, m-1);
        quickSort(A, m, right);
    }
}


private int Partition(int[] A, int left, int right){
    int pivot = A[right];
    int i = left;
    int j = right;

    while (true) {
        while ( (A[j] > pivot)) {
            j--;
        }
        while ((A[i] < pivot)) {
            i++;
        }
        if (i < j){
            int swap = A[j];
            A[j] = A[i];
            A[i] = swap;
        }else{
            return i;
        }
    }
}

}



public class HybridSort {

int k;
int m;
InsertionSort iSort;

public HybridSort() {
    k = 3;
    iSort = new InsertionSort();
}

public void hybridSort(int[] A, int left, int right) {
    if (left < right) {
        if ((right - left) < k) {
                                    iSort.sort(A,left,right);
        } else {                
            m = Partition(A, left, right);
            hybridSort(A, left, m - 1);
            hybridSort(A, m, right);
        }
    }
}

private int Partition(int[] A, int left, int right) {
    int pivot = A[right];
    int i = left;
    int j = right;

    while (true) {
        while ((A[j] > pivot) && (j >= 0)) {
            j--;
        }
        while ((A[i] < pivot) && (i < A.length)) {
            i++;
        }
        if (i < j) {
            int swap = A[j];
            A[j] = A[i];
            A[i] = swap;
        } else {
            return i;
        }
    }
}


public void setK(int k) {
    this.k = k;
}
}
4

3 回答 3

0

一些提示/可能的解决方案？：

我还没有阅读您的 QuickSort 或 HybridSort 实现，但我假设它们是正确的。

  1. 如果您要比较两种算法的性能，您绝对应该将它们的性能与相同的输入进行比较。目前您正在生成两个随机数组（尽管大小相同）。这不一定是一个准确的测试，因为我可以很容易地找到一个测试用例，其中如果随机生成器要欺骗你，一种算法将优于另一种算法。

  2. 在我看来，你比较这两种算法的逻辑有点奇怪和不正确。为什么要比较时间字符串的长度？根据您的逻辑，1 与 9 相同，1,000,000,000 与 9,999,999,999 相同，这显然是不正确的。一种算法几乎是另一种算法的 10 倍。

  3. 此外，没有输出的一个原因可能是您仅在混合排序优于快速排序而不是相反时输出的原因。我相信还有其他原因，但这可能是一个容易引起注意的原因（如果您的实现不正确）。

    我确实注意到您关闭了输出流，这很好，因为这是没有输出的一个非常常见的原因。但是，您应该在 try-catch 部分关闭蒸汽，finally因为这样它们就保证会关闭。您可能会收到 IOException，在您的情况下，这也不会关闭输出组，因此不会导致文件中没有输出。

这是我在进行任何比较测试时会遵循的示例结构。它易于阅读且易于调试，具有足够的输出，可以让您找出哪种算法性能更好。这只是一个建议。

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.Random;

public class Tester {

  private static int[] initArray(int size) {
    Random rand = new Random();
    int[] arr = new int[size];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = rand.nextInt();
    }
    return arr;
  }

  public static void main(String[] args) {
    final int MAX_ITERATIONS = 25;
    final int INITIAL_ARRAY_SIZE = 10;
    final int MAX_ARRAY_SIZE = 4500;
    final int ARRAY_SIZE_INCREMENT = 100;

    long start;
    int[] score = null;

    PrintWriter out = null;
    try {
      out = new PrintWriter(new FileOutputStream("out.txt"));
      for (int arraySize = INITIAL_ARRAY_SIZE; arraySize <= MAX_ARRAY_SIZE; arraySize += ARRAY_SIZE_INCREMENT) {
        // score[0] is for quickSort and score[1] is for hybridSort
        score = new int[2];
        for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
          int[] testArray = initArray(arraySize);
          int[] testArrayCopy = new int[arraySize];
          System.arraycopy(testArray, 0, testArrayCopy, 0, arraySize);

          start = System.nanoTime();
          // Do quicksort here using testArray
          long qSortfinish = System.nanoTime() - start;

          System.arraycopy(testArray, 0, testArrayCopy, 0, arraySize);
          start = System.nanoTime();
          // Do hybridsort here using testArrayCopy
          long hybridSortfinish = System.nanoTime() - start;

          // Keep score
          if (qSortfinish < hybridSortfinish)
            score[0]++;
          else if (qSortfinish > hybridSortfinish) {
            score[1]++;
          } else {
            score[0]++;
            score[1]++;
          }
        }
        out.println("Array Size: " + arraySize + " QuickSort: " + score[0] + " HybridSort: " + score[1]);
      }
    } catch (FileNotFoundException e) {
      e.printStackTrace();
    } finally {
      if (out != null)
        out.close();
    }
  }
}
于 2013-04-18T17:27:34.997 回答
0

您的实施Partition不正确。考虑下面的小测试（我Partition static为方便起见）。

两个while循环都不会执行，因为A[i] == A[j] == pivot. 此外，i<j, 所以这两个元素将被交换，从而产生完全相同的数组。因此，外while循环变为无限。

对于第一个和最后一个元素相同的任何数组，都会出现同样的问题。

public class Test {
    public static void main(String[] args) {
        int[] A = {1, 1};
        Partition(A, 0, 1);
    }

    private static int Partition(int[] A, int left, int right){
        int pivot = A[right];
        int i = left;
        int j = right;

        while (true) {
            while ( (A[j] > pivot)) {
                j--;
            }
            while ((A[i] < pivot)) {
                i++;
            }
            if (i < j){
                int swap = A[j];
                A[j] = A[i];
                A[i] = swap;
            }else{
                return i;
            }
        }
    }
}
于 2013-04-18T17:05:26.853 回答
0

您是否尝试过增加内存设置以使您的代码在 Eclipse 中运行。您可能会发现此设置从 Eclipse 运行的 Java 程序的内存很有帮助。

于 2013-04-18T17:06:13.467 回答