【算法与数据结构】6 学会对算法进行性能测试

简介: 【算法与数据结构】6 学会对算法进行性能测试

一、前情回顾

👉传送门:1 详解线性查找法

👉传送门:2 线性查找的优化

👉传送门:3 线性查找的测试

👉传送门:4 循环不变量与复杂度分析

👉传送门:5 常见的时间复杂度

二、算法性能测试

Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};


我们对于之前的线性查找的算法,只是使用了一个含有8个元素的data数组进行测试,这个数组规模太小,在现代计算机上,对于O ( n ) O(n)O(n)这个级别的复杂度,需要一定规模的数据才能看到相应的性能


1.生成测试用例

//作用:为我们生成一个数组,
public class ArrayGenerator {
    // 用户无需生成一个ArrayGenerator的对象,因此将构造函数设置为私有
    private ArrayGenerator(){}
    //使用静态方法
    //生成一个数组,数组中的元素是顺序存放
    public static Integer[] generateOrderedArray(int n){
        //对线性查找进行测试,所以生成的数组中的元素就是[0...n-1]
        //其中n的大小是变化的,是用户进行输入指定
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        return arr;
    }
}
 return arr;
    }
}


新建一个ArrayGenerator类,专门用于生成数组

数组生成中的方法采用静态方法,且用户无需生成一个ArrayGenerator的对象,因此将构造函数设置为私有

此处主要用于测试前面的线性查找算法的性能,所以生成的数组中的元素顺序存放,范围[ 0... n − 1 ] [0...n-1][0...n−1],其中n是由用户进行指定的

2.使用测试用例

public class LinearSearchGenerator {
    private LinearSearchGenerator(){}
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target)
                return i;    //如果找到目标,返回对应的索引值
        }
        return -1;          //如果没有找到目标,返回-1
    }
    public static void main(String[] args) {
        //准备用于查找的数组,数组中有100000个元素
        Integer[] data = ArrayGenerator.generateOrderedArray(100000);
        int res = LinearSearchGenerator.search(data, 100000);
        System.out.println(res); //输出res
    }
}


data数组直接使用ArrayGenerator.generateOrderedArray()生成

首次传入的参数为100000,并且将查找的target值设为100000

很明显,在一个元素个数只有100000的数组中,且数组的元素是顺序存放的[0…100000),查询是否有100000这个数的结果一定是-1

2.1 检验测试用例的用时

为了检验出对于这次查询,这次的函数调用具体消耗了多少时间,我们可以使用Java为我们提供的nanoTime()方法做一个计时

public class LinearSearchGenerator {
    private LinearSearchGenerator(){}
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target)
                return i;    //如果找到目标,返回对应的索引值
        }
        return -1;          //如果没有找到目标,返回-1
    }
    public static void main(String[] args) {
  int n = 100000;
        //准备用于查找的数组,数组中有100000个元素
        Integer[] data = ArrayGenerator.generateOrderedArray(n);
        //nanoTime()方法返回的其实是一个时间戳,
        // 是一个长整型,当前用纳秒计算的时间戳
        long startTime = System.nanoTime();
        int res = LinearSearchGenerator.search(data, n);
        System.out.println(res); //输出res
        long endTime = System.nanoTime();
        //endTime - startTime的值就是两个时间戳之间的线性查找所用的时间,单位是纳秒
        //纳秒与秒之间是10^9
        //对于结果可以是一个浮点数,所以除以1000000000.0
        double time = (endTime - startTime) / 1000000000.0;
        System.out.println(time + " s");
    }
}


nanoTime()方法返回的其实是一个时间戳,用纳秒计算

在线性查找算法前使用一次,在线性查找算法结束后使用一次

endTime - startTime的值就是两个时间戳之间的线性查找所用的时间,单位是纳秒

结果如下:

消耗时间也与硬件有关,所以时间不一定相同

2.1 不同规模的测试用例的用时比较

