Problema con il tempo di esecuzione di un programma.

di
Justsniper92
il
16 risposte
J
Justsniper92
Pochi posts
Iscritto da
set, 2023
Messaggi:
6

Problema con il tempo di esecuzione di un programma.

Ciao ragazzi, ho un problema con questo codice, il testo dice:

"Scrivere un codice in C che generi un insieme di numeri random. Si generino tanti numeri in modo tale che sia possibile selezionare da questo set esattamente (e soltanto) 50 numeri primi. Successivamente si ordini il sottoinsieme di 50 numeri primi in ordine decrescente".

Sono riuscito a scrivere il codice, il problema è che ci mette molto tempo per eseguirlo : circa 4 minuti, c'è un modo per renderlo più veloce?

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

#define N 50

int main() {

      int i;
      int j;
      int k;
      int A[N] ;
      int B;
      int cont;
      int div;
      int temp;
      
      div=cont=0;
      k=0;
      
      srand(time(NULL));
      
//GENERAZIONE NUMERI    
   
      do {
            B = rand ()  ;
            for(j=1;j<=B;j++){
                  if(B%j==0)
                        div=div+1;
                              if(div>2)
                                    break;
             }                 
      if (div==2){
            printf("%d\n",B);
                  cont=cont+1;
                        A[k++]=B;
      }            
      div=0;            
      } 
      while(cont!=N);
   
//ORDINAMENTO NUMERI PRIMI
       
     for(i=0;i<N;i++)
            for(j=0;j<N;j++){
                  if( A[j] < A[i] ){
                  temp = A[i];
                  A[i] = A[j];
                  A[j] = temp;
                  }
            }                   

      for (i = 0; i < N ; i++) {
            printf("\nIl %d° numero primo è : %d ",N-i,A[i]);
      } 
}

