随笔-89  评论-944  文章-0  trackbacks-0

我作了双向扩充实现。昨天的方案是:

先判断插入的元素靠前还是靠后,靠哪边就准备往哪边挪旧元素,然后检查那头有没有空,没空换另一头,要是都没空但两头加起来却有空,那就重新调整位置,最后才重新分配空间。

我原以为考虑得好周到,可是实现起来却傻了眼。往末尾插入10万数据,有9万多次发生移动元素,不慢才怪。

 

调整了下,变成:

先判断考前还是靠后,靠哪边就往哪边挪旧元素,如果那头没空,直接重新分配空间,空间按每次*3增长直至足够。

 

这样,push_back 的性能与 std::vector 以及 std::deque 的粗略比较如下(图中的单位写错了,全是秒):

image

image

image

image

 

insert(begin(), i) 比较:

image

image

(vector 参与这项比较果然是不公平的,呵呵)

image

image

 

insert 到 begin + size() / 2 处:

image

image

 

resize 至固定大小,然后用 iterator 遍历赋值:

image

image

image

image

(今天回家了。以上测试都在家里的机器上做的,配置: AMD SP2500+ 1.4GHz,512MB RAM。)

 

这样的结果还算满意的。不知道 vector 为什么能保持 push_back 如此高效~

还有个挺奇怪的现象,使用 deque 的时候,如果数据量到百万,临退出前有好长一段时间要等待,难道是 deque 在做某些析构动作?

再呢。。貌似 deque 的 push_front 并没有 vector 的 push_back 神么、、

 

嗯……我的本意不是为了着重性能,而是尝试些有着那么一套接口的东西出来,同时也给自己用。现在来比性能只是为了论证一下实用程度如何,如此而已。

具体实现代码就不贴了,基本接口和上上篇里没多少变化。等以后这方面的东西做完了再一起拿出来。

posted on 2009-10-01 20:17 溪流 阅读(230) 评论(1)  编辑 收藏 引用 所属分类: C++

评论:
# re: 昨天傻掉了,是策略没搞好 2009-10-12 18:38 | 陈梓瀚(vczh)
你可以看看Delphi的TObjectList的实现。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理