Fharamir (Normal User)
Rookie
Messaggi: 21
Iscritto: 06/05/2011
|
Salve gente,
Ho terminato poco fa un programma che elenca i numeri primi da 19 in poi.
Volevo verificare la sua efficienza mettendolo a confronto con un altro programma molto simile trovato su questo sito.
Il risultato è stato che il programma trovato su questo sito ha battuto 12 a 1 il mio...
Bene, dato che adoro migliorare i miei algoritmi sono andato nello specifico del secondo sorgente a cercare il segreto che custodisce...
Purtroppo la ricerca è stata vana, per questo mi rivolgo a voi.
Il mio codice [scritto in C#] inizia a verificare da 19, tutti i numeri dispari.
Li memorizza in una List
E utilizza quelli memorizzati per verificare i successivi. (controlla solo con i numeri primi).
Termina quindi il controllo del numero se supera la radice quadrata del numero da verificare.
Ho aggiunto in più un "pre-controllo" per escludere i divisori più bassi e più facilmente riconoscibili (2, 3, 5, 7, 9, 11, 13, 17)
Codice sorgente - presumibilmente VB.NET |
List<UInt64> primi = new List<UInt64>(Load()); do { while (!Console.KeyAvailable) { num += 2; P = true; stop = ((UInt64)Math.Sqrt(num)); if (!LastIsFive(num)) if (Sommacifre(num) % 3 != 0) if (ScomponiSette(num) % 7 != 0) if (ScomponiUndici(num) % 11 != 0) if (ScomponiTredici(num) % 13 != 0) if (ScomponiDiciassette(num) % 17 != 0) foreach (UInt64 Primo in primi) { if ((num % Primo) == 0) { P = false; break; } if (Primo >= stop) { break; } } else P = false; else P = false; else P = false; else P = false; else P = false; else P = false; if (P) { primi.Add(num); Console.WriteLine(num); SW.WriteLine(num); }
|
(riporto solo la parte di codice essenziale)
L'altro codice invece [scritto in C] verifica ogni numero (pari compresi),
verifica ogni divisore (numeri non primi compresi)
e anche questo termina il calcolo al raggiungimento della radice quadrata del numero da verificare...
Io non credo che una differenza così grande sia dovuta al linguaggio usato (C# e C)
Forse c'è qualcosa che rallenta molto l'esecuzione del mio, ma non saprei dire cosa...
Secondo voi cosa può essere la causa della differenza?
Grazie
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Stai eseguendo il tuo programma in modalita' Release invece di Debug?
|
|
Fharamir (Normal User)
Rookie
Messaggi: 21
Iscritto: 06/05/2011
|
Si, sto eseguendo il mio direttamente dall'exe compilato senza passare per il compilatore.
|
|
HeDo (Founder Member)
Guru^2
Messaggi: 2765
Iscritto: 21/09/2007
|
Secondo me il problema sta in tutte quelle funzioncine Scomponi* et simila.
Posta quel codice
Ultima modifica effettuata da pierotofy il 27/11/2013 alle 17:11 |
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Postato originariamente da Fharamir:
Si, sto eseguendo il mio direttamente dall'exe compilato senza passare per il compilatore. |
non c'entra da dove lo stai eseguendo, hai compilato in modalita' release?
|
|
Fharamir (Normal User)
Rookie
Messaggi: 21
Iscritto: 06/05/2011
|
Queste sono gli "scomponi"
Codice sorgente - presumibilmente VB.NET |
static Boolean LastIsFive(UInt64 num) { string n = num.ToString(); if (((short)n[n.Length - 1] - 48) == 5) return true; return false; } static UInt64 Sommacifre(UInt64 num) { string n = num.ToString(); if (n.Length == 1) return num; UInt64 total = 0; for (int x = 0; x < n.Length; x++) total += (UInt64)n[x] - 48; return Sommacifre(total); } static UInt64 ScomponiSette(UInt64 num) { string n = num.ToString(); if (n.Length <= 2) return num; UInt64 Unit = (UInt64)n[n.Length - 1] - 48; UInt64 Numero = Convert.ToUInt64(n.Substring(0, n.Length - 1)); if (Numero < (Unit * 2)) return ScomponiSette((Unit * 2) - Numero); return ScomponiSette(Numero - (Unit*2)); } static UInt64 ScomponiUndici(UInt64 num) { string n = num.ToString(); if (n.Length <= 2) return num; UInt64 A = 0; for (int x = 0; x < n.Length; x += 2) A += (UInt64)n[x] - 48; UInt64 B = 0; for (int x = 1; x < n.Length; x += 2) B += (UInt64)n[x] - 48; if (A > B) return A - B; return B - A; } static UInt64 ScomponiTredici(UInt64 num) { string n = num.ToString(); if (n.Length <= 2) return num; UInt64 Unit = (UInt64)n[n.Length - 1] - 48; UInt64 Numero = Convert.ToUInt64(n.Substring(0, n.Length - 1)); return ScomponiTredici(Numero + (Unit * 4)); } static UInt64 ScomponiDiciassette(UInt64 num) { string n = num.ToString(); if (n.Length <= 2) return num; UInt64 Unit = (UInt64)n[n.Length - 1] - 48; UInt64 Numero = Convert.ToUInt64(n.Substring(0, n.Length - 1)); if (Numero < (Unit * 5)) return ScomponiDiciassette((Unit * 5) - Numero); return ScomponiDiciassette(Numero - (Unit * 5)); }
|
mmh... allora non ho capito cosa intendi per "compilato in modalita' release" ...
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
|
|
nessuno (Normal User)
Guru^2
Messaggi: 6405
Iscritto: 03/01/2010
|
Ammesso e non concesso che il codice che hai scritto abbia un senso, è ovvio che sia lentissimo rispetto ad una normale implementazione di un Crivello di Eratostene ... che domanda è ?
Cerca di capire come si scrive effettivamente un programma del genere senza inventare strani meccanismi e chiederti perché questi sono lenti ...
Qualcosa del genere ...
Codice sorgente - presumibilmente C++ |
UInt64 i, j, n=1000; UInt64 [] a = new UInt64[n]; for (i = 2; i<n-1; i++) a[i] = 1; for (i = 2; i < n - 1; i++) if (a[i]>0) for (j = i; (j * i) < n; j++) a[i*j] = 0; for (i = 2; i<n-1; i++) if (a[i]>0) Console.Write(i + " ");
|
è sufficiente ... al posto di quelle millemila linee ...
Ultima modifica effettuata da nessuno il 27/11/2013 alle 20:11
Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti ( uno dei padri fondatori del moderno Calcolo delle probabilità ) chiamava il gioco del Lotto Tassa sulla stupidità. |
|
GN (Member)
Guru
Messaggi: 772
Iscritto: 30/04/2011
|
Postato originariamente da Fharamir:
Si, sto eseguendo il mio direttamente dall'exe compilato senza passare per il compilatore. |
Detta così sembra che modifichi il codice e poi lanci l'exe senza riicompilare... ma non è così vero? |
|