16 Risposte

  • By65Franco
    By65Franco
    Molto attivo
    Iscritto da
    apr, 2023
    Messaggi:
    1022

    Re: Problema con il tempo di esecuzione di un programma.

    Ciao,

    in quale fase è lento ? 

    nel ciclo for per l'ordinamento dei numeri primi ? 

  • J
    Justsniper92
    Pochi posts
    Iscritto da
    set, 2023
    Messaggi:
    6

    Re: Problema con il tempo di esecuzione di un programma.

    No no, l'ordinamento dei numeri è quasi immediato.

    Mi da problemi nel trovare i numeri primi tra i numeri generati. Avendo numeri molto grandi ( dell'ordine di 10^10 ) ci sta molto a trovare i divisori, pensavo che con il secondo “if” nel ciclo do while avrei risolto, ma non è stato cosi (lo ha migliorato però).

  • J
    Justsniper92
    Pochi posts
    Iscritto da
    set, 2023
    Messaggi:
    6

    Re: Problema con il tempo di esecuzione di un programma.

    No no, l'ordinamento dei numeri è quasi immediato.

    Mi da problemi nel trovare i numeri primi tra i numeri generati. Avendo numeri molto grandi ( dell'ordine di 10^10 ) ci sta molto a trovare i divisori, pensavo che con il secondo “if” nel ciclo do while avrei risolto, ma non è stato cosi (lo ha migliorato però).

  • By65Franco
    By65Franco
    Molto attivo
    Iscritto da
    apr, 2023
    Messaggi:
    1022

    Re: Problema con il tempo di esecuzione di un programma.

    Capito… 

    Allora dovresti semplificare il ciclo for all'interno del do while … prendi la formula e vedi se spacchettabile per ciclare il meno possibile nel for.

    • se il numero random è < 1 ciclare (non è un numero primo)
    • se il numero random è = 2 uscire dal ciclo for (è un numero primo)
    • se il numero random è > 2 ed è “pari” allora ciclare (non è un numero primo) 
    • se il numero random è > di 2 allora verificare la sua radice quadrata… per esempio 
      • for (int i = 3; i <= sqrt(n); i += 2) {  if (n % i == 0) { “non è un numero primo”  }

    A questo punto, escluso i casi sopra elencati, tutti gli altri numeri random sono numeri primi.

    pertanto l'idea per semplificare l'algoritmo si basa esclusivamente nell'individuare velocemente i casi in cui il numero restituito dal random non sia di tipo "Numero Primo" … prova a costruire l'algoritmo in tal senso e verifica le prestazioni.

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21791

    Re: Problema con il tempo di esecuzione di un programma.

    Usa l'algoritmo con la radice quadrata

    https://www.andreaminini.com/informatica/programmazione/algoritmo-dei-numeri-primi

  • A
    amorosik
    Utente Attivo
    Iscritto da
    nov, 2018
    Messaggi:
    254

    Re: Problema con il tempo di esecuzione di un programma.

    Sembra un esercizio di scuola

    Se lo mostri al docente che vai di forza bruta, ti manda dietro la lavagna, sui ceci

    Ad ogni modo, se dal compilatore togli le info debug e attivi qualche ottimizzazione (di solito ci sono dei check da attivare), dovrebbe andare ben piu' rapido

    Su mio pc, quel programma, per 50 valori, gira in 2'10" circa 

    (Ryzen7, consumo cpu al 8% circa, VisualStudio 2008, platform x64, optimize cod=on)

    A naso il grosso del tempo sta su quella rnd() perche' tutto il resto dovrebbe andare via a velocita' warp, verifica se trovi qualcosa di piu rapido per tirare fuori un valore casuale

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21791

    Re: Problema con il tempo di esecuzione di un programma.

    06/09/2023 - Justsniper92 ha scritto:

    circa 4 minuti

    A parte il fatto che anche con il tuo programma impiego 1 o 2 secondi (che compilatore e che PC usi??), comunque:

    considera in partenza casi come 1 e 2 

    escludi tutti i numeri pari 

    fatto questo il ciclo può essere eseguito solo per i dispari

    il ciclo si può fermare alla radice quadrata del valore 

  • J
    Justsniper92
    Pochi posts
    Iscritto da
    set, 2023
    Messaggi:
    6

    Re: Problema con il tempo di esecuzione di un programma.

    Intanto grazie a tutti per i consigli :), ho apportato le modifiche che mi avete consigliato ed effettivamente adesso il programma gira molto più veloce (ci mette circa 2 minuti :|).

    A sto punto penso sia anche un problema di computer non abbastanza potente. Per rispondere alla domanda di Oregon:

    07/09/2023 - oregon ha scritto:

    che compilatore e che PC usi??

    Come pc uso un Macbook pro con Intel Core i5 quad-core, mentre per compilare uso il terminale e lo faccio col comando cc nomefile.c -o nomefile.exe

  • By65Franco
    By65Franco
    Molto attivo
    Iscritto da
    apr, 2023
    Messaggi:
    1022

    Re: Problema con il tempo di esecuzione di un programma.

    07/09/2023 - Justsniper92 ha scritto:

    Intanto grazie a tutti per i consigli :), ho apportato le modifiche che mi avete consigliato ed effettivamente adesso il programma gira molto più veloce (ci mette circa 2 minuti :|).

    Un esempio in C# … potresti prendere spunto e trasformarlo in C … (rispecchia quanto ti avevo riportato nel precedente post)

    50 numeri primi generati random:

    tempo di esecuzione per il ciclo di ricerca dei 50 numeri primi random e ordinamento crescente dell'array : 
    circa 98 millisecondi e in alcuni casi, essendo random il processo, anche meno tempo è necessario, dai 60 ai 70ms ;-))

    Esempio di codice:

            // GENERATES A RANDOM PRIME NUMBERS
        public static void MyRndPrime()
        {
        	// set variable
            int intP = 50;
            int[] aryPrime = new int[intP];
            Random intRnd = new Random();
            int intX = 0;
            // search prime numbers
            do
            {
                int intRndNumber = intRnd.Next();
                if (MyCheckPrime(intRndNumber)) { aryPrime[intX] = intRndNumber; intX++; }
            }
            while (intX < intP);
            // sort array
            Array.Sort(aryPrime);
            // enumerate array
            for (intX = 0; intX < intP; intX++) 
            { Console.WriteLine(aryPrime[intX]); }
        }

        // FIND IF IS A PRIME NUMBER
        static bool MyCheckPrime(int intN)
        {
            // check prime number 
            if (intN <= 1) { return false; }
            if (intN == 2) { return true; }
            if (intN % 2 == 0) { return false; }
            for (int i = 3; i <= Math.Sqrt(intN); i += 2)
            { if (intN % i == 0) { return false; } }
            // default value if prime number 
            return true;
        }
  • By65Franco
    By65Franco
    Molto attivo
    Iscritto da
    apr, 2023
    Messaggi:
    1022

    Re: Problema con il tempo di esecuzione di un programma.

    Ulteriori test:

    Ricercare 1000 numeri primi random: tempo impiegato 1 secondo e 302 millisecondi

    Ricercare 5000 numeri primi random: tempo impiegato 6 secondi e 65 millisecondi

    Mi sembrano tempi accettabili… ;-))

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1238

    Re: Problema con il tempo di esecuzione di un programma.

    Io farei qualcosa del genere:

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

