Deltamaster Tech Center

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

下面就是一个经典问题：

我们需要一个容器，容器中存放的是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)的方法进行查找。那么对于这段程序（下面表里的算法复杂度是针对每次插入操作而言的）：

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

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

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

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

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