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点部分).

有什么办法可以像D代码那样快速地生成C++代码吗？为什么我的C++代码运行速度与D代码一样快？

---

编辑:对于所有的澄清,g ++用于C++而没有任何优化,而'dmd'用于Dlang,没有任何优化

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

find()在D修改数组(看起来像某种动态编程,你是否兑现以前的结果),而在C++中你总是进行完全查找.你应该比较苹果和苹果,特别是这些代码可以在C++中以完全相同的方式编写.