D-lang比C++更快嗎？

Question

所以我正在爲即將到來的算法編程競賽練習，而我偶然發現了去年的一個問題。

我幾乎解決了它（在C++中），但我得到了一些超時，所以我看看官方解決方案，它是用Dlang編寫的。

然後我嘗試模仿D中的官方答案，但我仍然超時（單個輸入> 4秒）。 AFAIK，C++應該是比d快，但d解決了相同的輸入中分裂第二和C++的時間超過5秒，它

這裏是d答案代碼

import std.stdio; 
import std.algorithm; 

struct edge { 
    int src, des, w, o; 

    int opCmp (ref const edge e) const { 
     if(w != e.w) return w - e.w; 
     else return o - e.o; 
    } 
}; 

const int MAXN = 100004, MAXM = 200004; 
int N, M, D, ee, weight, days; 
int[MAXN] ds; 
edge[] edges; 

void init() { 
    for(int i=1;i<=N;i++) ds[i] = i; 
} 

int find(int x) { 
    return ds[x] = (x == ds[x] ? x: find(ds[x])); 
} 

bool connected(int x, int y) { 
    return find(x) == find(y); 
} 

bool merge(int x, int y) { 
    int xr = find(x), yr = find(y); 
    if(xr^yr) { 
     ds[xr] = yr; 
     return 1; 
    } 
    return 0; 
} 

void main() { 
    scanf("%d%d%d", &N, &M, &D); 
    for(int i=1, a, b, c;i<=M;i++) { 
     scanf("%d%d%d", &a, &b, &c); 
     if(i < N) 
      edges ~= edge(a, b, c, 0); 
     else 
      edges ~= edge(a, b, c, 1); 
    } 
    edges.sort(); 
    init(); 
    int i, maxe=0; 
    for(i=0;i<edges.length;i++) { 
     auto e = edges[i]; 
     if(merge(e.src, e.des)) { 
      if(e.o) 
       days ++; 
     } 
    } 
    printf("%d", days); 
} 

然後在這裏是我在C寫++作爲答案代碼

#include <iostream> 
#include <vector> 
#include <map> 
#include <algorithm> 

using namespace std; 

struct Edge{ 
    long long source, end, weight, old; 
    Edge(long long _s, long long _e, long long _w, long long _o):source(_s), end(_e), weight(_w), old(_o){} 
}; 

int parents[100004]; 
vector<Edge>edges; 

bool inc(Edge a, Edge b) 
{ 
    if(a.weight == b.weight)return a.old > b.old; 
    return a.weight < b.weight; 
} 

long long find(long long node) 
{ 
    if(parents[node] == node)return node; 
    else return find(parents[node]); 
} 

void init(long long M) 
{ 
    for(long long i = 0; i < M; ++i)parents[i] = i; 
} 

bool connect(long long x, long long y) 
{ 
    long long fx = find(x); 
    long long fy = find(y); 
    if(fx == fy)return false; 
    parents[fx] = fy; 
    return true; 
} 

long long noOfDays() 
{ 
    long long days = 0; 
    for(auto edge : edges){ 
     if(connect(edge.source, edge.end)){ 
      if(!edge.old)++days; 
     } 
    } 
    return days; 
} 

int main() 
{ 
    ios::sync_with_stdio(false); 
    long long N, M , D; 
    cin >> N >> M >> D; 
    N--; 
    for(long long i = 0; i < M; ++i){ 
     long long a,b,c; 
     cin >> a >> b >> c; 
     if(i < N){ 
      edges.push_back(Edge(a,b,c,1)); 
     }else{ 
      edges.push_back(Edge(a,b,c,0));   
     } 
    } 
    sort(edges.begin(), edges.end(), inc); 
    init(N+2); 
    cout << noOfDays() << endl; 
} 

這需要在C++ 5秒以上的輸入，和第二對d的分割可以在這裏找到「http://ddl3.data.hu/get/356808/10699419/s4.24.in」

這是我實際上試圖解決的問題「https://dmoj.ca/problem/ccc17s4」（我只做了11分的部分）。

有什麼辦法讓我的C++代碼和D代碼一樣快嗎？爲什麼我的C++代碼不像D代碼那麼快？

---

編輯：對於所有的澄清，使用克++爲C++，沒有任何優化，併爲Dlang「DMD」，沒有任何優化任一

Answer 1

find()似乎是大量使用和它們在d非常不同和C++實現：

int find(int x) { 
    return ds[x] = (x == ds[x] ? x: find(ds[x])); 
} 

VS：

long long find(long long node) 
{ 
    if(parents[node] == node)return node; 
    else return find(parents[node]); 
} 

在d find()修改陣列（看起來像某種動態編程的，你是否兌現以前的結果），而在C++中，你總是進行全面查找。您應該將蘋果與蘋果進行比較，尤其是這種代碼可以用C++完全相同的方式編寫。

Answer 2

一種可能的貢獻者C的性能下降++版本是'inc'功能。它通過值接收2個'Edge'結構體，在C++中這意味着在main（）結束的排序調用期間爲每次比較複製結構體。

嘗試更改'inc'的簽名以接受'const Edge &'而不是'Edge'。這將導致結構值被引用傳遞，因此避免額外的複製。

另外，如果你運行一個分析器，你應該能夠找到大部分時間都花在哪裏。這是進行優化的「正確」方式：衡量您是否遇到性能瓶頸，再次解決瓶頸問題並再次測量，以確認您確實已經提高了性能。

Answer 3

出於好奇，我試着運行OP代碼，以及下面的版本，我通過最小化調整'D'代碼以便它可以在C++下編譯創建。 OP的C++版本需要大約12秒的時間才能運行。下面的版本花費了大約0.25秒的時間來運行。

我的結論是，在回答這個問題時，OP所看到的運行時間的差異很可能是由於其他一些答案中描述的實現差異，而不是C++的糟糕表現。

#include <cstdio> 
#include <vector> 
#include <algorithm> 

struct edge { 
    edge(int src, int des, int w, int o) : src(src), des(des), w(w), o(o) {} 

    int src, des, w, o; 

    int opCmp(const edge& e) const { 
     if (w != e.w) return w - e.w; 
     else return o - e.o; 
    } 
}; 

const int MAXN = 100004, MAXM = 200004; 
int N, M, D, ee, weight, days; 
int ds[MAXN]; 
std::vector<edge> edges; 

void init() { 
    for (int i = 1; i <= N; i++) ds[i] = i; 
} 

int find(int x) { 
    return ds[x] = (x == ds[x] ? x : find(ds[x])); 
} 

bool connected(int x, int y) { 
    return find(x) == find(y); 
} 

bool merge(int x, int y) { 
    int xr = find(x), yr = find(y); 
    if (xr^yr) { 
     ds[xr] = yr; 
     return 1; 
    } 
    return 0; 
} 

void main() { 
    std::scanf("%d%d%d", &N, &M, &D); 
    for (int i = 1, a, b, c; i <= M; i++) { 
     scanf("%d%d%d", &a, &b, &c); 
     if (i < N) 
      edges.push_back(edge(a, b, c, 0)); 
     else 
      edges.push_back(edge(a, b, c, 1)); 
    } 
    std::sort(edges.begin(), edges.end(), [](const edge& lhs, const edge& rhs) { return lhs.opCmp(rhs) < 0; }); 
    init(); 
    int i, maxe = 0; 
    for (i = 0; i<edges.size(); i++) { 
     auto e = edges[i]; 
     if (merge(e.src, e.des)) { 
      if (e.o) 
       days++; 
     } 
    } 
    printf("%d", days); 
}