正文 

当前位置： 首页 > java > java教程

setvector与list的构造与排序的耗时测试

author author     2022-10-16     779

关键词：

测试目标

测试在成员个数不断递增的情况下，set、vector与list的构造与排序的耗时变化，找出set耗时连续超过其他容器耗时的成员个数


测试方式

  • set使用直接插入

  • vector使用assign构造并使用全局sort排序

  • list使用assign构造与成员sort的排序之间

  • 比较的是耗时时间大小，对耗时的具体值不关心，因为不同的机器配置不一样


测试结论

由于设定的连续超过次数不同，得到的成员个数值也不同，并且随着连续超过上限的增加而增加，因此现在得到的成员个数值并不准确，如：

在连续超过上限为10时，成员个数最大在700左右

在连续超过上限为20时，成员个数最大在2000左右

但有一点可以肯定：set的边插入边排序效率，没有vector与list的赋值或排序高，如果有海量数据排序的情况，用vector或list的赋值后排序的性能相对于set比较好。


测试代码

// 主逻辑 main.cpp
#include "TimeConsume.h"
#include "Random.h"
#include <unistd.h>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdint>
#include <string>
using namespace std;

// set耗时是否连续超出其他容器
bool is_continue_beyond(uint64_t vector_time, uint64_t list_time, uint64_t set_time, uint64_t beyond_num) {
    static uint64_t s_beyond_num = beyond_num; 
    if (set_time > list_time && set_time > vector_time) {
	--s_beyond_num;
    } else {
	s_beyond_num = beyond_num;
    }

    return s_beyond_num == 0;
}

int main(int argc, char** argv) {

    uint64_t member_count_num = 0;
    uint64_t member_add_num = 0;
    uint64_t beyond_num = 0;
    if (argc != 4) {
	cout << "input: " << argv[0] << " member_start_num member_add_num beyond_num" << endl;
	return -1;
    } else {
	member_count_num = strtoull(argv[1], NULL, 10);
	member_add_num = strtoull(argv[2], NULL, 10);
	beyond_num = strtoull(argv[3], NULL, 10);
    }

    uint64_t vector_time = 0;
    uint64_t list_time   = 0;
    uint64_t set_time    = 0;

    while (!is_continue_beyond(vector_time, list_time, set_time, beyond_num)) {
	vector<uint64_t > input_random_num; // 使用一样的随机数据
	Random random;
	random.SetRandomNum<vector<uint64_t> >(member_count_num, input_random_num);

	// 构造排序函数
	vector<uint64_t> monitor_vector; // 外部定义容器，防止构造析构带来的时间计算
	auto vector_sort = [&]() {
	    monitor_vector.assign(input_random_num.begin(), input_random_num.end());
	    sort(monitor_vector.begin(), monitor_vector.end());
	};

	list<uint64_t> monitor_list;
	auto list_sort = [&]() {
	    monitor_list.assign(input_random_num.begin(), input_random_num.end());
	    monitor_list.sort();
	};

	set<uint64_t> monitor_set;
	auto set_sort = [&](){
	    monitor_set.insert(input_random_num.begin(), input_random_num.end());
	};

	// 统计排序时间
        TimeConsume vector_time_consume(vector_sort);
        TimeConsume list_time_consume(list_sort);
        TimeConsume set_time_consume(set_sort);

	vector_time = vector_time_consume.GetFnTime();
	list_time = list_time_consume.GetFnTime();
	set_time = set_time_consume.GetFnTime();

	cout << "count:" << member_count_num<< "	" << "vector_time:" << vector_time << "	" << "list_time:" << list_time << "	" << "set_time:" << set_time << endl;
	sleep(0.5);
	member_count_num += member_add_num;
    }
    return 0;
}
/*
TimeConsume.h
用于获得程序运行的时间消耗，支持函数对象（C++11新标准）
获得的耗时为微秒级
*/
#ifndef TIME_CONSUME_H
#define TIME_CONSUME_H

#include <sys/time.h>
#include <ctime>
#include <functional>
using std::function;

#define SEC_RATIO_MSEC 1000
#define SEC_RATIO_USEC (1000*SEC_RATIO_MSEC)

