8

I am trying to improve a C++ assignment to make it more efficient. I am a beginner with the language (and programming in general too), so I am only using what I know so far (if, else). I have a function that converts scores into levels, so anything under 30 = 1, 30-49 = 2, 50-79 = 3 and so on...

Here is how I am doing it:

if (score1 <= 30) level1 = 1;
else if (score1 <= 49) level1 = 2;
else level1 = 3;

if (score2 <= 30) level2 = 1;
else if (score2 <= 49) level2 = 2;
else level2 = 3;

//etc...

Is there a better way to do this, as I am aware this will require a new line for every single score I have.

10
  • 1
    OP here - Thanks for the help. This has given me plenty of food for thought. I will have a go at turning the statements into a function and pass in the score.
    – B Smith
    Oct 25, 2010 at 13:35
  • What do you mean by "efficient"? You might be able to make the code shorter, but it will likely only get slower (but not measurably so) in terms of run-time.
    – user229044
    Oct 25, 2010 at 15:45
  • Sorry I am still learning the lingo! - A better word might have been 'cleaner'. I don't necessarily want the code to run quicker. But I am aware, that if I had say 4 scores rather than 2, the current model would double in length.
    – B Smith
    Oct 25, 2010 at 15:52
  • If you often have questions like this, one book to check out is Martin Fowler's Refactoring: Improving the Design of Existing Code (martinfowler.com/books.html#refactoring).
    – user334856
    Oct 25, 2010 at 16:21
  • 1
    I edited your title to match your comment, so as not to confuse people. Oct 26, 2010 at 4:16

9 Answers 9

13

This rather depends on what you mean by efficiency. You could keep the limits for each level in an array

int level_limits[] = {0, 30, 49, 79, [...]};

int getLevel(int score)
{
   int level;
   for (level = 0; level < N_LEVELS; ++level)
       if (level_limits[level] > score)
            return level;
   return level; // or whatever should happen when you exceed the score of the top level
 }
 ...

 level1 = getLevel(score1);
 level2 = getLevel(score2);

... or something like that.

6
  • 5
    l+=1 is spelled ++l in C++.
    – sbi
    Oct 25, 2010 at 14:45
  • 1
    That's just a style issue? Personally, I prefer l += 1 Oct 25, 2010 at 14:48
  • 1
    This seems to be the most easily maintainable and extendable solution. The mainline code just calls a well-named function, getLevel, you have a simple representation for defining the levels (the array), and getLevel is easy to unit test. (Even better would be to use a variable named level, so that the l doesn't look like a 1. Readability is important, and there's no need to abbreviate in this case. Most style guides will recommend ++level over level += 1.)
    – user334856
    Oct 25, 2010 at 16:14
  • 2
    I wouldn't recommend to use l as a variable name, because it is easy to confuse with 1 (I actually did =)).
    – vitaut
    Oct 26, 2010 at 6:38
  • Typo in array declaration - Nice idea though!
    – Dijkstra
    Oct 26, 2010 at 10:17
5

Create a function where you pass in the score and it returns the level. Also, if there are going to be a lot of them you should create an array of scores and levels.

for (x=0;x < num_scores;x++)
{
   level[x] = get_level(score[x]);
}

something like that.

7
  • 1
    +1 for the function idea. The array idea might not be the best, however, since the original post is clearly based on ranges.
    – Randolpho
    Oct 25, 2010 at 13:06
  • @Randolpho: Should still be able to handle ranges easily enough with an array (and if even if there are many, a binary search will still be possible). Oct 25, 2010 at 13:08
  • 1
    @Randolpho: the arrays are used to store the scores and levels, not as a lookup table to determine a level based on a score. Oct 25, 2010 at 13:09
  • The array is for the starting scores. The get_level() function returns the correct level for the score. And if your ranges change, you need to fix one if statement, not N of them. Oct 25, 2010 at 13:09
  • 4
    Why use x != num_scores instead of x < num_scores?
    – jball
    Oct 25, 2010 at 13:11
5

First of all factor out the code for computing the level into a separate function, say get_level:

level1 = get_level(score1);
level2 = get_level(score2);

You can implement get_level in different ways.

If the number of levels is small you can use the linear search:

const int bounds[] = {30, 49, 79}; // Add more level bounds here.

int get_level(int score)
{
    const size_t NUM_BOUNDS = sizeof(bounds) / sizeof(*bounds);
    for (size_t i = 0; i < NUM_BOUNDS; ++i)
        if (score <= bounds[i])
            return i + 1;
    return NUM_BOUNDS + 1;
}

Or, if you are an STL fan:

#include <algorithm>
#include <functional>

const int bounds[] = {30, 49, 79}; // Add more level bounds here.

int get_level(int score)
{
    return std::find_if(bounds,
        bounds + sizeof(bounds) / sizeof(*bounds),
        std::bind2nd(std::greater_equal<int>(), score)) - bounds + 1;
}

If you have many levels binary search may be more appropriate:

#include <algorithm>

const int bounds[] = {30, 49, 79}; // Add more level bounds here.

int get_level(int score)
{
    return std::lower_bound(bounds,
        bounds + sizeof(bounds) / sizeof(*bounds), score) - bounds + 1;
}

