6
\$\begingroup\$

I'm trying to optimize my code (time optimization) based on this problem:

Let S be a set of strings. Each string in S is associated with a set of elements. Consider, for example, S = {"home", "tree"}. Implement a data structure that is a collection of sets and supports the operations Union, Move and Print. Initially, each string belongs to its own set. In particular, S1 = {'home'}, S2 = {'tree'}.

Allowed operations are:

  • u tree house: Combine the house sets containing (S1) and shaft (S2).
  • m tree house: Move the string in the set of tree house (S2).
  • s house: Print the number of items in the home and the amount of length of the strings present.

The reading must be done by standard inputs. For each test, the first line contains the character and the two integers a and b (a, b > 0), where a represents the number of elements in S and b represents the number of operations to be performed. The second line begins with the character and followed by the list of strings in S. The remaining lines b contain the operations to be performed.

N.B.: The last line contains the string "<END>"

Here's my attempt:

int main() {

    map<string, unsigned int> myMap;
    map<unsigned int, pair<unsigned int, set<string> > > mapSet;

    std::ios_base::sync_with_stdio(false);
    string line;
    string line1;
    string line2;

    int value = 0;
    while (line.compare("<END>") != 0) {
        cin >> line;
        if (line.compare("i") == 0) {
            cin >> line1 >> line2;

            value = atoi(line1.c_str());
            myMap.clear();
            mapSet.clear();

        }

        if (line.compare("e") == 0) {

            for (unsigned int i = 0; i < value; i++) {
                cin >> line1;

                myMap[line1] = i;
                set<string> set;
                set.insert(line1);
                mapSet[i] = make_pair(line1.length(), set);

            }
        } else {
            if (line.compare("m") == 0) {

                cin >> line1 >> line2;

                int index = myMap[line1];
                int index2 = myMap[line2];

                if (index != index2) {
                    if (mapSet[index].first > line1.length()) {
                        int newLength = mapSet[index].first;
                        mapSet[index].first = newLength - line1.length();
                        mapSet[index].second.erase(line1);
                    }
                    mapSet[index2].first += line1.length();
                    mapSet[index2].second.insert(line1);

                    myMap[line1] = index2;

                }
            }

            else {
                if (line.compare("u") == 0) {
                    cin >> line1 >> line2;

                    int index = myMap[line1];
                    int index2 = myMap[line2];

                    if (index != index2) {
                        if (mapSet[index].second.size()
                                < mapSet[index2].second.size()) {
                            set<string>::iterator it =
                                    mapSet[index].second.begin();
                            string value;
                            int sum = mapSet[index].first
                                    + mapSet[index2].first;
                            mapSet[index2].first = sum;

                            while (it != mapSet[index].second.end()) {

                                value = (*it);
                                myMap[value] = index2;
                                mapSet[index2].second.insert(value);
                                it++;
                            }
                            mapSet.erase(index);
                        } else {
                            set<string>::iterator it =
                                    mapSet[index2].second.begin();
                            string value;
                            int sum = mapSet[index].first
                                    + mapSet[index2].first;
                            mapSet[index].first = sum;

                            while (it != mapSet[index2].second.end()) {

                                value = (*it);
                                myMap[value] = index;
                                mapSet[index].second.insert(value);
                                it++;
                            }
                            mapSet.erase(index2);
                        }

                    }
                } else {
                    if (line.compare("s") == 0) {

                        cin >> line1;

                        cout<<mapSet[myMap[line1]].second.size()<<" "<<mapSet[myMap[line1]].first;

                    }

                }
            }

        }
    }

    return 0;
}
\$\endgroup\$
1
  • \$\begingroup\$ Each time you call [] on the map, it performs an expensive search. Store the result in a reference. \$\endgroup\$
    – Neil Kirk
    Jun 21, 2014 at 23:10

1 Answer 1

3
\$\begingroup\$

Before you attempt to optimize this, I would recommend refactoring it to be easier to follow. It may seem easier to just put everything into main() and not have to worry about functions, but that's actually worse. Just by looking at this, I wouldn't be able to tell what the code is doing nor how many different operations are being performed. There is a lot of nesting here, which can greatly complicate the code and even suggest longer runtime (especially nested loops and conditions in loops, which bring branch prediction into the equation).

But, luckily you've provided the challenge prompt for this, so it can be refactored.

Essentially, you can have three functions: one for each of the stated operations. They can all just be called in main() (unless one needs to call another), after initialing the data structures.

It should then be much easier to follow the program's flow and determine where possible optimizations may be needed. You'll especially benefit from greater maintainability, for yourself and for others.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.