c++ - 在 C++ 中加速算法

Question

TL;DR:我的代码在 Java 中“很快”，但在 C++ 中却慢得要死。为什么？

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


using namespace std;

int read(string data, int depth, int pos, vector<long>& wantedList) {
    // 91 = [
    if (data.at(pos) == 91) {
        pos++;
        // Get first part
        pos = read(data, depth + 1, pos, wantedList);
        // Get second part
        pos = read(data, depth + 1, pos, wantedList);
    } else {
        // Get the weight
        long weight = 0;
        while (data.length() > pos && isdigit(data.at(pos))) {
            weight = 10 * weight + data.at(pos++) - 48;
        }
        weight *= 2 << depth;
        wantedList.push_back(weight);
    }
    return ++pos;
}


int doStuff(string data) {
    typedef map<long, int> Map;
    vector<long> wantedList;
    Map map;
    read(data, 0, 0, wantedList);
    for (long i : wantedList) {
        if (map.find(i) != map.end()) {
            map[i] = map[i] + 1;
        } else {
            map[i] = 1;
        }
    }

    vector<int> list;
    for (Map::iterator it = map.begin(); it != map.end(); ++it) {
        list.push_back(it->second);
    }
    sort(list.begin(), list.begin() + list.size());
    cout << wantedList.size() - list.back() << "\n";
    return 0;

}

int main() {
    string data;
    int i;
    cin >> i;
    for (int j = 0; j < i ; ++j) {
        cin >> data;
        doStuff(data);
    }
    return 0;
}

我刚刚尝试了我的第一个 C++ 项目，它是从 Java 重写的代码。最初的任务是计算需要更改多少数字才能“平衡”输入，假设高于某物的每个级别的重量都是较低的两倍

例如 [1,2] 需要 1 次更改(1->2 或 2->1 以便两边相等，而 [8,[4,2]] 需要 1 次更改(2-> 4)为了让“lower level”变成8，从而在higher level上具有同等的权重。有兴趣的可以在这里找到问题:

Problem link

对于那些想知道的人，这是一项关于算法的学校作业，但我并不是在寻求帮助，因为我已经用 Java 完成了它。问题是当谈到 C++ 时，我的算法似乎很糟糕。

在 Java 中，我得到的时间大约为 0.6 秒，而在 C++ 中，“相同”代码给出的时间 >2 秒(超过时间限制)。

有人愿意给我指点这是为什么吗？我的印象是，在处理这些类型的问题时，C++ 据说比 Java 更快。

Answer 1

可能的原因之一是复制。

每当您在 C++ 中按值传递某些内容时，都会创建一个拷贝。对于像 double、int 或指针这样的类型，这不是问题。

但对于像 std::string 这样的对象，复制可能会很昂贵。由于您不修改 data，因此通过 const 引用传递它是有意义的:

int read(const string &data, int depth, int pos, vector<long>& wantedList)