#define N 50

int main()
{
    srand(time(NULL));
    unsigned int v[N];
    for(unsigned int flag, n, i, k = 0; k < N;)
    {
        for(n = rand(), flag = i = 2; i <= n / i && (flag = n % i); i += i == 2 ? 1 : 2);
        if(flag && n)
        {
            v[k++] = n;
            printf("%u:\t%u\n", k, n);
        }
    }
}
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6073

    Re: Problema con il tempo di esecuzione di un programma.

    Scoprire se un numero N e' primo in teoria e' mooolto banale, basta controllare se e' divisibile per uno qualunque dei numeri M<N

    Questo approccio e' per sua natura LENTO: con K numeri devi fare K^2 prove. 

    Ma ci sono un'infinita di ‘trucchi’ per velocizzare questo passo.

    Dal punto di vista ‘teorico' sono tutte cose molto semplici 

    MA

    l'implementazione richiede un po' di pratica. Fondamentalmente e' un suicidio scrivere tutto nel main, bisogna strutturare il programma in diverse funzioni, una delle quali adibita al test di primalita'. 

    Elenco dei trucchi:

    1. non serve scandire i numeri da 2 a N-1, basta farlo da 2 a SQRT(N) (radice quadrata intera!) Pero' bisogna sapere perché! 
    2. non serve scandire tutti i numeri da 2 a SQRT(N), basta usare la tabellina dei numeri primi, anche qui bisogna avere chiaro perche'

    la tabellina te la puoi costruire da codice oppure cercare su internet le tabelline gia' pronte. 

    Anche questa parte richiede un po' di pratica perche' non puoi semplicemente scaricarti un file e scandire il file ogni volta, sarebbe peggio di prima. 

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1238

    Re: Problema con il tempo di esecuzione di un programma.

    07/09/2023 - migliorabile ha scritto:

    non serve scandire i numeri da 2 a N-1, basta farlo da 2 a SQRT(N) (radice quadrata intera!)

    In realtà non serve calcolare esplicitamente la radice quadrata, è infatti sufficiente utilizzare la condizione:

    i <= n / i

    dove “n” è il numero che stiamo testando e "i" il generico divisore. 
    Inoltre la suddetta divisione risulta quasi a costo zero visto che dopo dobbiamo comunque utilizzare l'operatore modulo con gli stessi operandi.

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6073

    Re: Problema con il tempo di esecuzione di un programma.

    Si, si potrebbe fare anche cosi'. 

    L'operazione non e' accosto zero, ma ti costa come il modulo, quindi e' come fare 2 divisioni. 

    In ogni caso, per un esercizio scolastico, chissene ;-)

Devi accedere o registrarti per scrivere nel forum
16 risposte