测试算法的性能
简单记录-bobo老师的玩转算法系列–玩转算法 -排序基础
04-Selection-Sort-Detect-Performance
衡量算法性能 ，看排特定的数据集上的执行时间。
那就写一个算排序时间的，测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间。
Java代码实现
SortTestHelper
package algo;
import java.lang.reflect.Method;
import java.lang.Class;
public class SortTestHelper {
// SortTestHelper不允许产生任何实例
private SortTestHelper(){}
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
assert rangeL <= rangeR;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = new Integer((int)(Math.random() * (rangeR - rangeL + 1) + rangeL));
return arr;
}
// 打印arr数组的所有内容
public static void printArray(Object arr[]) {
for (int i = 0; i < arr.length; i++){
System.out.print( arr[i] );
System.out.print( ' ' );
}
System.out.println();
return;
}
// 判断arr数组是否有序
public static boolean isSorted(Comparable[] arr){
for( int i = 0 ; i < arr.length - 1 ; i ++ )
// 只要 arr[i] > arr[i+1] 无序 我们要的是从小到大的
if( arr[i].compareTo(arr[i+1]) > 0 )
return false;
return true;
}
// 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
public static void testSort(String sortClassName, Comparable[] arr){
// 通过Java的反射机制，通过排序的类名，运行排序函数
// *
try{
// 通过sortClassName获得排序函数的Class对象
Class sortClass = Class.forName(sortClassName);
// 通过排序函数的Class对象获得排序方法
Method sortMethod = sortClass.getMethod("sort",new Class[]{Comparable[].class});
// 排序参数只有一个，是可比较数组arr
Object[] params = new Object[]{arr};
long startTime = System.currentTimeMillis();
// 调用排序函数
sortMethod.invoke(null,params);
long endTime = System.currentTimeMillis();
assert isSorted( arr );
System.out.println( sortClass.getSimpleName()+ " : " + (endTime-startTime) + "ms" );
}
catch(Exception e){
e.printStackTrace();
}
}
}
SelectionSort
package algo;
import java.util.*;
public class SelectionSort{
// 我们的算法类不允许产生任何实例
private SelectionSort(){}
public static void sort(Comparable[] arr){
int n = arr.length;
for( int i = 0 ; i < n ; i ++ ){
// 寻找[i, n)区间里的最小值的索引
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
// 使用compareTo方法比较两个Comparable对象的大小
//arr[j].compareTo( arr[minIndex] )
if( arr[j].compareTo( arr[minIndex] ) < 0 )
minIndex = j;
swap( arr , i , minIndex);
}
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
// 测试排序算法辅助函数
int N = 1000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10000);
SortTestHelper.testSort("algo.SelectionSort", arr);//1000个数时间稍微变化 13ms
System.out.println("判断arr数组是否有序:" + SortTestHelper.isSorted(arr));
SortTestHelper.printArray(arr);
return;
}
}
Result
D:Environmentsjdk-11.0.2injava.exe -javaagent:D:JavaideaIU-2019.2.winlibidea_rt.jar=6995:D:JavaideaIU-2019.2.winin -Dfile.encoding=UTF-8 -classpath D:IdeaProjectsimoocPlay-with-Algorithms 2-Sorting-Basicoutproduction 4-Selection-Sort-Detect-Performance algo.SelectionSort
SelectionSort : 13ms
判断arr数组是否有序:true
20 27 35 49 105 106 113 120 122 132 135 144 153 155 163 168 169 171 183 194 222 232 252 252 278 288 333 335 346 356 365 369 400 414 418 424 428 436 455 461 473 477 483 496 528 532 533 533 533 537 539 553 559 573 604 614 617 636 639 649 656 665 671 674 679 682 684 700 704 717 717 719 730 741 759 763 772 775 777 779 785 794 797 811 814 815 822 823 824 839 843 868 875 897 903 906 918 926 947 948 958 1012 1044 1046 1053 1076 1090 1095 1099 1101 1122 1124 1127 1129 1141 1174 1178 1180 1181 1195 1197 1203 1206 1222 1227 1237 1244 1249 1276 1287 1300 1312 1316 1341 1348 1349 1353 1365 1369 1378 1391 1398 1407 1421 1424 1457 1472 1499 1506 1511 1520 1526 1567 1577 1578 1579 1583 1592 1594 1602 1646 1651 1654 1666 1694 1700 1703 1703 1732 1733 1735 1735 1759 1767 1770 1776 1777 1783 1788 1807 1809 1810 1813 1820 1822 1839 1849 1856 1867 1883 1890 1897 1908 1918 1922 1930 1933 1955 1960 1961 1963 1969 1980 1990 1996 1997 2001 2020 2025 2028 2035 2036 2046 2049 2060 2067 2085 2109 2129 2132 2134 2135 2139 2145 2165 2168 2176 2181 2191 2215 2256 2259 2276 2276 2298 2303 2305 2369 2373 2382 2405 2411 2436 2450 2453 2472 2483 2502 2515 2516 2530 2537 2552 2567 2581 2582 2607 2624 2630 2666 2688 2692 2701 2708 2709 2721 2729 2731 2734 2746 2750 2754 2757 2777 2783 2788 2791 2803 2810 2814 2824 2829 2830 2848 2850 2851 2856 2856 2866 2882 2886 2891 2895 2906 2917 2924 2927 2937 2938 2939 2950 2980 2988 2990 2999 3009 3018 3019 3037 3039 3069 3078 3084 3102 3118 3132 3148 3173 3186 3197 3222 3244 3256 3261 3268 3273 3277 3280 3282 3288 3307 3327 3337 3348 3354 3359 3366 3375 3383 3395 3398 3404 3411 3421 3427 3435 3436 3474 3479 3480 3497 3499 3522 3531 3540 3563 3564 3572 3595 3598 3609 3634 3652 3662 3663 3665 3667 3668 3673 3693 3706 3717 3734 3740 3747 3748 3769 3780 3785 3797 3804 3807 3812 3820 3839 3860 3868 3877 3880 3903 3907 3907 3921 3939 3954 4004 4005 4010 4015 4016 4017 4023 4025 4051 4059 4071 4072 4073 4079 4089 4093 4094 4130 4137 4139 4178 4190 4192 4212 4215 4220 4221 4249 4251 4255 4257 4266 4275 4280 4311 4318 4325 4339 4348 4361 4371 4377 4385 4404 4413 4416 4431 4431 4469 4471 4474 4475 4481 4482 4498 4518 4521 4542 4545 4547 4548 4556 4561 4571 4574 4603 4611 4613 4613 4635 4643 4643 4646 4647 4654 4659 4659 4672 4675 4675 4687 4697 4721 4723 4733 4741 4749 4761 4770 4785 4787 4794 4799 4806 4809 4821 4823 4836 4848 4850 4858 4859 4861 4862 4863 4878 4879 4913 4917 4932 4935 4935 4941 4945 4952 4975 4981 5046 5065 5067 5091 5095 5100 5101 5105 5106 5112 5130 5142 5146 5147 5158 5162 5167 5169 5188 5213 5228 5229 5229 5240 5245 5255 5264 5311 5317 5322 5336 5337 5354 5360 5375 5388 5391 5395 5402 5411 5423 5433 5440 5443 5443 5467 5471 5476 5484 5508 5515 5516 5516 5520 5543 5572 5576 5577 5581 5584 5596 5603 5613 5616 5625 5626 5632 5658 5661 5663 5679 5686 5688 5696 5698 5708 5716 5721 5721 5723 5726 5738 5738 5749 5753 5755 5770 5772 5784 5823 5833 5835 5838 5840 5846 5850 5862 5876 5881 5884 5896 5922 5946 5954 5955 5964 5964 5969 5979 5980 5994 5997 5998 5999 6004 6005 6008 6033 6035 6036 6044 6055 6068 6111 6131 6154 6156 6157 6159 6179 6180 6192 6200 6205 6215 6218 6229 6246 6249 6284 6289 6296 6303 6325 6334 6337 6338 6353 6353 6364 6366 6372 6375 6407 6432 6480 6480 6481 6483 6485 6489 6489 6496 6498 6522 6529 6539 6550 6558 6560 6570 6572 6585 6591 6597 6605 6622 6624 6627 6637 6648 6658 6665 6667 6681 6685 6693 6693 6719 6734 6738 6739 6744 6748 6761 6763 6772 6773 6784 6792 6803 6806 6818 6842 6842 6844 6845 6853 6869 6889 6909 6919 6940 6941 6955 6962 6969 6971 7018 7024 7044 7053 7056 7060 7074 7111 7116 7119 7149 7156 7184 7186 7199 7209 7211 7232 7252 7258 7261 7273 7288 7304 7309 7309 7312 7312 7314 7314 7322 7323 7325 7337 7341 7390 7398 7403 7410 7435 7443 7444 7451 7451 7462 7475 7476 7494 7494 7504 7556 7557 7577 7590 7635 7643 7657 7670 7676 7694 7699 7700 7702 7705 7773 7776 7778 7797 7810 7811 7816 7847 7855 7877 7886 7892 7901 7934 7939 7940 7941 7954 7955 7957 7998 8017 8017 8019 8024 8046 8049 8056 8082 8099 8104 8111 8132 8139 8145 8147 8150 8162 8180 8188 8200 8227 8242 8254 8264 8275 8284 8284 8307 8307 8308 8324 8337 8339 8340 8344 8349 8361 8369 8378 8383 8398 8408 8419 8459 8462 8470 8475 8482 8483 8485 8523 8550 8554 8569 8580 8581 8592 8595 8603 8613 8635 8637 8659 8662 8691 8694 8702 8705 8726 8744 8758 8758 8788 8803 8806 8842 8844 8851 8882 8884 8897 8900 8902 8903 8916 8919 8920 8925 8940 8955 8976 8978 8995 9016 9032 9035 9036 9076 9102 9108 9138 9139 9152 9195 9199 9202 9214 9239 9251 9253 9261 9266 9273 9274 9283 9289 9295 9295 9341 9359 9382 9391 9408 9412 9427 9446 9451 9458 9466 9485 9492 9493 9498 9505 9522 9522 9527 9527 9537 9554 9556 9558 9589 9593 9617 9618 9620 9628 9629 9631 9635 9648 9670 9673 9727 9742 9756 9761 9762 9766 9769 9775 9782 9796 9797 9809 9822 9828 9831 9873 9875 9876 9891 9912 9940 9940 9951 9956 9957 9958 9966 9969 9976 9981 9988
Process finished with exit code 0