Optimization of multiple ifs into something more practical

Asked

Viewed 259 times

3

I have a string alphabetical:

char string[] = "aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";

I want to go through it all and for every character of it, say how many times it repeats in the string.

Example:

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

struct Quantidade{
   int qtd;
};

char string = 
"aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";


int main(){
     struct Quantidade vetor[];

     for(i=0; i<strlen(string); i++{
        if(string[i] == 'a'){
            vetor[0].qtd++;    
        } 
        else if(string[i] == 'b'){
            vetor[1].qtd++;
        }
        ...
        else if(string[i] == 'z'){
             vetor[25].qtd++;
        }
     }

   return 0;
 }

Instead of using 26 ifs within the code, as I can do more optimally?

  • Ever heard of switch?

  • 1

    Without creating too complex a data structure, the simplest solution is to create a array for each option and increment based on calculation with the character. Can only lower case letters? There the array will have 26 positions. I’ll see if I can fix it in a little while.

  • can be also, I just wonder if there is another logic with loop so as not to be using 26 ifs...

2 answers

9


If only lower case letters can make one array with 26 positions and keep in them according to what you find.

In *string - 'a' is a calculation to find out the position of the array. You can almost always use math to help simplify algorithms. So I take the content pointed by the pointer string which is the character of that step, it will be evaluated according to the ascii table. Then the a is code 97, we don’t want that, we want 0, so it’s simple, we subtract 97, but to be more readable we subtract the own a which is worth 97. And if the character is d, not 100 - 97 gives 3, so the element used will be how much of array. Everything works out.

When using to restore the character you have to add the 97 again.

Thus:

#include <stdio.h>

int main() {
    char *string = "aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";
    int quantidade[26] = { 0 }; //inicializa todos elementos zerados
    for (; *string != '\0'; string++) { //termina quando chegar no nulo que é fim de string
        quantidade[*string - 'a']++; //incrementa conteúdo apontado por string - código 'a'
    }
    for (int i = 0; i < 26; i++) {
        printf("%c => %d\n", i + 'a', quantidade[i]); //soma 'a' pra ter o caractere correto
    }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

If you can have other characters, just increase the number of positions in the array to fit all and count the character always using the first possible.

This does not work if you can have separate character ranges. This algorithm only works for a single track of any size.

If you want you can filter the ones with 0 not to print in the list, this is very easy.

This algorithm does the same as the question.

But if zeroes can’t even be on array, then you will have to create a more complex structure where you store the character and its sum, only when it reaches at least 1. And there will have to be a search algorithm in this *array8 that can be linear, logarithm or constant depending on how much assurance of performance and acceptable complexity. It’s much more complicated to do this.

Note that I avoided the use of strlen() which is not the most appropriate. So I walk the pointer (string++) in each character and checks whether came to the end. If you have difficulty reading this see pointer operators.

I almost did with while, I think it was the best in this case.

  • Dude, this is exactly what I wanted. Although I haven’t understood the logic yet, I’ll even save it on my github as well for future revisions. Brawl @bigown :D

  • I’ll explain it better later :)

  • Very good logic, as always; the only thing that would do otherwise would be to create a second pointer to traverse the string, since in real cases you will probably want to keep a reference to the principle of it to use it again...

  • @Wtrmute I thought to do this, for an exercise is fine like this, in a real code I would actually need.

0

#include <string.h>   // strlen()
//#include <stdio.h>

#define NUM_ALPHA 26
struct Quantidade{
   int qtd;
};

//char string =
//"aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";
char string[] =
"aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";

int main(){
     //struct Quantidade vetor[];
     struct Quantidade vetor[ NUM_ALPHA ];

     for( int i=0; i<NUM_ALPHA; i++ )
     {
         vetor[ i ].qtd = 0;  // initialize
     }

     // for(i=0; i<strlen(string); i++{
     for( size_t i=0; i<strlen(string); i++ )
     {
        //if(string[i] == 'a'){
        //    vetor[0].qtd++;
        //}
        //else if(string[i] == 'b'){
        //    vetor[1].qtd++;
        //}
        //...
        //else if(string[i] == 'z'){
        //     vetor[25].qtd++;
        //}
        vetor[ string[i] - 'a' ].qtd++;
     }

   return 0;
 }
  • @Jeffersonquesado, se, array of 26

  • @Jeffersonquesado, OP wanted to use a structure

  • understood. I had focused more on the problem (excess of ifs), so I ended up ignoring that detail. I will remove my comments after spending time in the cone of shame

Browser other questions tagged

You are not signed in. Login or sign up in order to post.