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 代码那么快？

编辑：对于所有澄清，g++ 用于 C++，没有任何优化，'dmd' 用于 Dlang，也没有任何优化

Answer 1

导致 C++ 版本性能低下的一个可能因素是 'inc' 函数。它按值接收 2 'Edge' 个结构，这在 C++ 中意味着在 main() 结束时的排序调用期间为每次比较复制结构。

尝试更改 'inc' 的签名以接受 'const Edge&' 而不是 'Edge'。这将导致结构值通过引用传递，从而避免额外的复制。

此外，如果您运行是一名探查员，您应该能够找到大部分时间都花在了哪里。这是接近优化的 'right' 方法：通过测量找到性能瓶颈，解决瓶颈并再次测量以确认您确实提高了性能。

Answer 2

find() 似乎被大量使用，它们在 D 和 C++ 实现中有很大不同：

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

对比：

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

find() 在 D 中修改数组（看起来像某种动态规划，你是否兑现了以前的结果）而在 C++ 中你总是进行完整查找。您应该将苹果与苹果进行比较，尤其是这段代码可以用 C++ 完全相同的方式编写。

Answer 3

出于好奇，我尝试了运行ning OPs 代码，以及下面的版本，我通过对 'D' 代码进行微调来创建它，以便它可以在 C++ 下编译。 OPs 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);
}

D-lang 比 C++ 更快？

D-lang being faster than C++?

c++

algorithm

d

c++11