November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts

What is optimal algorithm for switch case

Page  
1

Hi everybody!
I have current construction:

  1. switch(val){
  2.     case '0':
  3.         type = "mode a";
  4.         state = "free";
  5.         break;
  6.     case '1':
  7.         type = "mode a";
  8.         state = "busy";
  9.         break;
  10.     case '2':
  11.         type = "mode a";
  12.         state = "not def";
  13.         break;
  14.     case 'a':
  15.         type = "mode b";
  16.         state = "free";
  17.         break;
  18.     case 'b':
  19.         type = "mode b";
  20.         state = "busy";
  21.         break;
  22.     case 'c':
  23.         type = "mode b";
  24.         state = "not def";
  25.         break;
  26.     ...
  27.     default:
  28.         break;
  29. }

and its very long switch.
Any advice for shorter or more optimal code?

22 replies

November 22, 2011

BilbonSacquet BilbonSacquet
Lab Rat
75 posts

I assume that ‘val’ is a type char, why not do 2 index tables and a string list:

  1. int type_index[256] = { };
  2. int state_index[256] = { };
  3. QString messages[] = { "mode a", "mode b", "free", "busy", "not def" };
  4.  
  5. type = messages[type_index[val]]];
  6. state = messages[state_index[val]]];

?

November 22, 2011

Andre Andre
Robot Herder
6420 posts

There is no way around defining your mappings between your val and your state and type somewhere. You may be able to make that a bit shorter though. There are several ways to do that. You could think of:
1. Using a macro to replace the case blocks (ok, not pretty, but it works), so you end up with something like this

  1. switch(val) {
  2.    TYPE_MAP(0, "mode a", "free")
  3.    TYPE_MAP(1, "mode a", "busy")
  4.    /... etc.
  5. }

which would expand to whatever you are showing above.

2. Init some kind of mapping in a QHash, where you use your char as a key and store a struct that containst the values type and state. Then, the switch can be replaced by a lookup in the hash. However, you still need to initialize this hash somewhere, and although you can make that shorter than what you have now if you create a simple constructor, that is still a significant amount of code.

2a. I have also in the past avoided such large initializations of code by simply storing these mappings in a resource, and reading those in at initialization. I used a .csv file for that and just compiled that in using the Qt resource system. That prooved quite easy to maintain.

I’m sure there are many other tricks you can think of, including tricks involving templates, or perhaps encoding your different modes and states in a state machine. It all depends on your specific needs. Is this a speed-critical part of your code, for instance? How important is code size for you, if you weigh it against maintainability and against speed?

November 22, 2011

Andre Andre
Robot Herder
6420 posts

BilbonSacquet wrote:
I assume that ‘val’ is a type char, why not do 2 index tables and a string list:

  1. int type_index[256] = { };
  2. int state_index[256] = { };
  3. QString messages[] = { "mode a", "mode b", "free", "busy", "not def" };
  4.  
  5. type = messages[type_index[val]]];
  6. state = messages[state_index[val]]];

?

Interesting solution, though it seems to me to become hard to maintain for large mappings.

November 22, 2011

Volker Volker
Ant Farmer
5428 posts

Andre wrote:

Interesting solution, though it seems to me to become hard to maintain for large mappings.

And it looks ugly if you have wholes holes in the sequence, as one would need to fill those with null values.

I personally would go for a QHash/QMap – initializing it statically (hard coded in C++) or from a resource would have to be decided on a project to project base.

November 22, 2011

rokemoon rokemoon
Lab Rat
197 posts

Or like this:

  1. SomeClass::SomeClass()
  2. {
  3.  //here you cache needed types and states and associate them with value
  4.         //you can init in for example constructor of some class
  5.  QString modeA("mode a"), modeB("mode b");
  6.  QString stateFree("free"), stateNotDef("not def"), stateBusy("busy");
  7.  typedef QPair<QString, QString> type_state_t;
  8.  QMap<QChar, type_state_t > map;
  9.  map['0'] = type_state_t(modeA, stateFree);
  10.  map['1'] = type_state_t(modeA, stateBusy);
  11.  map['2'] = type_state_t(modeA, stateNotDef);
  12.  map['a'] = type_state_t(modeB, stateFree);
  13.  // and so on
  14. }

  1. void SomeFunc::setStateAndType(const QChar &val)
  2. {
  3.         //here your new switch
  4.  QMap<QChar, type_state_t >::iterator it;
  5.  it = map.find(val);
  6.  if (it != map.end()) {
  7.   type = it.value().first;
  8.   state = it.value().second;
  9.  }
  10. }

