坑爹的list容器size方法--为了splice居然把复杂度设计为O(N)?

2023-10-21 02:58

本文主要是介绍坑爹的list容器size方法--为了splice居然把复杂度设计为O(N)?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 最近在做一个性能要求较高的项目,有个服务器需要处理每秒2万个udp包,每个包内有40个元素(当然这是高峰期)。服务器需要一个链表,算法中有个逻辑要把每个元素添加到链表末尾(只是这个元素对象的指针,不存在对象复制的问题),再从链表中把这些元素取出(另一个时间点)。就是一个单线程在做这件事。


既然逻辑这么简单,我自然选用了C++的标准STL容器List(Linux GNU,sgi的实现),想来如此简单的事情,不过是一次末尾插入,一次头部取出而已,就用STL的List容器吧。没有想到这是痛苦的开始。我预想中每秒处理80万元素应该是很轻松写意的,没想到每秒一千个包时服务器就顶不住了,处理算法的线程占用CPU达到百分之百,大量的包得不到及时处理而超时。由于算法较为复杂,定位这问题耗了不少时间,终于感觉到LIST容器似乎有严重性能问题。


于是干脆自己写了个简单的链表,替代了STL的容器后性能有了极大的提升。为此我特意写了个简单的程序,大致模仿我算法中的场景,程序流程如下:

每3秒中向链表中插入N个元素(指针),再把这N个元素从链表中取出释放。之后查看耗时t,如果t小于3秒,就sleep(3-t)秒,并打印出睡眠的时间。

在我的测试机上,出现了差异很大的测试结果,大约每3秒测试2万个元素时,使用STL LIST的压力程序导致CPU已经达到70%了,而使用自己写的简单链表几乎没有感觉。直到每3秒测试2000万个元素时,才导致CPU占用80%结果有一千倍的差距!这里没有对象的复制,我插入链表的都只是指针而已!

