测量时间的不同排序方法

Question

我正在编写代码，该代码应该使用特定大小的数组测量不同排序方法的不同排序时间，并在GUI中显示输出时间。我已经得到了它的大部分工作，但程序不是每次显示相同的结果。例如，它会说一次运行0.2毫秒，下一次运行0.1毫秒。我认为问题是在runSort()方法。有人能帮帮我吗?下面是代码:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.Random;
import java.util.Arrays;
public class Benchmarks extends JFrame
{
  private static int numberOfRuns = 20;
  private JTextField arraySizeInput, display;
  private String sortMethodNames[] =
  {"Selection Sort", "Insertion Sort", "Mergesort", "Quicksort", "Arrays.sort"};
  private JComboBox chooseSortMethod;
  private final long seed;
  private int arraySize;
// Constructor
   public Benchmarks()
  {
     super("Benchmarks");
     Container c = getContentPane();
     c.setLayout(new GridLayout(6, 1));
     c.add(new JLabel(" Array size: "));
     arraySizeInput = new JTextField(4);
     arraySizeInput.setText("1000");
     arraySizeInput.selectAll();
     c.add(arraySizeInput);
     chooseSortMethod = new JComboBox(sortMethodNames);
     c.add(chooseSortMethod);
     JButton run = new JButton("Run");
     run.addActionListener(new RunButtonListener());
     c.add(run);
     c.add(new JLabel(" Avg Time (milliseconds): "));
     display = new JTextField("   Ready");
     display.setBackground(Color.YELLOW);
     display.setEditable(false);
     c.add(display);
  // Use the same random number generator seed for all benchmarks
  //   in one run of this program:
     seed = System.currentTimeMillis();
  }
// Fills a[] with random numbers and sorts it using the sorting method
// specified in sortMethod:
//     1 -- Selection Sort
//     2 -- Insertion Sort
//     3 -- Mergesort
//     4 -- Quicksort
// This is repeated numberOfRuns times for better accuracy
// Returns the total time it took in milliseconds.
   private long runSort(double[] a, int sortMethod, int numberOfRuns)
  {
     long startTime;
     long endTime;
     long diffTime;  
     Random generator = new Random(seed);
     for(int i= a.length-1; i>0; i--)
     {
        a[i]= generator.nextDouble(); 
     }
     startTime= System.currentTimeMillis();
     switch(sortMethod) 
     {  
        case 1: //Selection Sort
           SelectionSort sel = new SelectionSort(); 
           sel.sort(a);
           break; 
        case 2: //Insertion Sort 
           InsertionSort nsert= new InsertionSort();
           nsert.sort(a); 
           break; 
        case 3: //Merge Sort 
           Mergesort merge = new Mergesort(); 
           merge.sort(a); 
           break; 
        case 4: // Quick Sort 
           Quicksort quick = new Quicksort();
           quick.sort(a); 
           break; 
     }
     endTime= System.currentTimeMillis();
     diffTime= endTime- startTime; 

     return  diffTime ;  
  }
// Handles Run button events
   private class RunButtonListener implements ActionListener
  {
      public void actionPerformed(ActionEvent e)
     {
        String inputStr = arraySizeInput.getText().trim();
        try
        {
           arraySize = Integer.parseInt(inputStr);
        }
            catch (NumberFormatException ex)
           {
              display.setText(" Invalid array size");
              arraySize = 0;
              return;
           }  
        if (arraySize <= 0)
        {
           display.setText(" Invalid array size");
           return;
        }
        if (arraySize <= 0)
           return;
        int sortMethod = chooseSortMethod.getSelectedIndex() + 1;
        double a[] = new double[arraySize];
        double avgTime = (double)runSort(a, sortMethod, numberOfRuns)
                                                      / numberOfRuns;
        display.setText(String.format("  %.2f", avgTime));
        arraySizeInput.selectAll();
        arraySizeInput.requestFocus();
        System.out.println("Array size = " + arraySize +
           " Runs = " + numberOfRuns + " " +
           sortMethodNames[sortMethod - 1] + " avg time: " + avgTime);
     }
  }
//************************************************************
   public static void main(String[] args)
  {
     numberOfRuns = 20;
     if (args.length > 0)
     {
        int n = -1;
        try
        {
           n = Integer.parseInt(args[0].trim());
        }
            catch (NumberFormatException ex)
           {
              System.out.println("Invalid command-line parameter");
              System.exit(1);
           }
        if (n > 0)
           numberOfRuns = n;
     }
     Benchmarks window = new Benchmarks();
     window.setBounds(300, 300, 180, 200);
     window.setDefaultCloseOperation(EXIT_ON_CLOSE);
     window.setVisible(true);
  }
}

谢谢你的帮助

Answer 1

由于许多次要因素，例如计算机当时有多忙，您会得到不同的结果。此外，System.currentTimeMillis()本质上是不准确的;在某些系统上，5ms可以测量为0到10ms。为了在测量少量时间时获得更好的准确性，您应该使用System.nanoTime()。此外，在测量开始时间和测量结束时间之间应该没有。这意味着没有 for或while循环、if语句或switch语句。

Answer 2

你所尝试的根本是不可能的。您需要一个保证cpu时间的系统。但是调度和不同的负载使得不可能得到准确的时间。另外，java垃圾收集和从java环境进行优化之类的事情会改变您的结果。你可以使用像junitbenchmark这样的框架，让代码多次运行——但是记住这不会给你一个"真正可用"的结果。它可以帮助您确定每个算法相对于其他算法的速度