I have a list of commands that if a user inputs then it will call separate functions. Talking to a friend he said I should use switch, which is faster and easier to read over "if, else if, else" statements.
When checking how to implement this I realised that I wouldn't be able to because the input is a string and for a switch to work I would need to cast it to an enum and it seems like the most straightforward option I have is to map each of the options like below.
header
enum class input
{
min,
max,
avg,
count,
stdev,
sum,
var,
pow
};
map<string, input> inMap
{
{ "min", input::min },
{ "max", input::max },
{ "avg", input::avg },
{ "count", input::count },
{ "stdev", input::stdev },
{ "sum", input::sum },
{ "var", input::var },
{ "pow", input::pow }
};
Is there a more accessible option to use enum where I don't have to map each value? This is very time-consuming and I'm not seeing any benefits at the moment.
cpp.
void test::processInput(vector<string> input) {
switch (inMap[input[0]]) {
case inMap::min:
MIN(input);
break;
case inMap::max:
MAX(input);
break;
case inMap::avg:
AVG(input);
break;
case inMap::count:
COUNT(input);
break;
case inMap::stdev:
STDEV(input);
break;
case inMap::sum:
SUM(input);
break;
case inMap::var:
VAR(input);
break;
case inMap::pow:
POW(input);
break;
default:
std::cout << "Error, input not found" << std::endl;
}
I read some posts about hashing the value instead, is this a good option? At this point wouldn't be just better to continue using if, else if, else?
Thanks!
CodePudding user response:
Why not have a map of string to function.
Then you don't need to convert to an enum.
using Action = void(std::vector<std::string>);
using ActionFunc = std::function<Action>;
using ActionMap = std::map<std::string, ActionFunc>;
void MIN(std::vector<std::string>){}
... etc
ActionMap inMap
{
{ "min", MIN },
{ "max", MAX },
{ "avg", AVG },
{ "count", COUNT },
{ "stdev", STDDEV },
{ "sum", SUM },
{ "var", VAR },
{ "pow", POW }
};
void test::processInput(std::vector<std::string> input) // May want a ref here.
{
auto find = inMap.find(input[0]);
if (find == inMap.end()) {
std::cout << "Error, input not found" << std::endl;
return;
}
find->second(input);
}
CodePudding user response:
Either way you are doing a number of string compares, and string compares are slow.
When you do the if/else you are on average doing n/2 compares if you have n target strings. So 4 compares for the 8 keywords.
When you do a map
, this reduces to log2(n) compares - so 3 compares for 8 entries. Oh and one extra backwards compare to check if the value equals the index. If it is both not less and not greater, then it must be equal.
Given the map code is more complex, you don't win, as you have seen. With (many) more keywords to check for, you will get a benefit.
If you use unordered_map
, then the string is converted into an integer hash value, and that is effectively used to directly look up the answer. Calculating the hash can be a slow process, though, and a final compare will be done to check the found value exactly matches. There is also a higher set-up cost generating the hashes for all the keywords. In this particular case, you could write your own hash function which just takes the first 2 characters, and perhaps trim the range down, which would be somewhat faster than the default string hash function.
The final alternative is to do a character-by-character look-up. If the first character is 'm' then you immediately reduce the check to 2 options. 's' gives 2 other options, and so-on. For a small data set like this, just doing that first character filter will make a difference, doing a second character gives you unique checks. These are simple character compares, not whole string compares, so much faster!
There is no trivial stdlib data structure that can help you with this. You could write it out longhand as 2 levels of nested case statements:
switch (input[0][0])
{
case 'm':
switch (input[0][1])
{
case 'i':
if (input[0].compare("min")==0) return MIN;
return NO_MATCH;
case 'a':
if (input[0].compare("max")==0) return MAX;
return NO_MATCH;
}
return NO_MATCH;
case 's':
switch(input[0][1])
{
case 't':
case 'u':
}
... etc
(as an exercise for the reader, there is a version of string::compare() that will skip the characters you have already compared)
You can build your own tree structure to represent this word look-up. If you add the ability to skip through multiple letters in the tree you can produce a fairly efficient string dictionary look-up which costs little more than a single string compare.
Another option is that with a sorted vector of string/target pairs you can do a custom binary chop function that takes advantage of knowing that all the strings still in the search span have the same initial letters, and do not need to be compared any more. In this case, it won't make much difference, but with hundreds of keywords, this would be much more maintainable than the manual case statements.
But in the end, most keyword detecting code is fast enough using the simple hash table provided by unordered_map
.