爲什麼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慢？

回答

相關問題