(下面附测试程序,这里只是对比两种list的性能,机器的参数并不重要。请大家注意71行代码

#include <list>
#include <sys/time.h>
#include <iostream>using namespace std;//待测试的对象,链表中的每个元素就是对象A的指针
class A {};//每3秒钟插入链表末尾/从链表首部取出的元素个数
int testPressureNum = 40000;//测试的STL链表
list<A*> testList;//自己写的链表
typedef struct
{A*	p;void* 	prev;void*	next;
} SelfListElement;SelfListElement*  myListHead;
SelfListElement*  myListTail;
int	myListSize;//向自己写的链表首部添加元素
bool add(A* packet)
{SelfListElement* ele = new SelfListElement;ele->p = packet;myListSize++;if (myListHead == NULL){myListHead = myListTail = ele;ele->prev = NULL;ele->next = NULL;return true;}ele->next = myListHead;myListHead->prev = ele;ele->prev = NULL;myListHead = ele;return true;
}
// 从自己写的链表尾部取出元素
SelfListElement* get()
{if (myListTail == NULL)return NULL;myListSize--;SelfListElement* p = myListTail;if (myListTail->prev == NULL){myListHead = myListTail = NULL;}else{myListTail = (SelfListElement*)myListTail->prev;myListTail->next = NULL;}return p;
}//从STL链表中取出元素并删除
void testDelete1()
{while (testList.size() > 0)//这行语句有严重性能问题,size的复杂度不是常量级,而是O(N),请注意!就是这里跳坑里去了{A* p = testList.back();testList.pop_back();delete p;p = NULL;}
}
//从简单链表中取出元素并删除
void testDelete2()
{do {SelfListElement* packet = myListTail;if (packet == NULL)break;packet = get();delete packet->p;delete packet;packet = NULL;} while (true);
}
//向Stl链表中添加元素
void testAdd1()
{for (int i = 0; i < testPressureNum; i++){A* p = new A();testList.push_front(p);}
}
//向简单链表中添加元素
void testAdd2()
{for (int i = 0; i < testPressureNum; i++){A* p = new A();add(p);}
}void printUsage(int argc, char**argv)
{cout<<"usage: "<<argv[0]<<" [1|2] [oneRoundPressueNum]"<<endl<<"1 means STL, 2 means simple list\noneRoundPressueNum means in 3 seconds how many elements add/del in list"<<endl;	
}int main(int argc, char** argv)
{//为方便测试可使用2个参数if (argc < 2){printUsage(argc, argv);return -1;}int type = atoi(argv[1]);if (type != 1 && type != 2){printUsage(argc, argv);return -2;}if (argc >= 2)testPressureNum = atoi(argv[2]);cout<<"every 3 seconds add/del element number is "<<testPressureNum<<endl;struct timeval time1, time2;gettimeofday(&time1, NULL);while (true){gettimeofday(&time1, NULL);if (type == 1){testAdd1();cout<<"stl list has "<<testList.size()<<" elements"<<endl;}else{testAdd2();cout<<"my list has "<<myListSize<<" elements"<<endl;}//每3秒一个周期gettimeofday(&time2, NULL);unsigned long interval = 1000000*(time2.tv_sec-time1.tv_sec)+time2.tv_usec-time1.tv_usec;if (interval < 3000000){cout<<"after add sleep "<<3000000-interval<<" usec"<<endl;usleep(3000000-interval);}elsecout<<"add cost time too much"<<interval<<endl;gettimeofday(&time1, NULL);if (type == 1){testDelete1();cout<<"stl list has "<<testList.size()<<" elements"<<endl;}else{testDelete2();cout<<"my list has "<<myListSize<<" elements"<<endl;}//每3秒一个周期gettimeofday(&time2, NULL);interval = 1000000*(time2.tv_sec-time1.tv_sec)+time2.tv_usec-time1.tv_usec;if (interval < 3000000){cout<<"after delete sleep "<<3000000-interval<<" usec"<<endl;usleep(3000000-interval);}elsecout<<"delete cost time too much"<<interval<<endl;}return 0;}

一千倍的性能差距太夸张了。究竟是什么原因导致STL性能这么差呢?之前对在一些性能要求高的场景下我没怎么用过STL容器,对它还不够熟悉。这篇博客发出后, 陈硕帮忙指出原来是第71行的size()方法出了问题!   将size()方法改为 empty()方法后,list性能有了大幅度提高,当然与上面自己写的链表相比还有差距,大概自写链表性能比STL的list还要高出70%左右!
 

我很好奇究竟size()方法干了些什么?看看它的实现!(STL的代码我下的是sgi 3.3版本)

  size_type size() const {size_type __result = 0;distance(begin(), end(), __result);return __result;}

原来这个size()方法并不像自己写的链表那样,用一个变量来存储着链表的长度,而是去调用了distance方法来获取长度。那么这个distance方法又做了些什么呢?

template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n)
{__STL_REQUIRES(_InputIterator, _InputIterator);__distance(__first, __last, __n, iterator_category(__first));
}

又封了一层__distance,看看它又做了什么?

template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{typename iterator_traits<_InputIterator>::difference_type __n = 0;while (__first != __last) {++__first; ++__n;}return __n;
}

原来是遍历!为什么获得链表长度必须要遍历全部的链表元素才能获得,而不是用一个变量来表示呢?sgi设计list的思路何以如此与众不同呢(话说微软的STL实现就没有这个SIZE方法的效率问题)?

看看作者自己的解释:http://home.roadrunner.com/~hinnant/On_list_size.html

开篇点题,原来作者是为了

splice(iterator position, list& x, iterator first, iterator last);
方法所取的折衷,为了它的实现而把size方法设计成了O(N)。
splice方法就是为了把链表A中的一些元素直接串联到链表B中,如果size()设计为O(1)复杂度,那么做splice时就需要遍历first和last间的长度(然后把链表A保存的链表长度减去first和last(待移动的元素)之间的长度)!于是作者考虑到size方法设计为O(N),就无需在splice方法执行时做遍历了!
看看splice的实现:
  void splice(iterator __position, list&, iterator __first, iterator __last) {if (__first != __last) this->transfer(__position, __first, __last);}

再看看transfer干了些什么:
  void transfer(iterator __position, iterator __first, iterator __last) {if (__position != __last) {// Remove [first, last) from its old position.__last._M_node->_M_prev->_M_next     = __position._M_node;__first._M_node->_M_prev->_M_next    = __last._M_node;__position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position._List_node_base* __tmp      = __position._M_node->_M_prev;__position._M_node->_M_prev = __last._M_node->_M_prev;__last._M_node->_M_prev     = __first._M_node->_M_prev; __first._M_node->_M_prev    = __tmp;}}

作者确实是考虑splice执行时,不用再做遍历,而是仅仅移动几个指针就可以了,因此牺牲了size的效率!

怎么评价这种设计呢?作者的出发点是好的,但是,毕竟绝大多数程序员都会潜意识认为 size方法的复杂度是常量级的,同时size方法也是最常用的!这个确实是作者在给我们挖坑哈!

这个例子真是告诉我们,必须谨慎使用第三方软件,特别是对它有较高的要求时,务必对将要使用它的所有方法都有足够的了解,不是满足于它能做什么,还必须要知道它怎么做到的,否则,还是老老实实用自己熟悉的工具吧。




这篇关于坑爹的list容器size方法--为了splice居然把复杂度设计为O(N)?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/251468

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

【北交大信息所AI-Max2】使用方法

BJTU信息所集群AI_MAX2使用方法 使用的前提是预约到相应的算力卡,拥有登录权限的账号密码,一般为导师组共用一个。 有浏览器、ssh工具就可以。 1.新建集群Terminal 浏览器登陆10.126.62.75 (如果是1集群把75改成66) 交互式开发 执行器选Terminal 密码随便设一个(需记住) 工作空间:私有数据、全部文件 加速器选GeForce_RTX_2080_Ti

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域,图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能,成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限,比如只有一台高性能电脑时,如何高效地让七人同时流畅地进行设计工作,便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器(CPU):选择多核、高线程的处理器,例如Intel的至强系列或AMD的Ry

K8S(Kubernetes)开源的容器编排平台安装步骤详解

K8S(Kubernetes)是一个开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述: 安装步骤: 安装Docker:K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master:在集群中选择一台主机作为Master节点,安装K8S的控制平面组件,如AP

Spring框架5 - 容器的扩展功能 (ApplicationContext)

private static ApplicationContext applicationContext;static {applicationContext = new ClassPathXmlApplicationContext("bean.xml");} BeanFactory的功能扩展类ApplicationContext进行深度的分析。ApplicationConext与 BeanF

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机