当前位置: 首页 > news >正文

数据结构进阶 unordered系列的效率对比

作者:@小萌新
专栏:@数据结构进阶
作者简介:大二学生 希望能和大家一起进步!
本篇博客简介:对比map set和unordered系列map和set的效率

unordered系列的效率对比

  • map/set与unordered_map/unordered_set的区别
  • map/set与unordered_map/unordered_set的性能测试
    • 插入效率测试
    • 查找效率测试
    • 删除效率测试
    • 测试数为10000
      • debug
      • release
    • 测试数为10000000
      • debug
      • realease
  • 测试结论
  • 测试代码

map/set与unordered_map/unordered_set的区别

map/set与unordered_map/unordered_set虽然它们的接口函数名称近乎一致 但是它们的底层实现却大不相同

容器底层数据结构是否有序实现版本增删查改的效率迭代器类型
unordered_map/unordered_set哈希表/散列表遍历无序C++11O(1)单向迭代器
map/set红黑树遍历有序C++98O(logN)双向迭代器

map/set与unordered_map/unordered_set的性能测试

我们这里分别使用不同的数据量对这两种容器进行增删查 的效率测试

我们使用set和unordered_set来进行测试

首先我们生成N个随机数 将它们插入到一个容器vector里

代码标识如下

	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

这里利用我们之前学过的一个知识点 我们使用const修饰的全局变量N

在这里插入图片描述

插入效率测试

代码表示如下

我们分别使用两个时间标志来记录它们插入的时间

	// 插入 
	set<int> s;
	clock_t begin1 = clock();
	for (auto x : v)
	{
		s.insert(x);
	}
	clock_t end1 = clock();

	unordered_set<int> us;
	clock_t begin2 = clock();
	for (auto x : v)
	{
		us.insert(x);
	}
	clock_t end2 = clock();

查找效率测试

	// 查找
	clock_t begin3 = clock();
	for (auto x : v)
	{
		s.find(x);
	}
	clock_t end3 = clock();

	clock_t begin4 = clock();
	for (auto x : v)
	{
		us.find(x);
	}
	clock_t end4 = clock();

删除效率测试

	// 删除
	clock_t begin5 = clock();
	for (auto x : v)
	{
		s.erase(x);
	}
	clock_t end5 = clock();

	clock_t begin6 = clock();
	for (auto x : v)
	{
		us.erase(x);
	}

测试数为10000

debug

在这里插入图片描述

release

在这里插入图片描述

我们可以发现 在小数据的时候它们之间的效率差别不大 在release版本下都被优化的很好

测试数为10000000

debug

在这里插入图片描述

realease

在这里插入图片描述
我们可以发现在测试数量巨大的时候它们之间的效率就开始出现差别了

unordered系列的效率明显快于set 尤其是查找操作

测试结论

  • 当测试数据较小时 选择map/set容器与unordered_map/unordered_set容器都可以
  • 当测试数据较大时 unordered_map/unordered_set容器的效率明显高于map/set

但是unordered_map/unordered_set容器对比map/set有一个缺点 就是它是无序的

所以说当我们要排序的时候冒着牺牲效率的代价也要选择map/set

测试代码

大家可以自行修改N的值进行测试

#define _CRT_SECURE_NO_WARNINGS 1
#include<time.h>
#include<set>
#include<unordered_set>
#include<iostream>
using namespace std;
const int N = 10000000;



int main()
{
	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}
	// 插入 
	set<int> s;
	clock_t begin1 = clock();
	for (auto x : v)
	{
		s.insert(x);
	}
	clock_t end1 = clock();

	unordered_set<int> us;
	clock_t begin2 = clock();
	for (auto x : v)
	{
		us.insert(x);
	}
	clock_t end2 = clock();

	//分别输出插入set容器和unordered_set容器所用的时间
	cout << "set insert: " << end1 - begin1 << endl;
	cout << "unordered_set insert: " << end2 - begin2 << endl;


	// 查找
	clock_t begin3 = clock();
	for (auto x : v)
	{
		s.find(x);
	}
	clock_t end3 = clock();

	clock_t begin4 = clock();
	for (auto x : v)
	{
		us.find(x);
	}
	clock_t end4 = clock();

	//分别输出在set容器和unordered_set容器中查找这N个数所用的时间
	cout << "set find: " << end3 - begin3 << endl;
	cout << "unordered_set find: " << end4 - begin4 << endl;


	// 删除
	clock_t begin5 = clock();
	for (auto x : v)
	{
		s.erase(x);
	}
	clock_t end5 = clock();

	clock_t begin6 = clock();
	for (auto x : v)
	{
		us.erase(x);
	}
	clock_t end6 = clock();
	//分别输出将这N个数从set容器和unordered_set容器中删除所用的时间
	cout << "set erase: " << end5 - begin5 << endl;
	cout << "unordered_set erase: " << end6 - begin6 << endl;
	return 0;
}

相关文章:

  • VScode远程连接Linux
  • QTreeView ui相关
  • [贪心]376. 摆动序列 53. 最大子序和 122.买卖股票的最佳时机II 55. 跳跃游戏 45. 跳跃游戏II
  • 【SpringBoot3】SpringBoot中实现全局统一异常处理
  • 分支语句(选择结构)——“C”
  • 【寒假每日一题】洛谷 P6421 [COCI2008-2009#2] RESETO
  • aws codesuit 在codebuild和codepipeline中集成jenkins
  • DPU网络开发SDK—DPDK(八)
  • DW 2023年1月Free Excel 第五次打卡 文本函数
  • 第四层:友元与函数成员别样定义
  • SpringCloud(11):Hystrix请求合并
  • SpringBoot的自动配置