STL locale 使用小结
fstream 文件 IO 点滴

从 std::list 中 size() 的时间复杂度引出的讨论...

輝夜(tadvent) posted @ 2009年5月10日 05:49 in C/C++ with tags STL gcc list VC c++ , 9088 阅读

很奇怪的,或者说是一个不应成为问题的问题...
std::list 的 size() 方法时间复杂度是多少?第一感觉应该是 O(1) 没错吧,多一个变量用于储存链表长度应该是很轻易的事情。于是有了下面这段代码:

#include<iostream>
#include<list>
#include<ctime>
using namespace std;

int main(){
    time_t start, finish;
    int num = 0;
    list<int> coll;

    start = clock();
    for(int i=0;i<10000;++i){
        coll.push_back(i);
        num += coll.size();
    }
    finish = clock();
    cout<<finish - start<<"   num:"<<num<<endl;

    coll.clear();
    start = clock();
    for(int i=0;i<10000;++i){
        coll.push_back(i);
    }
    finish = clock();
    cout<<finish - start<<endl;
    return 0;
}

对两个循环分别计时比较。前一个循环只比后一个多了一句 num += coll.size(); 为了使编译器确实生成 list::size() 的代码。
在 MinGW 5.1.4 中 (GCC 3.4.5) 编译结果运行如下:

450   num:50005000
10

可以看到,前一个循环居然比后一个多花了几乎 45 倍的时间...当我把循环次数从 10000 加到 100000 时程序半天没出结果...

由此有理由猜测 std::list 的 size() 方法难道是 O(N) 的?果然,在头文件中发现了这一段:

size_type
size() const
{ return std::distance(begin(), end()); }

 

直接调用 <algorithm> 算法库函数 distance() 计算元素个数……怪不得这么慢。然后又用 VS2008 (VC9.0)编译,结果如下:

30   num:50005000
60

奇怪的是前一个循环居然比后一个还快...不过至少知道 VS2008 (VC9.0)里的 size() 应该是 O(1) 的。同样查看了一下代码,如下:

size_type size() const
    {   // return length of sequence
    return (_Mysize);
    }

_Mysize 是一个 size_type 类型的变量。疑问解决。不过又有了新问题:

--------------- 咱 -- 是 -- 分 -- 隔 -- 线 ------------------

为什么 GCC 里要把 list::size() 的复杂度搞成 O(N)?

一通搜索后终于看到有这样的讨论:关于 list::splice() 函数。

list 是链表结构,它的优势就在于可以 O(1) 的时间复杂度任意插入删除甚至拼接 list 片段(删除时可能不是,因为要释放内存),list::splice() 是一个很强大的功能,它可在任意位置拼接两个 list,这正是 list 的优势。如果我们在类内部以一个变量储存 list 的长度,那么 splice() 之后新 list 的长度该如何确定?这是一个很严峻的问题,如果要在拼接操作时计算拼接部分的长度,那么将把 O(1) 的时间变成 O(N),这么一来 list 相对 vector 的优势就消失殆尽。

面对这个问题,GCC 和 VC 的 STL 库作者们做了不同的选择。GCC 选择舍弃在 list 内部保存元素数量,而在 size() 时直接从头数到尾,这便出现了开头看到的 O(N) 时间才算出 size();相反,VC 中有了变量 _Mysize ,无论在 insert() erase() splice() 或是 push() pop() 时都需要对其做相应修改。在上面的两个试验中已经看出同样是 10000 个 push_back() 操作,VC 花的时间比较长,不过也仅仅是一个 inc 指令,差别很小就是了。上面几种会改变 list 内容的操作中,大部分对元素数量的影响只是 +1 或 -1,只有 splice() 需要计算拼接部分元素个数,这个差别就大了,咱还是继续用实验证明吧:

#include<iostream>
#include<list>
#include<ctime>
using namespace std;

int main(){
    time_t start,finish;
    list<int> col;
    col.push_back(1);
    col.push_back(10000);

    list<int> col2;
    start = clock();
    for(int i=2;i<10000;++i)
        col2.push_back(i);
    finish = clock();
    cout<<finish - start<<endl;

    int num = 0;
    start = clock();
    for(int i=0;i<10000;++i){
        col.splice(++col.begin(),col2,++col2.begin(),--col2.end());
        num += *(++col.begin());
        col2.splice(++col2.begin(),col,++col.begin(),--col.end());
        num += *(++col2.begin());
    }
    finish = clock();
    cout<<finish - start<<"   num:"<<num<<endl;
    return 0;
}

首先是 MinGW (GCC 3.4.5) 的结果:

10
0   num:60000

可以看到 10000 次 push 是 10,相对的 20000 次 splice() 几乎没花时间 = =

然后是 VS2008 (VC9.0):

20
2714   num:60000

差别非常明显,花了2秒多才完成。当我把循环次数改成 100000 后 GCC 仍是眨眼间的事,VC 却长时间运行无结果……

怎么说呢,GCC 显然是追求效率至上,尽量体现出 list 的优势所在,不过我觉得这么一来倒不如干脆不提供 list 的 size() 方法,有需求的程序员可以自己维护一个变量记录长度,以免误认为 size() 是 O(1) 的而犯下严重错误。相对的 VC 强调功能性和整体效率,可能在实际中需要对链表一段内容做 splice() 操作的机会远远小于求 size() 的操作,所以舍弃前者而保留后者,不过要维护 _Mysize 其他相关函数中也增加了开销。一个见仁见智的问题,我觉得还是 GCC 的选择比较好,list 的优势应该保留,但能在 size() 函数处给个 warning 什么的就好了。

我想还有一个选择是这样:在 list 内部用一个 bool 变量指示当前内部 size 值是有效还是无效。在通常操作时 bool 保持 true,这样在 size() 时直接返回原值即可;在 splice() 后将此 bool 值置为 false 并不计算长度,直到最后又有需要 size() 时发现 bool 是 false 则从头再来一遍 distance() 并再将 bool 置为 true。暂时只想出这么一个算是折中的方法,基本上都能保持两边 O(1) 的效率,但相应其他各关于元素数量的函数内部都要多一个判断当前 size 值是有效还是无效并选择是否改变其值。反正总是不能非常完美

嘛...本来只是发现 size() 的效率问题,没想到却扯出这么一桩事出来...也算长知识了吧

unblocked games 66 7 说:
2022年8月20日 03:00

Play Bartender Perfect Mix Game. We Unblocked it For You to Play at School. We at Unblocked Games 66 77 99 Unblocks All Games Like Bartender Perfect 2021. Unblocked Games GOGO is one of the game sites that are unblocked games at school that I secretly created. unblocked games for school, unblocked games 66 77 unblocked games 66,unblocked games happy wheels,unblocked games google sites,unblocked games 77,unblocked games 99.

Alyssa 说:
2023年1月04日 21:47

Time complexity of size() in std::list is dependent on the size of the list. If the list is coronavirus vaccine small, then the time complexity of size() is constant. However, if the list is large, the time complexity of size() is linear.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter