如何跟踪 Java 中 insertionSort 算法实现的持续时间？

Question

我需要一些关于在 Java 中实现插入排序算法的帮助。我有一个巨大的文件，每行包含一个 BigInteger。该文件的大小约为 250 MB。我的目标是将这些值存储在 ArrayList<BigInteger> 中，然后使用如下开发的 insertionSort 对 ArrayList 进行排序：

    /**
 * Method insertionSort
 * This method sorts ArrayList list made of generic T elements
 * @param list the ArrayList to be sorted
 */
public static <T extends Comparable<T>> void insertionSort(ArrayList<T> list){
    T temp;
    int position;
    for(int i = 1; i < list.size(); i++){
        temp = list.get(i);
        position = i;
        while(position > 0 && list.get(position-1).compareTo(temp) > 0){
            //Shift bigger values to the right
            list.set(position, list.get(position-1));
            position--;
        }
        list.set(position, temp);
    }
}

我还需要跟踪排序方法的持续时间。例如：假设 x 是排序完成的百分比，y 方法完成其工作所需的秒数。

while(method is sorting){
    System.out.println("Sorting started...");
    ***Sorting in Progress***
    System.out.println("Method has sorted x% of ArrayList");
    ***Sorting Method keeps doing its job***
    System.out.println("Method has sorted x% of ArrayList");
    ***Sorting Method keeps doing its job***
    System.out.println("Method has sorted 100% of ArrayList");
    System.out.println("It took y seconds to sort the provided ArrayList");
}

现在我的问题是：当方法是运行时，如何跟踪此算法的持续时间和完成排序的百分比？希望我已经清楚了，你们可以帮助我。谢谢

Answer 1

您可以使用此代码跟踪持续时间，在我的示例中以秒为单位：

long start = System.nanoTime(); //you take the instant when the operation is starting
//here is where the code will do stuff
Double secondsLenght = (System.nanoTime()-start)/ Math.pow(10, 9); //this is for capturing the result in seconds

然后您可以使用它获得中间状态，并根据您的变量计算百分比，在您的示例中，list.size() 和 position

Answer 2

这是一个完整的解决方案，包括百分比记录和时间测量：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class App {
    /**
     * Method insertionSort
     * This method sorts ArrayList list made of generic T elements
     * @param list the ArrayList to be sorted
     */
    public static <T extends Comparable<T>> void insertionSort(List<T> list){
        T temp;
        int position;
        int size = list.size();
        for(int i = 1; i < size; i++){
            temp = list.get(i);
            position = i;
            while(position > 0 && list.get(position-1).compareTo(temp) > 0){
                //Shift bigger values to the right
                list.set(position, list.get(position-1));
                position--;
            }
            list.set(position, temp);
            System.out.println("Sorting... " + ((double)i/(double)size)*100.0 + "%");
        }
    }

    public static void main(String args[]) {
        long startTime = System.nanoTime();

        List<Integer> list = new ArrayList<>(Arrays.asList(10,6,3,8,1,7,2,9,5,4));

        App.insertionSort(list);

        Double secondsLenght = (System.nanoTime()-startTime)/ Math.pow(10, 9);

        System.out.println(list);
        System.out.println("Sorting took " + secondsLenght + " seconds.");

    }
}

一些补充意见：

为什么要实现自己的排序算法？
您应该将 insertionSort 方法的签名更改为 insertionSort(List<T> list)，使其独立于 List 实现。
与其在函数内部执行 println，不如实现某种回调来执行更新。

如何跟踪 Java 中 insertionSort 算法实现的持续时间？

How to track duration of insertionSort Algorithm Implementation in Java?

java

sorting

insertion-sort