class TimeConsume {
public:
    TimeConsume(const function<void()> &monitor_fn = [](){;})
	: m_monitor_fn(monitor_fn) {
	    Clear();
    }

    ~TimeConsume()
    {;}

    // 设置耗时监控的函数对象
    inline function<void()> SetMonitorFn(const function<void()> &monitor_fn()) {
    	auto old_monitor_fn = m_monitor_fn;
    	m_monitor_fn = monitor_fn;
    	return old_monitor_fn;
    }

    // 记录开始监控的时间点
    inline void Start() {
	    gettimeofday(&m_start, NULL);
    }
    
    // 记录结束监控的时间点
    inline void End() {
	    gettimeofday(&m_end, NULL);
    }

    // 依据开始和结束监控的时间点，得到微秒级耗时
    inline uint64_t GetIntervalTime() {
    	if ((m_end.tv_sec > m_start.tv_sec)
    	    || (m_end.tv_sec == m_start.tv_sec && m_end.tv_usec >= m_start.tv_usec)) {
    	    return (m_end.tv_sec - m_start.tv_sec)*SEC_RATIO_USEC + (m_end.tv_usec - m_start.tv_usec); 
    	} else {
    	    return 0;
    	}
    }

    // 获得监控函数对象的微秒级运行耗时
    inline uint64_t GetFnTime() {
        Clear();
    	Start();
    	m_monitor_fn();
    	End();
    	return GetIntervalTime();
    }

protected:
    // 格式化内部相关值
    inline void Clear() {
    	m_start.tv_sec = 0;
    	m_start.tv_usec = 0;
    	m_end.tv_sec = 0;
    	m_end.tv_usec = 0;
    }

private:
    struct timeval m_start;
    struct timeval m_end;
    function<void()> m_monitor_fn;
};
#endif
/*
Random.h
可以向STL 容器里填充指定个数的随机值，取值范围在[0-RAND_MAX]，RAND_MAX为最大值的整数常量表达式。此值依赖实现。保证此值至少为32767
*/
#ifndef RANDOM_H
#define RANDOM_H

#include <ctime>
#include <iterator>
using std::inserter;

class Random {
public:
    Random() {
	srand(time(NULL));
    }

    ~Random()
    {;}

    template <typename  ContainerT>
    inline void SetRandomNum(uint64_t count, ContainerT &container) {
	auto iter = inserter(container, container.end());
	for (uint64_t i = 0; i < count; ++i) {
	    iter = rand();
	}
    }
};

如果对测试有什么疑问或建议，欢迎大家来讨论

arrays排序算法(代码片段)

Arrays排序算法importjava.util.Arrays;排序算法-数据结构Arrays.sort耗时100000个数升序排列耗时测试:耗时:14、耗时:10、耗时:14、耗时:11、耗时:13、耗时:10、耗时:11、耗时:12、耗时:17、耗时:15从时间上查看排序算法-数据结构，与快速排... 查看详情

c++中的stl（超详细的操作）(代码片段)

vectorvector构造函数vector赋值操作vector容器和大小vector插入和删除vector数据存取vector互换容器vector预留空间stringstring构造函数string赋值操作string字符串的拼接string查找和替换rfind从右向左查，find从左向右查string字符串比较主要... 查看详情

c#list排序各种用法与比较

...我们建一个People的实体，有name、age、sex的属性，我们要排序的字段是年龄age新建一个实体类publicclassPeople{publicstringname{get;set;}publicintage{get;set;}publicstringsex{get;set;}}新建list的数据List<People&g 查看详情

接口测试框架实战|requests与接口请求构造

Requests是一个优雅而简单的PythonHTTP库，其实Python内置了用于访问网络的资源模块，比如urllib，但是它远不如Requests简单优雅，而且缺少了许多实用功能。所以，更推荐掌握Requests接口测试实战技能，这也是互联网大厂流行的接口... 查看详情

软件测试与评估

...对比测试百词斩和扇贝单词测试进度表项目内容说明预估耗时（分钟）实际耗时（分钟）Planning计划 5 5·Estimate· 估计这个任务需要多少时间 5 5TestingDesign测试设计 180 180·Analysis· 需求和测试需求分... 查看详情

如何构造条件查询以将指定的字符串与 List<String> 匹配