public class LinearSearchGenerator {
    private LinearSearchGenerator() {
    }
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target)
                return i;    //如果找到目标,返回对应的索引值
        }
        return -1;          //如果没有找到目标,返回-1
    }
    public static void main(String[] args) {
        //不同规模的数据
        int[] dataSize = {1000000, 10000000};
        for (int n : dataSize) {
            //准备用于查找的数组
            Integer[] data = ArrayGenerator.generateOrderedArray(n);
            //nanoTime()方法返回的其实是一个时间戳,
            // 是一个长整型,当前用纳秒计算的话时间戳
            long startTime = System.nanoTime();
            //对于每个规模的数据,可以通过增加查找次数来达到扩大时间规模的目的
            /*因为直接进行查找特别大的规模的数据,比如1亿个数据,
              尤其我们需要的是连续空间,在一般的计算机上可能也会费一点劲,
              我们通过多做几回,对100万个数据进行100次查找,时间也会相对稳定一些
             */
            for (int k = 0; k < 100; k++) {
                LinearSearchGenerator.search(data, n);
            }
            long endTime = System.nanoTime();
            //endTime - startTime的值就是两个时间戳之间的线性查找所用的时间,单位是纳秒
            //纳秒与秒之间是10^9
            //对于结果可以是一个浮点数,所以除以1000000000.0
            double time = (endTime - startTime) / 1000000000.0;
            System.out.println("n = " + n + ", 100runs: " + time + " s");
        }
    }
}


直接将不同规模的数据存放在数组中

int[] dataSize = {1000000, 10000000};

对于每个规模的数据,可以通过增加查找次数来达到扩大时间规模的目的

因为直接进行查找特别大的规模的数据,比如1亿个数据,尤其我们需要的是连续空间,在一般的计算机上可能也会费一点劲,我们通过多做几回,对100万个数据进行100次查找,时间也会相对稳定一些

并且多次测量就有多组数据,可以进行统计分析,计算平均值、标准差等

for (int k = 0; k < 100; k++) {
  LinearSearchGenerator.search(data, n);
}


对于1000000和10000000这两个规模的数据,分别执行查找100次,最后的结果如下:

消耗时间也与硬件有关,所以每次时间都不相同

从运行结果中,可以看到,对于100万级别的数据,进行100次的查询,大概是0.13s的时间,对于1000万级别,大概是0.7s的时间

0.7大概是0.13的5倍(其实有时候是6倍以上甚至10倍,这与计算机的性能有关),而我们第一次的数据规模是第二次的10倍

从侧面证明了线性查找法的时间复杂度是O ( n ) O(n)O(n)级别的,时间性能和数据规模之间是线性关系

时间复杂度描述的是随着n的增长相应的算法的性能增长的趋势其实就是这个意思


相关实践学习
通过性能测试PTS对云服务器ECS进行规格选择与性能压测
本文为您介绍如何利用性能测试PTS对云服务器ECS进行规格选择与性能压测。
目录
打赏
0
0
0
0
211
分享
相关文章
文本聚类效果差?5种主流算法性能测试帮你找到最佳方案
本文探讨了自然语言处理中句子嵌入的聚类技术,使用Billingsmoore数据集(925个英语句子)进行实验。通过生成句子嵌入向量并可视化分析,对比了K-Means、DBSCAN、HDBSCAN、凝聚型层次聚类和谱聚类等算法的表现。结果表明,K-Means适合已知聚类数量的场景,DBSCAN和HDBSCAN适用于未知聚类数量且存在异常值的情况,而谱聚类在句子嵌入领域表现不佳。最终建议根据数据特征和计算资源选择合适的算法以实现高质量聚类。
47 0
文本聚类效果差?5种主流算法性能测试帮你找到最佳方案
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
98 9
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
116 3
 算法系列之数据结构-Huffman树
|
4月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
105 22
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
139 29
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
195 25
|
8月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
182 58
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
21 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问