This code not tested, but I think the main idea you get.

November 22, 2011

Andre Andre
Robot Herder
6420 posts

Also, have a look at this [stackoverflow.com] discussion.

November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts

Andre wrote:

BilbonSacquet wrote:
I assume that ‘val’ is a type char, why not do 2 index tables and a string list:

  1. int type_index[256] = { };
  2. int state_index[256] = { };
  3. QString messages[] = { "mode a", "mode b", "free", "busy", "not def" };
  4.  
  5. type = messages[type_index[val]]];
  6. state = messages[state_index[val]]];

?

Interesting solution,

Yes it is but unfortunately i have holes in sequence as said Volker.

November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts

rokemoon wrote:
Or like this:
  1. SomeClass::SomeClass()
  2. {
  3.  //here you cache needed types and states and associate them with value
  4.         //you can init in for example constructor of some class
  5.  QString modeA("mode a"), modeB("mode b");
  6.  QString stateFree("free"), stateNotDef("not def"), stateBusy("busy");
  7.  typedef QPair<QString, QString> type_state_t;
  8.  QMap<QChar, type_state_t > map;
  9.  map['0'] = type_state_t(modeA, stateFree);
  10.  map['1'] = type_state_t(modeA, stateBusy);
  11.  map['2'] = type_state_t(modeA, stateNotDef);
  12.  map['a'] = type_state_t(modeB, stateFree);
  13.  // and so on
  14. }

  1. void SomeFunc::setStateAndType(const QChar &val)
  2. {
  3.         //here your new switch
  4.  QMap<QChar, type_state_t >::iterator it;
  5.  it = map.find(val);
  6.  if (it != map.end()) {
  7.   type = it.value().first;
  8.   state = it.value().second;
  9.  }
  10. }

This code not tested, but I think the main idea you get.

Nice, i like it. And what about code rate?

November 22, 2011

Andre Andre
Robot Herder
6420 posts

What is “code rate”?

November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts

Andre wrote:

Is this a speed-critical part of your code, for instance? How important is code size for you, if you weigh it against maintainability and against speed?

Speed is more important, maintainability is next and then size.

November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts
Andre wrote:
What is “code rate”?

Sory i translate by google :)

I mean code speed.

November 22, 2011

Andre Andre
Robot Herder
6420 posts

In that case: you should probably stick to using a switch, or something that results in a switch like the macro-based version I showed you. Those will probably perform better than the alternatives, though only measurements can of course tell you in the end. Note that if there are differences in the frequency the cases occur, you need to at least sort the cases in that order (most occurring one at the top). Some [eventhelix.com] even suggest to split up the switch in multiple nested blocks. Not nice for readability, but perhaps better for speed (again: measure to be sure).

Edit:
Then again: realize that premature optimization is the root of many programming issues. Are you sure this is your time-critical bottleneck? How did you determine that?

November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts

Program receive messages from devices and do some action with result of switch()
Yes it is maybe not so critical but i assume speed is more important.

November 22, 2011

Andre Andre
Robot Herder
6420 posts

Never assume such things, especially if you are about to sacrifice maintainabiltiy of your code for it.

My first concern is to write code that I (and others) can read and understand later, and can modify if needed later on. Only when profiling shows that a section is time critical, I spend the effort to optimize the design of the code in that area.

November 22, 2011

qxoz qxoz
Area 51 Engineer
1079 posts

Andre wrote:
Never assume such things, especially if you are about to sacrifice maintainabiltiy of your code for it.

My first concern is to write code that I (and others) can read and understand later, and can modify if needed later on. Only when profiling shows that a section is time critical, I spend the effort to optimize the design of the code in that area.

You right. Thank you.
I think i’ll use rokemoon’s solution.
And thank you everybody for respond and advices

Page  
1

  ‹‹ compiler error in calling friend function!!??      [Valgrind] Conditional jump or move depends on uninitialised value on setTransform() ››

You must log in to post a reply. Not a member yet? Register here!