】如何构造条件查询以将指定的字符串与List<String>匹配【英文标题】：HowtoconstructcriteriaQuerytomatchaspecifiedStringwithList<String>【发布时间】：2021-09-0702:57:46【问题描述】：publicclassMyEntityprivateLongid;@Convert(converter=MyEntity.StringLi... 查看详情

vs2010启动调试运行和开始执行的区别与耗时

参考技术ACtrlF5测试运行后不自动推出控制台，直接按F5会自动退出去，用贯6.0的人稍微有点不习惯。至少要看看执行结果吧。 查看详情

1035插入与归并测试点256

易错点测试点2：插入排序的判断，思路是否正确，可检验测试点：3132132，如果输出：插入排序，123，即正确测试点5、6：归并排序中，若归并的每组数的数量为n，若最后一组数的数量不足n，此时最后一组数也要记得进行排序。... 查看详情

软件质量与测试第4周小组作业：wordcount优化(代码片段)

...责词频统计模块与其他模块 组员：　　屈佳烨：负责排序模块　　苑子尚：负责输出模块　　李一凡：负责输入模块  PSP表格 PSP2.1PSP阶段预估耗时（分钟）实际耗时（分钟）Planning计划  ·Estim 查看详情

如何使用特定的托管对象来构造排序描述符？

】如何使用特定的托管对象来构造排序描述符？【英文标题】：Howtouseaspecificmanagedobjecttoconstructasortdescriptor?【发布时间】：2011-11-1716:03:34【问题描述】：实体B（书籍）与实体D（描述）具有一对多的关系。这个想法是一本书对不... 查看详情

c#datatable与list读写性能测试(代码片段)

最近看见同事在写需要非常多次遍历的算法，发现DataTable的读取速度竟然吊打List于是我做了个3千万条数据的读写性能测试usingSystem;usingSystem.Collections.Generic;usingSystem.Data;usingSystem.Diagnostics;usingSystem.Runtime.InteropServices;namespaceConsole 查看详情

接口测试框架实战之requests与接口请求构造(代码片段)

Requests简介Requests是一个优雅而简单的PythonHTTP库，其实Python内置了用于访问网络的资源模块，比如urllib，但是它远不如Requests简单优雅，而且缺少了许多实用功能。所以，更推荐掌握Requests接口测试实战技能ÿ... 查看详情

elasticsearch慢查询故障诊断

...逻辑。breakdown里的主要指标及lucene中的实现：build_scorer:构造一个scorer的耗时。scorer主要用于对matching的doc进行打分和排序。build_scorer内部构造了迭代器，这个迭代器可以遍历所有matcheddocument，构造迭 查看详情

第六周小组作业：软件测试与评估

...择的两款产品是毕博平台和网易云课堂项目内容说明预估耗时（分钟）实际耗时（分钟）Planning计划 30 30·Estimate· 估计这个任务需要多少时间30 30TestingDesign测试设计90110 ·Analysis· 需求和测试需求分析3030&nbs... 查看详情

测试与优化(代码片段)

...择部分单元测试代码发布在博客中，并说明测试的函数，构造测试数据的思路classMathExam6317Test@TestvoidtestGradeOne()MathExam6317.gradeOne(5);assertEquals(5,MathExam6317.str.length);@Tes 查看详情

数据结构与算法学习——二叉排序树

数据结构与算法学习——二叉排序树目录博主介绍博主介绍简介二叉排序树的生成与节点插入1、生成二叉树的前中后序遍历1、递归实现1.2、非递归实现二叉排序树节点的删除1、编写用于搜索待删除节点和待删除节点父节点的方... 查看详情

将排序列表与java中的迭代器合并

我使用的方法采用两个排序列表，并按排序顺序返回包含两个原始列表中所有元素的单个列表。例如，如果原始列表是（1,4,5）和（2,3,6），则结果列表将是（1,2,3,4,5,6）。有什么我想念的吗？publicstatic<EextendsComparable<E>>L... 查看详情

数据结构与算法学习——二叉排序树

数据结构与算法学习——二叉排序树目录博主介绍博主介绍简介二叉排序树的生成与节点插入1、生成二叉树的前中后序遍历1、递归实现1.2、非递归实现二叉排序树节点的删除1、编写用于搜索待删除节点和待删除节点父节点的方... 查看详情