Recently did an online programming assessment, where the question was essentially "search a number for specified integers and increment a count".

My solution was to convert the given number to a string, and then search through the string using a for loop and a switch statement. So basically:

for (int i = 0; i < str.length(); i  ;)
{
    switch(str[i]) {
      case  '1':
       count  ;
      case  '4': 
       count  ;
      case  '8': 
       count  ;
       // etc
    }
}

What I'm wondering is, is this an inefficient way of accomplishing this? I believe the time complexity is O(n), but I could be wrong. If it is inefficient, what is a better solution?

**Edited for clarification, added cases '4' and '8'

CodePudding user response：

switch is generally not inefficient; internally it is typically implemented either as a jump-table to the various options, or as a binary search, or as a series of if-then statements, depending on what the compiler/optimizer thinks will execute fastest.

However, you could gain some efficiency in this case by avoiding the switch/case block altogether and using a lookup-table instead, like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int, char **)
{  
   const int BUFSIZE=1024*1024*10;  // 10MB
   
   char * str = new char[BUFSIZE];
   for (int i=0; i<BUFSIZE; i  ) str[i] = (rand()7) 1;
   str[BUFSIZE-1] = '\0';
      
   unsigned char mask[256];
   memset(mask, 0, sizeof(mask));
   mask['1'] = 1;
   mask['4'] = 1;
   mask['8'] = 1;

   for (int i=0; i<BUFSIZE; i  ) if (mask[(unsigned)str[i]] != 0) count  ;

   printf("count=%i\n", count);
   return 0;
}

On my computer, doing it this way executed a little more than twice as quickly than the original (switch-based) approach did.

CodePudding user response：

Is searching a string using a switch inside a for loop inefficient?

In general, no.

What I'm wondering is, is this an inefficient way of accomplishing this?

Firstly, the switch is unnecessarily complex. An if statement is simpler:

if (str[i] == '1')
    count  ;

What about when there are multiple numbers to be matched?

Then a switch is probably more readable, but your example is broken since it counts 1 and 4 more than once. Fixed code:

switch(str[i]) {
  case  '1':
  case  '4': 
  case  '8': 
     count  ;
}

Secondly, this is probably not optimal. It will probably be a bit faster to repeatedly use remainder operator to get the least significant digit and divide by 10, and compare the digit. This is essentially part of what the string conversion function is doing internally.

To compare asymptotic complexity, this has same time complexity as your solution, O(log N) where N is the size of the integer. The size complexity is constant while your solution requires O(log N) for the string storage. Note that the comparison of asymptotic complexity is mostly irrelevant if you use this with primitive integers due to their limited range. This matters for arbitrary precision arithmetic.

Another potential optimisation is to not use a branch in the loop, but instead to count the frequency of all integers, and in the end loop the frequencies and switch only in that loop. Benchmarking will tell if this is faster.