1、数组生成器
测试算法性能肯定不能自己手动声明创建数组了,在现代计算机上,对于O(n)级别的算法,都需要10W级别以上的数据才能看到性能,我们肯定不能手动声明10W个元素的数组吧?
所以,创建数组生成器。
这里,自己创建一个数组生成器——ArrayGenerator。
package com.mosesmin.datastructure.week01.chap02;
/**
* @Misson&Goal 代码以交朋友、传福音
* @ClassName ArrayGenerator
* @Description TODO 数组生成器
* @Author MosesMin
* @Date 2023/4/14
* @Version 1.0
*/
public class ArrayGenerator {
private ArrayGenerator() {}
public static Integer[] generatedOrderedArray(int n){
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = i;
return arr;
}
}
2、使用数组生成器进行测试
详细代码如注释:
package com.mosesmin.datastructure.week01.chap02;
/**
* @Misson&Goal 代码以交朋友、传福音
* @ClassName LinearSearch03
* @Description TODO
* @Author MosesMin
* @Date 2023/4/14
* @Version 1.0
*/
public class LinearSearch09 {
private LinearSearch09(){}
public static <E> int search(E [] data,E target){
for (int i = 0; i < data.length; i++)
if (data[i].equals(target))
return i;
return -1;
}
public static void main(String[] args) {
int n = 1000000;
Integer[] data = ArrayGenerator.generatedOrderedArray(n);// 10w的数据规模
long startTime = System.nanoTime();//单位是纳秒 纳秒-微妙-毫秒-秒 差距都是1000倍
for (int k=0;k<100;k++)
LinearSearch09.search(data,n);//这里为了验证最差的情况,就传一个找不到的目标元素100000
long endTime = System.nanoTime();
double time = (endTime-startTime)/(1000*1000*1000.0);// 最后1000.0,因为我们希望结果是个浮点数
System.out.println(time + " s");
}
}
10W的数据规模,运行一次,在我的电脑(CPU为:Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz 3.20 GHz)运行时间约为0.0027秒,即2.7毫秒。
3毫秒,可能不够稳定,不一定是线性查找法运行的时间结果,因为操作系统也在运行,我们可以再试下使用更大的数据,比如使用100W的数据规模,看看它们运行
的时间差是否为10倍左右。
运行结果:
10W数据规模:
我们看到100W的运行结果约为6.6毫秒;几毫秒的运行结果还是不够稳。
100W数据规模:
我们再试下1000W的数据规模。
我们看到1000w约为26毫秒;
注:
对于一般的计算机而言,1000W的数据规模已经是个够量的规模了。
1000W数据规模:
我们还可以看一下1亿的规模,但是运行1亿的数据规模时,我的电脑运行了很久,将近20s时间,最终显示结果约为182毫秒。
为什么实际上运行了20s时间呢?
因为对于一般的计算机来说,开1亿个整型空间,尤其时1亿个连续的整型空间时需要一些时间的,特别是我的电脑配置不太高,i5的4代cpu(Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz 3.20 GHz)。
1亿数据规模:
如果我们希望得到的时间更长一些,一个简单方法是,多做几次,这里,我们就用100W的数据规模,然后测试100次。
100W的规模,执行100次,约为218毫秒。
100W数据规模运行100次:
3、一些测试优化
1、优化一下输出log
主要改动的语句为:
优化后的代码如下:
package com.mosesmin.datastructure.week01.chap02;
/**
* @Misson&Goal 代码以交朋友、传福音
* @ClassName LinearSearch03
* @Description TODO
* @Author MosesMin
* @Date 2023/4/14
* @Version 1.0
*/
public class LinearSearch09 {
private LinearSearch09(){}
public static <E> int search(E [] data,E target){
for (int i = 0; i < data.length; i++)
if (data[i].equals(target))
return i;
return -1;
}
public static void main(String[] args) {
int n = 1000000;
Integer[] data = ArrayGenerator.generatedOrderedArray(n);// 10w的数据规模
long startTime = System.nanoTime();//单位是纳秒 纳秒-微妙-毫秒-秒 差距都是1000倍
int num = 100;
for (int k=0;k<num;k++)
LinearSearch09.search(data,n);//这里为了验证最差的情况,就传一个找不到的目标元素100000
long endTime = System.nanoTime();
double time = (endTime-startTime)/(1000*1000*1000.0);// 最后1000.0,因为我们希望结果是个浮点数
System.out.println("数据规模n为:"+n+",运行次数:"+ num +"次,运行时间为:" + time + " s.");
}
}
2、创建数据规模数组,利用循环一次测试多个数据规模
添加数据规模数组后的代码如下:
package com.mosesmin.datastructure.week01.chap02;
/**
* @Misson&Goal 代码以交朋友、传福音
* @ClassName LinearSearch03
* @Description TODO
* @Author MosesMin
* @Date 2023/4/14
* @Version 1.0
*/
public class LinearSearch09 {
private LinearSearch09(){}
public static <E> int search(E [] data,E target){
for (int i = 0; i < data.length; i++)
if (data[i].equals(target))
return i;
return -1;
}
public static void main(String[] args) {
int [] dataSize = {100000,1000000,10000000};
for (int n:dataSize) {
Integer[] data = ArrayGenerator.generatedOrderedArray(n);// 10w的数据规模
long startTime = System.nanoTime();//单位是纳秒 纳秒-微妙-毫秒-秒 差距都是1000倍
int num = 100;
for (int k=0;k<num;k++)
LinearSearch09.search(data,n);//这里为了验证最差的情况,就传一个找不到的目标元素100000
long endTime = System.nanoTime();
double time = (endTime-startTime)/(1000*1000*1000.0);// 最后1000.0,因为我们希望结果是个浮点数
System.out.println("数据规模n为:"+n+",运行次数:"+ num +"次,运行时间为:" + time + " s.");
}
}
}
创建一个数据规模数组,循环执行,可以看是10W、100W、1000W的运行时间差异确实约为10倍的差距。
ok,到这里,我们的测试方法讲解结束了,后续我们都可以用这样的方式来对不同的算法做测试。