CODEWITHSUNDEEP
c++algorithmoptimization
Eric
Eric

Reputation: 127

Speeding up algorithm in C++

TL;DR: My code is "fast" in Java but slow as hell in C++. Why?

#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;
}

I have just tried my first C++ project, and it's re-written code from Java. The original task was to calculate how many numbers that needed to be changed in order to "balance" the input, given that each level above something weighs double the lower

eg [1,2] would need 1 change (either 1->2 or 2->1 in order to be equal on both sides and [8,[4,2]] would need 1 change (2->4) in order for the "lower level" to become 8 and therefore be of equal weight on the higher level. The problem can be found here for those who are interested:

Problem link

And for those who wonder, this is a school assignment regarding algorithms, but I'm not asking for help with that, since I have already completed it in Java. The problem is that my algorithm seem to be pretty shit when it comes to C++.

In Java I get times around 0.6 seconds, and in C++, the "same" code gives >2 seconds (time limit exceeded).

Anyone care to give me a pointer as to why this is? I was under the impression that C++ is supposedly faster than Java when it comes to these type of problems.

Upvotes: 0

Views: 169

Answers (1)

maxim1000
maxim1000

Reputation: 6365

One of possible reasons is copying.

Whenever you pass something by value in C++ a copy is created. For tings like double, int or a pointer, that's not a problem.

But for objects like std::string copying may be expensive. Since you don't modify data it makes sense to pass it by const reference:

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

Upvotes: 5

Related Questions