0

I have a map with pair as its index. I found that it takes a lot of time to visit elements in it. I want to know whether there are some ways to accelerate the process? My code is as follow:

std::vector words;
...to generate a words vector...
std::map<std::pair<std::string, std::string>, int> wordCountMap;
wordsSize = words.size()
for(int i = 0; i < wordsSize; ++i){
    for(int j = i + 1; j < min(i + e, wordsSize); ++j){
        std::pair<std::string, std::string> pk = words[i] < words[j] ? std::make_pair(words[i], words[j]) : std::make_pair(words[j], words[i]);
        wordPairCountMap[pk] = wordPairCountMap.find(pk) != wordPairCountMap.end() ? wordPairCountMap[pk] + 1 : 1;
    }
}

I found that the construction of the pair indexed map cost a lot of time. How can I optimize it?

maple
  • 1,828
  • 2
  • 19
  • 28
  • "I found that the visit of the pair indexed map cost a lot of time." You show us only how you construct your `wordCountMap` but let us in the dark about your usual scenarios of "visiting" it after it is built. As such, we have no idea how well our potential suggestion may impact (help or hinder) the code which consumes this `wordCountMap`. – Adrian Colomitchi Oct 18 '16 at 07:26
  • StackOverflow questions should demonstrate that you have researched your problem and sought to thoroughly understand it before asking. – Miles Rout Oct 18 '16 at 07:29
  • @AdrianColomitchi It cost time at the construction procedure in the for loop. I just want to optimize the code inside the for loop above. – maple Oct 18 '16 at 08:58
  • @maple "It cost time at the construction procedure in the for loop" I would suggest using a `std::map wordCountMap;` with the key being the concat of the two words separated by a space. But can I honestly suggest it not knowing how the consuming code is going to react? – Adrian Colomitchi Oct 18 '16 at 09:04
  • @AdrianColomitchi Thanks, it's a good idea. However, I'm afraid "w1" + "w2" is the same as "w1w" + "2", because I cannot guaranteen that the word doesn't contain space. – maple Oct 18 '16 at 09:14
  • @maple did you know that you actually can [insert](http://en.cppreference.com/w/cpp/string/basic_string/insert) a [`0x00` character](http://stackoverflow.com/questions/164168/how-do-you-construct-a-stdstring-with-an-embedded-null) into a `std::string` and make it count towards the `str.length()`? If you don't like the `c_str()` mangled up, how about using the [BEL control char](https://en.wikipedia.org/wiki/Bell_character) as a separator? – Adrian Colomitchi Oct 18 '16 at 09:47

1 Answers1

1
++wordPairCountMap[pk];

may replace

wordPairCountMap[pk] = wordPairCountMap.find(pk) != wordPairCountMap.end() ?
                           wordPairCountMap[pk] + 1 : 1;

To avoid an extra lookup.

Note also that you does a lot of copy of string with your pairs

Jarod42
  • 203,559
  • 14
  • 181
  • 302