java - 为什么 C++ 在拓扑排序上比 Java 慢？

Question

我正在尝试解决 Leetcode(link here)上的拓扑排序问题。而且我惊讶地发现，使用相同的算法，C++ 比 Java 慢! C++方案耗时近500ms，而Java只有6~7ms。令人困惑...而且 C++ 也比 python、c# 和 javascript 慢。这是公认的解决方案运行时分布:

这里是C++版本和Java版本的代码。它们都使用DSF方法进行拓扑排序。

//Java
public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] edges = new ArrayList[numCourses];
    int[] visited = new int[numCourses];
    int[] res = new int[numCourses];
    for (int i = 0; i < edges.length; i++) 
        edges[i] = new ArrayList<Integer>();
    for (int[] edge : prerequisites) 
        edges[edge[0]].add(edge[1]); 

    for (int i = 0, j = 0; i < numCourses; i++) {
        j = dfs(i, edges, visited, res, j);
        if (j == -1) return new int[0]; // cycle, return empty array
    }

    return res;
}

private int dfs(int v, List<Integer>[] edges, int[] visited, int[] res, int i) {
    if (visited[v] == 2) return i;           // black node
    if (visited[v] == 1) return -1;          // gray node -> cycle
    visited[v] = 1;
    for(int j : edges[v]) {
        i = dfs(j, edges, visited, res, i);
        if (i == -1) return -1;              // if there is a cycle, propagate the error
    }
    visited[v] = 2;
    res[i] = v;
    return i+1;
}

--

//C++
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<int> outputs;
    vector<int> nodes(numCourses, 0);

    vector<list<int>> edges(numCourses);
    for (auto i=prerequisites.begin(); i!=prerequisites.end(); i++) {
        edges[i->first].push_back(i->second);
    }

    for(int i=0; i<numCourses; ++i)
    {
        if(!dfs(edges, outputs, nodes, i, numCourses))
        {
            outputs.clear();
            return outputs;
        }
    }

    return outputs;
}

bool dfs(vector<list<int>>& edges, vector<int>& outputs, vector<int>& nodes, int cur, int numCourses)
{
    if(nodes[cur] == 1) return false;
    if(nodes[cur] == 0)
    {
        nodes[cur]++;
        for(auto i=edges[cur].begin(); i!=edges[cur].end(); ++i)
        {
            if(!dfs(edges, outputs, nodes, *i, numCourses))
                return false;
        }
        nodes[cur]++;
        outputs.push_back(cur);
    }

    return true;
}

Answer 1

int[] res = new int[numCourses];与 vector<int> outputs;例如，这里的问题是 Java 预先知道它需要多少空间，来自 C++ 的 vector 可能需要在运行期间进行调整(这很昂贵，它涉及复制、分配和释放内存)。我不是说这是问题所在，这是问题之一。一定要针对 C++ 测试构建一个版本，而不是调试，同时避免不必要的复制，这是减慢速度的一个来源。