Or if you have relatively small number of levels then use if-else chain similar to your original version:

int get_level(int score)
{
    if (score <= 30)
        return 1;
    else if (score <= 49)
        return 2;
    else if (score <= 79)
        return 3;
    return 4;
}

Note that putting returns on separate lines can make your program easier to trace in the debugger.

6
  • std::lower_bound(bounds,bounds + sizeof(bounds) / sizeof(*bounds), score) - bounds + 1; You have to love the STL sometimes, but I do wonder if the authors of it have ever actually written any working code. Oct 26, 2010 at 4:34
  • They did - it was STL itself =)
    – vitaut
    Oct 26, 2010 at 6:02
  • @Martin: STL to me feels like a design someone came up with to shoe-horn features from other high level languages into C++, without requiring a new compiler. Oct 26, 2010 at 10:24
  • @vitaut: The lower_bound is almost perfect, if it weren't for all the cruft of turning an iterator back into an index. Because of that, I think the first option is the best you have here. I also wouldn't take the ternary option, unless it could be re-formatted like the original if-then blocks. It takes no-brainer code and makes it so you have to think about it for a second, which is exactly the opposite of what you're trying to do. Oct 26, 2010 at 10:36
  • @Merlyn: I wouldn't use the version with ternary operators either - it was only to illustrate the point. It should probably be removed because it was written when a question was about efficiency, not clarity.
    – vitaut
    Oct 26, 2010 at 11:07
4

No, In terms of efficiency it's already optimized.

On another stylistic note. I would recommend putting the conditions and statements on separate lines:

if (score1 <= 30) {
    level1 = 1;
} else if (score1 <= 49) {
    level1 = 2;
} else if (score1 <= 79) {
    level1 = 3;
}

and as the other answer suggest, another stylistic plus would be to extract out the common behavior into a function

6
  • 3
    Optimized, maybe, but definitely not maintainable, which should always be your primary focus.
    – Randolpho
    Oct 25, 2010 at 13:07
  • I agree, I would create a function personally like phkahler said (I even voted it up), but to answer the OP, his if statements can't really be written to function faster (or at least I can't think of a way to do so) Oct 25, 2010 at 13:09
  • Ah, though, I did just see the last line of his question ("is there a better way to do this") Oct 25, 2010 at 13:10
  • 1
    In terms of maintainability, the one-entry-per-line style of the OP seems a lot easier to me than yours.
    – sbi
    Oct 25, 2010 at 14:48
  • I guess it has always been my pet peeve to open conditional statements with { and close them with }, so seeing the OP's style makes me instantly want to change it. :) Oct 25, 2010 at 14:50
2

The absolute fastest way:

Create an array of 80 values, one for each possible score. Fill in the array with the level for each possible score.

Example: int score_array[80] = {1,1,1,1,...};

The following code gets you the level for each score:

level2 = score_array[score2];

This will compile down to one machine instruction. Doesn't get much faster.

3
  • I'd stay away from "absolute fastest". That one instruction does a random access on a large array (were not given any upper limit to the value), which can cause page faults and goodness knows what else, all leading to many thousands of instructions being processed before that one instruction completes!
    – Skizz
    Oct 26, 2010 at 10:28
  • I wouldn't call this a "large" array, but that's a good point.
    – Jay
    Oct 26, 2010 at 16:49
  • hehe nice, maintenance nightmare, but definitely the fasted :) Feb 22, 2011 at 19:52
2

If the score has a "manageable" range, how about the following?

// Convert score to level. Valid scores are in the range [0-79]
int score2level( int score ) {

    static const int level_table[ 80 ] = {
        1, 1, 1, ...     // 31 "1"s for range 0-30
        2, 2, 2, ...     // 19 "2"s for range 31-49
        3, 3, 3, ...     // 30 "3"s for range 50-79
    };

    assert( (0 <= score) && (score <= 79) );

    return level_table[ score ];
 }

The motivation is to avoid conditional code (the if, elses) at the cost of a pre-populated table. May be its too much for 3 levels, but may help when the number of levels increase.

1
  int getLevel(int score)
  {
      if(score<=30)
          return 1;
      int level=2,limit=49;
      while(score > limit)
      {
          limit+=30;
          level++;
      }
      return level;
  }  

  int score[]={35,25,67,56,78};
  int level[5];
  for(int i=0;i<5;i++)
      level[i]=getLevel(score[i]);

Cheers :)

1

You can utilize modulo and a hash table in order to achieve some code style elegance. Pseudo code:

int getLevel(int num)
{
   hash_table = (30=>1, 49=>2, 79=>3);
   foreach threshold (keys hash_table) {
      if (num modulo (threshold + 1) == num) {
        return hash_table[threshold];
      }
   }
}
1

If you have less levels than fingers on your hands, you should use Paul's suggestion. However, if the number of levels are bigger, you could use binary search if your level thresholds are fairly uniform (and strictly increasing). Then you can get close to logarithmic runtime (I mean, you were asking for efficiency).

This is a good compromise between the lookuptable-suggestion and the linear search, but again, it only pays if you have a lot of levels.

Oh, by the way, if there is a pattern in how the thresholds are chosen, you should use that instead of searching for the right level.

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.