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

我试图解决Leetcode上的拓扑排序问题（link here）。我惊讶地发现C++比Java有相同的算法慢！ C++解决方案的成本几乎为500毫秒，但Java仅为6〜7毫秒。这很让人困惑......而且C++也比python，c＃和javascript更慢。这里是公认的解决运行时分发：为什么C++在拓扑排序上比Java慢？

这里是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; 
}

来源

2016-04-28 Yyao

[这可能包含您的问题的答案]（http://stackoverflow.com/questions/145110/c-performance-vs-java-c） – SomeJavaGuy

C++版本不是1：1端口，它是轻微的不同于Java版本。所以你没有做出公正的比较。 – DarkDust

这听起来像使用C++调试版本。如果你想记录一个差异，你必须提供相关的**信息**。 –

int[] res = new int[numCourses];与vector<int> outputs;在此例如，该问题是Java会事先需要多大的空间，矢量从C++在运行过程中可能需要调整，知道（它是昂贵它涉及拷贝，分配和释放内存）。我不是说这是问题，而是问题之一。一定要测试为C++构建一个发行版而不是调试版，并且还要避免不必要的复制，这是造成速度放慢的一个原因。

来源

2016-04-28 09:12:34

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

回答

相关问题