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

本文主要是介绍坑爹的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)？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---