适当的方法来计时排序算法需要多长时间

我正在测试排序数组以查看不同排序数组的速度有多快。我想清除错误的时间，所以理想情况下我想启动一个计时器，在100次循环中运行排序，停止计时器，然后除以100得到相当准确的度量。

的问题是如果我是循环中的同一个阵列，它会按正确的第一次，然后以后每个排序，它会保持排序已经排好序排列，这不是我想要的。

也许我缺少一个明显的解决方案，但有什么办法可以让它保持分类相同的初始随机排列？

我想过每一次重新分配新排序的数组回到初始随机排列，但会弄乱我的定时器..

感谢您的任何建议

我想做些什么：

 startTime = System.nanoTime(); 
     for(int i=0; i<cntr; i++) { 
      sort array 
     } 
     endTime = System.nanoTime(); 
     time = (endTime - startTime)/cntr;

来源

2012-03-05 user1189352

FYI，定时这样的事情准确与JIT非常棘手。使用[Caliper]（http://code.google。com/p/caliper /）知道如何为你处理这个问题。 – 2012-03-05 03:41:09

您可以在开始排序前制作副本，然后从该存储副本复制到循环的每次迭代中排序的数组中。

int[] toBeSorted = new int[10000]; 
// fill the array with data 
int[] copied = new int[10000]; 
System.arrayCopy(toBeSorted, 0, copied, 0, copied.length); 
// prepare the timer, but do not start it 
for (int = 0 ; i != 100 ; i++) { 
    System.arrayCopy(copied, 0, toBeSorted, 0, copied.length); 
    // Now the toBeSorted is in its initial state 
    // Start the timer 
    Arrays.sort(toBeSorted); 
    // Stop the timer before the next iteration 
}

来源

2012-03-05 03:02:35 dasblinkenlight

如果我理解正确，每次排序后从存储的副本进行复制都会影响计时器（以毫微秒和毫秒计时）。除非我误解？ – user1189352 2012-03-05 03:03:51

@ user1189352我添加了评论，提到定时器需要停止并在各种排序之间重新启动。 – dasblinkenlight 2012-03-05 03:08:35

啊好吧我明白了，那有效，谢谢 – user1189352 2012-03-05 03:08:46

一般来说，你会停下来，并开始在你正在测试的算法的每次运行之间的延时，增加了个人次，然后通过运行数除以。这样，不包括任何“设置时间”，因为定时器在设置期间没有运行。

来源

2012-03-05 03:03:29 Amber

啊雅我知道这一点，唯一的原因，我想不出一个解决方案是因为在第一次排序后，它将继续排序已经排序的数组 – user1189352 2012-03-05 03:13:39

@ user1189352是，但是一旦你在两次试验之间停止计时器，就可以花费尽可能多的时间，因为时钟没有运行，所以你需要重新初始化要排序的数组。 – Amber 2012-03-05 03:16:46

可以使用System.currentTimeMillis()方法来获得当前的时间，那么当方法完成执行减法。

long totalRuntime = 0; 

for(int i = 0; i < 100; i++) 
{ 
    long startTime = System.currentTimeMillis(); 
    sortArrays() 
    long endTime = System.currentTimeMillis(); 

    totalRuntime += (endTime - startTime); 
} 

System.out.println("Algorithm X on average took " 
        + totalRuntime/100 + " milliseconds);

如果你想这样做X次只是为每个算法和增量保留一个计数器。然后你可以除以最后的运行总数并进行比较。

来源

2012-03-05 03:04:21

亚这就是我所做的很多，但我想循环它100+次 – user1189352 2012-03-05 03:05:29

我看到你的编辑，但我相信它将在第二种排序后继续排序已经排序的数组。 – user1189352 2012-03-05 03:11:19

像这样的东西

new array equals random array, 
start timer 
sort new array 
stop timer 
add time to your list of times 
repeat until necessary

去只要你每次复制原始数组，你将永远不会排序原来

来源

2012-03-05 03:07:06

thx的建议，但正如我的OP所述，为什么我不能这样做的问题是因为在第一次排序后，我会排序一个已经排序的数组 – user1189352 2012-03-05 03:16:12

这就是第一行是'new array equals random array'每次将原始数组复制到一个新数组中，然后对新数组进行排序，这样您总是可以以未排序的顺序维护原始数组。它和dasblinken一样，只是伪代码。 – 2012-03-05 03:20:22

把排序算法的功能，并保持调用函数使用clone方法克隆它之后，将数组传递给函数。您可以调用当前时间函数并在每次运行循环时将其打印出来。

来源

2012-03-05 03:08:05 everconfusedGuy

，这也会工作，谢谢 – user1189352 2012-03-05 03:14:45

如果你愿意吹内存，那么就做出同样的阵列100（或然而，许多）副本开始定时之前。如果你不是，那么时间排序和复制在一起，然后时间只是复制，看看你的分拣+复制时间大约有多少是用于复制。

此外，阿里纳斯：考虑使用一个基准框架像Caliper，而不是做你自己“手动”的标杆。这很容易，而且他们已经解决了许多问题，您甚至可能不知道这些问题会影响您的时间安排。

来源

2012-03-05 03:10:33 jacobm

啊雅，我宁愿找到一个有效的方式这样做，虽然好思想和THX的建议 – user1189352 2012-03-05 03:15:20

适当的方法来计时排序算法需要多长时间

回答

相关问题