算法复杂度不等于性能,list的性能陷阱

在学习数据结构和算法的时候,我们一般都会通过分析算法复杂度,来对某个问题选择合适的数据结构和算法。

下面就是一个经典问题:

我们需要一个容器,容器中存放的是int数据。容器中的元素是有序的,对容器有一个插入操作,要求是插入后容器中的元素仍然是有序的。我们应该选择list还是vector?

让我们先从算法复杂度的角度来简单看一下这个问题。首先一点是有序,所以找到要插入的位置,对于list的算法复杂度是O(n),因为平均需要遍历一半的链表长度,对于vector的算法复杂度是log^2(n),因为可以进行二分查找确定位置。然后是插入,list的插入操作是O(1),非常理想的常数级操作,而vector的插入操作是O(n),因为平均要移动一半的元素。综合下来看,list是要更胜一筹,所以应该选择list。但是事实却与这个推测截然相反?

让我们用C++写一段程序来进行验证:

#include <iostream>
#include <vector>
#include <list>
#include <random>

using namespace std;

template <typename T>
typename T::iterator insert(T& c, typename T::value_type elem)
{
    auto i = c.begin();
    for (; i != c.end(); i++) {
        if (elem <= *i) {
            break;
        }
    }
    return c.insert(i, elem);
}

int main(int argc, char** argv)
{
    vector<int> v;
    list<int> l;
    auto engine = default_random_engine();

    if (argc < 3) return 1;

    if (argv[1] && argv[1][0] == 'v') {
        for (int i = 0; i < atoi(argv[2]); i++) {
            insert(v, engine());
        }
    } else {
        for (int i = 0; i < atoi(argv[2]); i++) {
            insert(l, engine());
        }
    }

    return 0;
}

在这里为了说明问题方便起见,在查找阶段我们让vector和list都使用O(n)的方法进行查找。那么对于这段程序(下面表里的算法复杂度是针对每次插入操作而言的):

  locate insert
vector O(n) O(n)
list O(n) O(1)

这样,我们通过生成一系列随机数的方式来进行测试。让我们看看不同数据规模下的测试结果如何,表格中的时间单位是秒。

规模 vector list
100 0.002 0.003
1000 0.003 0.004
10000 0.019 0.142
100000 1.153 29.504

为什么list的性能反而差,而且相差如此悬殊?因为我们之前没有站在体系结构的角度看问题。同样是O(n)的操作,对于计算机而言实际执行的效率可能有着天壤之别。

让我们回顾一下前面程序中的insert函数模板,对于两种容器,我们使用了完全相同的线性查找算法。对于计算机而言,list版本的步进操作(i++),需要多进行一次寻址(根据指针找到下一个节点的位置),而更重要的是,找到的下一个节点,很有可能没有命中缓存,因为通过list中的相邻元素在内存中并没有相邻关系;而vector的步进操作,几乎能够保证命中缓存,因为每次访问的,都是内存中相邻的元素。对于插入操作而言,list虽然只有O(1)复杂度,而且确实非常快,但却要每次进行一次很小的内存分配,而又因为list的每个节点都要包含其他指针信息,对于内存空间也是很大的浪费。

我们从这个测试中得到的启示是:

  • 性能分析要用实际测试数据说话,主观推测容易以偏概全;
  • 对于体系结构的理解非常重要,缓存命中率是影响性能的重要因素;
  • 数据规模小的时候,算法复杂度无关紧要;
  • 不要过度优化;
  • 节约使用内存!