How to improve performance on this code

0

I made the question The Legend of Flavious Josephus but the timeout expired , what I can change to shorten the time

My code

#include <stdio.h>

void carregaVetor(int *vetor, int numero);
void removeNum(int *vetor, int *cont, int *tam, int *indice);
void removeElem(int *vetor, int *posicao, int *tam, int *cont);  
int main(int argc, char** argv)
{

int vetor[90000], cont = 0, tam, indice = 0, posi;
int teste, numero, pulo, i;
while(scanf("%d", &teste) != EOF)
{
    for(i = 0; i < teste; i++)
    {
        scanf("%d %d", &numero, &pulo);
        tam = numero;
        carregaVetor(vetor, numero);
        while(tam != 1)
        {
            cont = posi = indice = 0;
            while(indice != (pulo - 1))
            {
                removeNum(vetor, &cont, &tam, &indice);
            }
            cont = 0;
            while(cont != pulo)
            {
                removeElem(vetor, &posi, &tam, &cont);
            }
        }
        printf("Case %d: %d\n", i + 1 , vetor[0]);
    }
}

  return 0;
}

 void carregaVetor(int *vetor, int numero)
{
   int i;
  for(i = 0; i < numero; i++)
  {
      vetor[i] = i + 1;
  }
}

 void removeNum(int *vetor, int *cont, int *tam, int *indice)
{
   (*tam)++;
   vetor[*tam] = vetor[*indice];
   (*cont)++;
   (*indice)++;
}

 void removeElem(int *vetor, int *posicao, int *tam, int *cont)
{
   int i;
   for(i = (*posicao); i < (*tam); i++)
   {
       vetor[i] = vetor[i + 1];
   }
   (*tam)--;
   (*cont)++;
}
    
asked by anonymous 25.08.2018 / 13:48

1 answer

2

To analyze this code, let's apply some transformations:

  • Correcting the indentation.

  • Place variable declarations in the smallest possible scope.

    • The variable tam can be declared where it receives numero . And this statement can be moved to stay just before while (tam != 1) .

    • The variables numero and pulo can be declared immediately before the scanf that reads them.

    • The variable indice can be declared in the place where zero is assigned to it.

    • Variables i can be declared in for where they are used.

    • The variable posi is only used in while of removeElem . Its value is always set to zero before this while is executed. So we can move your statement to stay immediately before this while . This way, while looks like this:

      int posi = 0;
      while (cont != pulo) {
          removeElem(vetor, &posi, &tam, &cont);
      }
      
    • The variable cont is set to zero before the while of the removeNum where it is used and set to zero again before the while of the removeElem where it is used. In this way, we can exchange for two different variables each declared before their respective while .

      int indice = 0, conta = 0;
      while (indice != pulo - 1) {
          removeNum(vetor, &conta, &tam, &indice);
      }
      
      int contb = 0, posi = 0;
      while (cont != pulo) {
          removeElem(vetor, &posi, &tam, &contb);
      }
      
  • We can copy and paste the body of functions removeElem , removeNum and carregaVetor back to main to make it easier for us to parse and debug the code. The variables i of carregaVetor and removeElem are renamed to j so as not to collide with i already in main . References and dereferences to pointers are eliminated. The result so far is this:

            for (int j = 0; j < numero; j++) {
                vetor[i] = j + 1;
            }
            int tam = numero;
            while (tam != 1) {
                int indice = 0, conta = 0;
                while (indice != pulo - 1) {
                    tam++;
                    vetor[tam] = vetor[indice];
                    conta++;
                    indice++;
                }
                int contb = 0, posi = 0;
                while (contb != pulo) {
                    for (int j = posi; j < tam; j++) {
                        vetor[j] = vetor[j + 1];
                    }
                    tam--;
                    contb++;
                }
            }
    
  • Note that the posi variable always has a value of zero. In fact, the removeElem function read its value from its address, but never wrote in it. So you can delete this variable.

  • Note that the variable conta (which is the cont of your original code when used in while of removeNum ) always has the same value of indice and its value never is used for nothing. Therefore, it can be deleted.

  • We can rewrite the two while s above (those of removeElem and removeNum ) as for loops. The first uses the variable indice as the counter and the second uses contb .

  • Your while (scanf("%d", &teste) != EOF) will only (or should be) run once. In this case, it is not necessary to use while , just use scanf alone. Your problem also does not need to consider malformed entries where the number of NC of the problem statement would not be reported or something, so you do not need to check the return of scanf .

  • Your while (tam != 1) looks like this:

        while (tam != 1) {
            for (int indice = 0; indice != pulo - 1; indice++) {
                tam++;
                vetor[tam] = vetor[indice];
            }
            for (int contb = 0; contb != pulo; contb++) {
                for (int j = 0; j < tam; j++) {
                    vetor[j] = vetor[j + 1];
                }
                tam--;
            }
        }
    
    • Note that tam++ will be executed a number of times that is exactly pulo - 1 . So you can put tam += pulo - 1 after this for and replace vetor[tam] with vetor[tam + indice] .

    • The variable tam is decremented whenever contb is incremented. At this point it is possible to conclude that it will be decremented contb times and it is possible to put tam -= pulo after for of contb . The value of tam in the loop j can be substituted for tam - contb . At this point we'll have this in the code:

          tam += pulo - 1;
          for (int contb = 0; contb != pulo; contb++) {
              for (int j = 0; j < tam - contb; j++) {
                  vetor[j] = vetor[j + 1];
              }
          }
          tam -= pulo;
      
    • We can then change the tam of the loop from j to tam + pulo - 1 , delete tam += pulo - 1; and change tam -= pulo; to tam--; .

    • With this, we can finally change the while (tam != 1) by a for loop.

  • The resulting code looks like this:

    #include <stdio.h>
    
    int main(int argc, char** argv) {
        int vetor[90000];
        int teste;
        scanf("%d", &teste);
        for (int i = 0; i < teste; i++) {
            int numero, pulo;
            scanf("%d %d", &numero, &pulo);
            for (int j = 0; j < numero; j++) {
                vetor[j] = j + 1;
            }
            for (int tam = numero; tam != 1; tam--) {
                for (int indice = 0; indice != pulo - 1; indice++) {
                    vetor[tam + indice] = vetor[indice];
                }
                for (int contb = 0; contb != pulo; contb++) {
                    for (int j = 0; j < tam + pulo - 1 - contb; j++) {
                        vetor[j] = vetor[j + 1];
                    }
                }
            }
            printf("Case %d: %d\n", i + 1, vetor[0]);
        }
    
        return 0;
    }
    

    Looking at the resulting code, we see that it has a high complexity since we have for within a for within a for within a for . The operation that is executed a greater number of times is the vetor[j] = vetor[j + 1]; that is intended to remove an element from the middle of the vector and to move all subsequent elements. In the indice loop, the vetor[tam + indice] = vetor[indice]; statement is also deleting elements from the middle of the vector.

    Vectors are not structures that count on removing elements in the middle as something efficient to do, so it would be best to look for a data structure that has such a characteristic, which suggests that the ideal solution would be done through of dynamically linked (and perhaps circular) lists.

        
    25.08.2018 / 17:25