java - 如何在java排序算法中找到两个或多个计时之间的最低计时？

Question

我有一个计时方法，可以获取算法运行所需的时间。

public static long timing()
{
    long startTime, endTime,elapsedTime;

    startTime = System.nanoTime();
    endTime = System.nanoTime();
    elapsedTime = (endTime - startTime) ;

    return elapsedTime ;
}

假设我有两种排序算法，一个迭代合并排序调用

        int[] copy12 = new int[values.length];
        System.arraycopy(values,0,copy12,0,values.length);

        iterativeMergeSort(copy12);
        System.out.println("\nTime for iterative merge sort: " + timing() + " nanoseconds");
        isSorted(copy12);
        System.out.println("Iterative merge sort successfully sorted " + count + " elements");

以及插入排序对值的调用

        int[] copy9 = new int[values.length];
        System.arraycopy(values,0,copy9,0,values.length);

        insertSort(copy9);
        System.out.println("\nTime for insertion sort: " + timing() + " nanoseconds");
        System.out.println("insertion sort successfully sorted " + count + " elements");

它们都有不同的计时，我试图找到运行最快的算法并将其打印出来，如下所示:

The best sorting method is insertion sort 
It sorted all 1000 numbers in 656000 nanoseconds.

在java中我怎么可能采取这两种不同的计时，或者是否有更多的算法并比较它们以查看哪个更快？我已经搜索过，但没有找到执行此操作的方法。

Answer 1

根据评论，您的问题似乎由两部分组成:

1. 如何正确计算函数的运行时间；
2. 如何找到 12 个函数中最小的运行时间。

<小时/>

<强>1。计算函数的运行时间

你的timing()方法并没有真正做太多事情。 你真正想做的是:

long before = System.nanoTime();
someFunction();
long after = System.nanoTime();
System.out.println("Total elapsed time is " + (after-before) + " ns.");

这将获取函数 someFunction() 的总运行时间(例如，在您的情况下为 insertSort())。 它本质上是存储两个时间戳:一个在函数调用之前，一个在函数调用之后。 函数的运行时间将是两者的差值。

您可以通过以下方式将其转化为您的问题:

// Time merge sort
long beforeMerge = System.nanoTime();
iterativeMergeSort(copy12);
long afterMerge = System.nanoTime();
long elapsedMerge = afterMerge - beforeMerge;

// Time insertion sort
long beforeInsert = System.nanoTime();
insertSort(copy9);
long afterInsert = System.nanoTime();
long elapsedInsert = afterInsert - beforeInsert;

// Print the elapsed time for each
System.out.println("Merge sort elapsed time = " + elapsedMerge + "ns.");
System.out.println("Insertion sort elapsed time = " + elapsedInsert + "ns.");
if(elapsedMerge<elapsedInsert)
    System.out.println("Merge sort was faster");
else
    System.out.println("Insertion sort was faster");

<小时/>

<强>2。找出十二个函数中运行时间最小的

现在我们可以计算一个函数的运行时间，我们对所有 12 个函数应用相同的方法。 这个想法是将所有运行时间存储在一个数组中，然后使用一个简单的循环来确定哪个运行时间最快。

// This will contain the running times of the different sorting functions
long[] elapsed = new long[12];
// This will contain the names of the sorting functions
String[] names = new String[12];

long before, after; // used to compute the running times

// Time merge sort
before = System.nanoTime();
iterativeMergeSort(copy12);
after = System.nanoTime();
elapsed[0] = after-before;
names[0] = "Merge sort";

// Time insertion sort
before = System.nanoTime();
insertSort(copy9);
after = System.nanoTime();
elapsed[1] = after-before;
names[1] = "Insertion sort";

// ... Do the same for the others ...

// Determine the smallest running time
int fastest = 0;
for(int i=1; i<12; i++) {
    if(elapsed[i]<elapsed[fastest])
        fastest = i;
}
// Now the variable fastest contains the index of the fastest function
System.out.println("The fastest function was " + names[fastest] + ", with a running time of " + elapsed[fastest] + " nanoseconds.");

这将打印如下内容:

The fastest function was Quicksort, with a running time of 12345 nanoseconds.