Algoritmo efficiente C/C++ per limitare tempo di esecuzione programma

Dopo aver visto alcuni esempi su come limitare tempo di esecuzione del codice (C/C++, Python, JavaScript, PHP), in generale, vediamo come farlo nel modo più efficiente, con degli esempi. Il codice l'ho scritto in C, lo stesso concetto può essere ovviamente applicato ovunque.

Nella discussione linkata, il codice di base era questo:

clock_t start = clock();
while((float)(clock()-start)/CLOCKS_PER_SEC < 1){
/* codice da eseguire */
}

Funziona, ma con un problema di fondo: ad ogni iterazione deve controllare la condizione se il tempo di esecuzione sia o meno inferiore ad un secondo. Dato che parliamo potenzialmente di milioni o miliardi di iterazioni, controllarlo ad ogni singola iterazione non ha senso, è uno spreco di risorse computazionali!

Quindi la strada dell'ottimizzazione che ho scelto, si basa su questi punti:

• controlliamo la condizione del tempo di esecuzione ogni 1000/10.000 iterazioni (valore che possiamo aggiustare a seconda del nostro caso specifico!)
• per farlo, possiamo costruire un ciclo infinito con all'interno un ciclo for che procede per step; abbiamo bisogno quindi di una variabile di supporto (oltre ad una variabile incide per il ciclo, ovviamente)
• in questo modo risulta un'efficienza enormemente superiore! Il fatto di controllare il tempo ogni tot iterazioni, comporta che magari non prendiamo il singolo millisecondo (e chissene frega!) ma l'intervallo di tempo sarà quello in cui avvengono le 1000/10.000 iterazioni, il valore scelto; questo significa che il programma può elaborare molto più velocemente le singole operazioni dato che, come detto, non deve essere interrotto ad ogni iterazione per verificare il tempo

Esempio pratico in C - gestione efficiente del tempo di esecuzione

Vediamo i due diversi casi, sempre con tempo di esecuzione limitato ad un secondo (programma semplicissimo che fa x++):

• caso 1: verifica il tempo ad ogni iterazione

  #include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  int main(){
  clock_t start = clock();
  register unsigned long int x=0;
  while((float)(clock()-start)/CLOCKS_PER_SEC < 1){
  x++;
  }
  printf("%ld\n",x);
  return 0;
  }

  Risultato: x=2.455.447
• caso 2: verifica del tempo ogni 10.000 iterazioni

  #include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  int main(){
  clock_t start = clock();
  register unsigned long int x=0;
  register unsigned long int i;
  register unsigned long int step=0;
  while(1){
  for(i=step;i<10000+step;i++){
  x++;
  }
  step++;
  if((float)(clock()-start)/CLOCKS_PER_SEC >= 1){break;}
  }
  printf("%ld\n",x);
  return 0;
  }

  Risultato: x=5.692.590.000

Significa 2300 volte più efficiente!!! Dato che nello stesso tempo di un secondo (più o meno frazioni millesime) il secondo programma ha eseguito circa 5,7 miliardi di operazioni (verificando il tempo ogni 10.000 iterazioni) mentre il primo programma ne ha eseguiti 2,45 milioni vale a dire quindi che il caso ottimizzato è oltre 2000 volte più veloce.
Se prendiamo N=1000 anziché 10.000, si ottengono 3,25 miliardi di iterazioni (sempre a parità di macchina ovviamente). È quindi evidente che seguire una strada di questo tipo, suddividendo in step da 1000, 10.000 o altro che sia, comporta un guadagno enorme nelle prestazioni!