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; 
} 

- この中vector<int> outputs;問題に対して

//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];例えばJavaはそれが必要とどのくらいのスペース事前に知っていることである、C++からのベクトルは、実行時に調整が必要な場合があります（これは高価ですそれには、メモリのコピー、割り当て、解放が含まれます）。私はそれが問題だと言っているわけではない、それは問題の一つだ。デバッグではなく、C++用のビルドをテストし、不必要なコピーを避けてください。これが遅くなる原因です。