用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)命令"较低级别"变为8级,因此在较高级别上具有相同的权重.对于那些感兴趣的人,可以在这里找到问题:

问题链接

对于那些想知道的人来说,这是关于算法的学校作业,但我并不是在寻求帮助,因为我已经用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)