再议C++的性能

最近在公司里的项目做的是性能优化，相关性能调优的经验总结也在前一篇文章里说了。这里再说一说和性能相关的东西。主要针对的是C++类库中常用的一些数据结构，比方说std::string、顺序容器(vector)、关联容器(std::unordered_set、unordered_map)等。

我们拿一道典型的面试题来作为本文分析的切入点。题目是这样的 (problem is from leetcode, Word Ladder)：

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

大意就是有一个转换字典并且指定了两个单词(单词1和单词2)，求单词1经过多少次转换后可以变成单词2，中间转换过程中生成的单词必须在转换字典中。

第一眼望过去，很明显是一个最短路径的问题，首先把dict转换成一个图，图的顶点就是单词。如果两个单词的编辑距离为一，那么两个顶点之间就有一条边。

解决这个问题的整个逻辑就可以看成是：

1. 将单词1加入到数组L中。
2. 判断数组L是否为空，若空，程序退出。
3. 遍历数组L中的每一个元素：
   • 如果某个元素等于单词2，那么程序返回数组L遍历次数，并退出。
   • 若找不到单词2，那么将所有和数组L中的顶点编辑距离为1的单词顶点找出来，并将数组L清空。
4. 将第三步找到的所有顶点重新加入到数组L中。
5. 重复步骤2

这是一个典型的广搜(BFS)问题(不能用深搜(DFS)来解决，为什么？)。

按照上面的思路我们可以先得到一个解决方案：

typedef pair<string, int>       vertex;                              // first is the vertex name, second is the distance from the start node.
typedef vector<vertex>             vertex_collection;
typedef unordered_map<string, vertex_collection>    graph;              // graph.first: graph name, graph.second adjcent vertexes

graph g;

void initGraph(unordered_set<string>& dict, const string& start, const string& end)
{
   g.clear();

    for (auto i = dict.begin(); i != dict.end(); ++i)
    {
        if (1 == getDistance(start, *i))
        {
            g[start].push_back(make_pair(*i, INT_MAX));
        }

        if (1 == getDistance(*i, end))
        {
            g[*i].push_back(make_pair(end, INT_MAX));
        }

        for (auto j = next(i); j != dict.end(); ++j)
        {
            if (1 == getDistance(*i, *j))
            {
                g[*i].push_back(make_pair(*j, INT_MAX));
                g[*j].push_back(make_pair(*i, INT_MAX));
            }
        }
    }
}

    int bfs(const string& start, const string& end)
    {
        unordered_set<string> unused;
        deque<vertex> processingQueue;

        processingQueue.push_back(make_pair(start, 1));
        while (!processingQueue.empty())
        {
            vertex v = processingQueue.front();
            processingQueue.pop_front();

            if (v.first == end)
            {
                return v.second;
            }

            vertex_collection& candidates = g[v.first];
            for (auto i = candidates.begin(); i != candidates.end(); ++i)
            {
                vertex& c = *i;
                if (unused.find(c.first) == unused.end())
                {
                    c.second = v.second + 1;
                    processingQueue.push_back(c);
                    unused.insert(c.first);
                }
            }
        }

        return 0;
    }

    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        initGraph(dict, start, end);

        return bfs(start, end);
    }

咋一看，没多大问题。但事实上问题还是挺多的，至少存在下面几个问题

1. 空间上的浪费。初始化时我们做了g[*i].push_back(make_pair(*j, INT_MAX))和g[*j].push_back(make_pair(*i, INT_MAX))，但是在后续bfs时我们更新的vertex c只影响到了graph g中的一个顶点。这个意思是说，当有两个顶点a、b和c的距离是1时，更新c的操作只会更新两个顶点中某一个顶点的邻接表，因为我们的push_back是按值传递的。其实，就本题目来说，vertex完全不需要使用pair。
2. 其实，第二个问题更严重。那就是初始化函数initGraph。这是个典型的O(n^2)的复杂度，而后面我们的bfs是O(n+e)的复杂度。所以对于一个有4、5千个顶点的图，在initGraph过程就会非常的耗时！！

要解决第二点问题，我们只需要把bfs改一改，把它改成明显的层次搜索的样子。另外，把initGraph全部丢弃。邻接表我们在bfs的时候动态计算。

int bfs(const string& start, const string& end, unordered_set<string>& dict)
    {
        unordered_set<string> unused;
        vector<vertex> level;
        vector<vertex> nextlevel;

        level.push_back(start);
        int length = 0;
        while (!level.empty())
        {
            ++length;
            for (auto i = level.begin(); i != level.end(); ++i)
            {
                vertex v = *i;

                if (v == end)
                {
                    return length;
                }

                for (auto j = dict.begin(); j != dict.end(); ++j)
                {
                    const vertex& c = *j;
                    if (1 == getDistance(v, c) && unused.find(c) == unused.end())
                    {
                        nextlevel.push_back(c);
                        unused.insert(c);
                    }
                }
            }

            swap(level, nextlevel);
            nextlevel.erase(nextlevel.begin(), nextlevel.end());
        }

        return 0;
    }

这样就是很明显的层次遍历，并且简化了pair类型的vertex，直接使用string。这里用的比较好的一个地方是swap函数，避免了nextlevel向level拷贝数据的操作。这里必须强调下，swap函数绝对是一个非常重要的函数！

我们很快会发现，这样的解决方案还不足以达到所期望的性能。仅从代码的表面看，我们至少可以发现一处可以优化的地方：

1. 在大数据的情况下，push_back、insert存在比较大的性能问题，这点是显而易见的。动态的内存分配不是个便宜的事情。这点我们可以通过容器的reserve函数来帮忙解决。

但是，事实告诉我们，使用reserve完全不能解决性能问题。

对于有4、5千个顶点来说，如果他是一个比较稠密的图的话，那么nextlevel.push_back(c)和unused.insert(c)会被执行几千次，在这个执行的过程中最大的问题就是字符串的构造函数会被调用很多次。

如何减少调用的次数呢？最直观的解决方案就是将容器保存的数据改成指针。

这个改动的过程相对来说，就会比较大一点，代码的结构也会看起来比较凌乱。虽然可以解决问题，但是绝对不是最好的方案。基于这个想法的改动，你可以在这里(Word Ladder.cpp)看到，实在是太丑了，就不贴了。

通过这一个简单的例子，我们可以看到，C++里常用的一些数据结构在大数据的情况下，性能表现其实是很一般的。造成这样的结果最主要的原因还是在如何使用上。在C++相对于C提供更多便捷的情况下，如何使用好C++却变得越来越有难度。同时C++本身在性能上也确实和C的差距比较大，所以我们可以看到最新的标准增加了右值引用等语言特性，增加了无序关联容器(unordered_set等)等数据结构。