Sfida di programmazione in c\c++
lancio una sfida:
creare un programma in c\c++ che calcoli tutti i numeri primi da 1 fino ad 1 000 000 nel minor tempo possibile.
la mia versione ci riesce in 16 secondi
qualcuno riesce a battermi?
(scrivete il codice come risposta ed io controllerò il tempo di esecuzione
).
creare un programma in c\c++ che calcoli tutti i numeri primi da 1 fino ad 1 000 000 nel minor tempo possibile.
la mia versione ci riesce in 16 secondi
qualcuno riesce a battermi?
(scrivete il codice come risposta ed io controllerò il tempo di esecuzione
).
Risposte
"gianpierovignola":
lancio una sfida:
...
qualcuno riesce a battermi?
E' una bella idea! Se ho un po' di tempo ci provo!
Decisamente poco efficiente, sono sicuro si possa fare in meno di un secondo. Hai usato il metodo naif? 16 secondi sono davvero tantissimi per solo un 1000000 di casi. Comunque vedo di scrivere velocemente un programmino e lo posto. Evito però i metodi più efficienti in assoluto però, non sono facili da scrivere.
42 secondi per trovare il più grande primo minore di 100 milioni (99999989), usando Eratostene. Per un milione basta infatti un secondo.
#include <vector>
#include <iostream>
#include <algorithm>
#include <ctime>
struct Timer
{
inline Timer(std::ostream & stream)
: stream(stream), start(std::time(0))
{
}
inline ~Timer()
{
std::time_t end = std::time(0);
long totalSeconds = static_cast<long>(std::difftime(end, start));
long seconds = totalSeconds;
int hours = 0, minutes = 0;
if (seconds > 120) {
minutes = seconds / 60;
seconds %= 60;
if (minutes > 60) {
hours = minutes / 60;
minutes %= 60;
}
}
stream << "Elapsed time: ";
if (minutes > 0) {
if (hours > 0) {
stream << hours << " hours, ";
}
stream << minutes << " minutes, ";
}
stream << seconds << " seconds" << '\n';
stream << std::endl;
}
private:
std::ostream & stream;
const std::time_t start;
};
template <typename T>
inline T findLargestPrimeLessThan(const T Max)
{
std::vector<bool> primes(Max, true);
primes[0] = false;
primes[1] = false;
std::cout << "Computing primes up to " << Max << std::endl;
{
Timer t(std::cout);
for (T i = 2; i < Max; ++i) {
if (primes[i]) {
for (T j = 2*i; j < Max; j += i) {
primes[j] = false;
}
}
}
}
return -1 + primes.size() - std::distance(
primes.rbegin(),
std::find(primes.rbegin(), primes.rend(), true));
}
int main()
{
const int largestPrime = findLargestPrimeLessThan<int>(100000000);
std::cout << "Largest computed prime: " << largestPrime << '\n';
}
Dato che scrivere tutti i primi in un file mi occupava il 99% del tempo, ho deciso di limitarmi a stampare a video il più grande ed identificare tutti gli altri (il mio codice ti permette di scrivere tutti i primi fino a quel numero volendo*).
Io ho usato C++11 (ma solo per utilizzare chrono e non dover, come claudio, scriverne una mia versione). Comunque il mio crivello di eratostene "quasi" standard ci ha messo solo 4,664 secondi (in release, lanciato dalla Power Shell di Windows e compilato con Visual Studio 2012) per trovare il massimo fino 100'000'000. Non so come mai quello di Claudio sia così lento.
fino ad un millione penso bastino meno di 100ms.
Volendo potrei modificarla come una classe template e mettere questo codice nel costruttore. Sarebbe una classe per controllare la primalità con complessità costante per determinare la primalità e complessità lineare per trovare l'n-esimo primo (ci sono delle migliorie che possono abbassare questo valore). Diventerebbe almeno più utile di così
.
* non sono però scritti su un array ma sono identificati come true nell'array globale. Riscriverli in un array non penso mi occuperebbe particolarmente più tempo.
Io ho usato C++11 (ma solo per utilizzare chrono e non dover, come claudio, scriverne una mia versione). Comunque il mio crivello di eratostene "quasi" standard ci ha messo solo 4,664 secondi (in release, lanciato dalla Power Shell di Windows e compilato con Visual Studio 2012) per trovare il massimo fino 100'000'000. Non so come mai quello di Claudio sia così lento.
#include <vector>
#include <cstdint>
#include <chrono>
#include <iostream>
int main()
{
uint64_t const Max = 100000000;
std::vector<bool> num_list(Max, false);
uint64_t max_prime = 5;
std::chrono::time_point<std::chrono::system_clock> start, end; // C++11
start = std::chrono::system_clock::now(); // C++11
// eliminazione multipli di 2 e 3
num_list[1] = true; // 2 e' primo
num_list[2] = true; // 3 e' primo
for(uint64_t i = 4, step = 4; i < Max; i+=step)
{
step = (step == 4)? 2 : 4;
num_list[i] = true;
}
for(uint64_t i = 4, step = 4; i < Max; i+=step)
{
step = (step == 4)? 2 : 4;
if(num_list[i] == true)
{
max_prime = i+1;
for(uint64_t j = 2*i+1; j < Max; j += max_prime)
{
num_list[j] = false;
}
}
}
end = std::chrono::system_clock::now(); // C++11
int64_t time_el = std::chrono::duration_cast<std::chrono::milliseconds> (end-start).count(); // C++11
std::cout<< "L'algoritmo ha identificato " << max_prime << "come il più grande primo fino a ";
std::cout<< Max << " in " << (time_el * 0.001) << "s"<<std::endl;
return 0;
}fino ad un millione penso bastino meno di 100ms.
Volendo potrei modificarla come una classe template e mettere questo codice nel costruttore. Sarebbe una classe per controllare la primalità con complessità costante per determinare la primalità e complessità lineare per trovare l'n-esimo primo (ci sono delle migliorie che possono abbassare questo valore). Diventerebbe almeno più utile di così
.* non sono però scritti su un array ma sono identificati come true nell'array globale. Riscriverli in un array non penso mi occuperebbe particolarmente più tempo.
Ma questa non è una sfida, è un semplice esercizio di implementazione di un crivello di qualche tipo. Rilancio con qualcosa di più complicato. Si trovino i 1000 primi che precedono \(10^10.\) Il programma deve funzionare anche su sistemi a 32 bit (niente allocazioni di qualche GB insomma..).
"vict85":
Non so come mai quello di Claudio sia così lento.
Chi ci ha pensato ad abilitare le ottimizzazioni…?
Facendolo arrivo a circa 5.5 secondi, che è paragonabile al tempo che ottieni tu.Avevo copiaincollato il mio timer da un vecchio progetto, in effetti con chrono c'è una risoluzione migliore.
Usando un bool* invece di un std::vector
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <chrono>
#include <ctime>
struct Timer
{
inline Timer(std::ostream & stream)
: stream(stream),
start(Clock::now())
{
}
inline ~Timer()
{
const TimePoint end = Clock::now();
auto duration =
std::chrono::duration_cast<Resolution>(end - start).count();
stream << "Elapsed time: " << duration * 0.001 << " seconds"
<< std::endl;
}
private:
typedef std::chrono::system_clock Clock;
typedef std::chrono::time_point<Clock> TimePoint;
typedef std::chrono::milliseconds Resolution;
std::ostream & stream;
const TimePoint start;
};
template <typename T>
inline T findLargestPrimeLessThan(const T Max)
{
std::vector<bool> primes(Max, true);
primes[0] = false;
primes[1] = false;
std::cout << "Computing primes up to " << Max << std::endl;
{
Timer t(std::cout);
for (T i = 2; i < Max; ++i) {
if (primes[i]) {
for (T j = 2*i; j < Max; j += i) {
primes[j] = false;
}
}
}
}
return Max - 1 - std::distance(
primes.rbegin(),
std::find(primes.rbegin(), primes.rend(), true));
}
template <typename T>
inline T to(const std::string & s)
{
std::istringstream stream(s);
T t;
stream >> t;
return t;
}
int main(int argc, char *argv[])
{
typedef int Type;
const Type Max = argc <= 1
? 10000000
: to<Type> (argv[1]);
const Type largestPrime = findLargestPrimeLessThan<Type>(Max);
std::cout << "Largest computed prime: " << largestPrime << '\n';
}
L'essere più compatto porta certamente ad un migliore uso della cache e ad una minore necessità di riallocare e copiare. La copia è inoltre forse più veloce. Non c'è infatti alcuna ragione per non specializzare in modo opportuno la copia per rendere possibile l'utilizzo di SSE et similia. Ma ripeto.. Secondo me, non si tratta di una vera sfida. Si può ridurre ancora il tempo eliminando i pari dall'array e volendo pure i multipli di 3. Poi si poteva riscrivere l'algoritmo nella sua versione cache oblivious. Ma per solo un milione è un esercizio fine a se stesso.
Sì, notavo semplicemente la differenza di tempo tra std::vector e T*, quando nella quasi totalità dei casi sono costrutti letteralmente identici, quindi il tempo di esecuzione dovrebbe essere uguale (l'unica eccezione è appunto quando T = bool, per una controversa specializzazione definita nello standard).
Soltanto per curiosità, con una migliore selezione degli elementi da controllare ed eliminando in anticipo tutti gli elementi multipli di 2, 3 e 5, il mio codice ci mette la metà del tempo per 10^8 (per 10^6 ci mette meno di 10ms ma anche prima non ci metteva molto).
Ora però il codice è molto più difficile da comprendere.
#include <vector>
#include <cstdint>
#include <chrono>
#include <iostream>
int main()
{
uint32_t const Max = 100000000;
//uint32_t const Max = 1000000;
std::vector<bool> num_list(Max, true);
uint32_t max_prime;
uint32_t step_index[] = { 6 , 4, 2, 4, 2, 4, 6, 2 };
std::chrono::time_point<std::chrono::system_clock> start, end; // C++11
start = std::chrono::system_clock::now(); // C++11
// eliminazione multipli di 2, 3 e 5
num_list[1] = true; // 2 e' primo
num_list[2] = true; // 3 e' primo
num_list[4] = true; // 5 e' primo
for(uint32_t i = 6, stp = 1; i < Max; i += step_index[stp++], stp %= 8)
{
num_list[i] = true;
}
for(uint32_t i = 6, stp = 1; i < Max; i += step_index[stp++], stp %= 8)
{
if(num_list[i] == true)
{
max_prime = i+1;
uint32_t k;
switch(stp)
{
case 0:
case 2:
case 5:
case 7:
k = 0;
break;
default:
k = 5;
}
for(uint32_t j = (max_prime*max_prime -1); j < Max; j += step_index[k++]*max_prime, k %= 8)
{
num_list[j] = false;
}
}
}
end = std::chrono::system_clock::now(); // C++11
int64_t time_el = std::chrono::duration_cast<std::chrono::milliseconds> (end-start).count(); // C++11
std::cout<< "L'algoritmo ha identificato " << max_prime << " come il piu' grande primo fino a ";
std::cout<< Max << " in " << (time_el * 0.001) << "s"<<std::endl;
int32_t i;
std::cin >> i;
return 0;
}Ora però il codice è molto più difficile da comprendere.
Whao!! devo dire che siete tutti più bravi di me io sono un dilettante grazie a tutti per le proposte anche se non ho capito tutte le righe di codice.
perciò lancio una sfida più precisa che si adatta alle mie conoscenze per poter capire bene il codice:
1) il programma può contenere solo le librerie che conosco : (math.h) - (stdio.h) - (stdlib.h) -
2)il programma può contenere solo variabili di tipo int, char, string (c++) sono ammessi anche vettori e matrici.
(magari per voi queste prime 2 regole sono poco efficenti ma questo è il mio mondo se usate altro non ci capirei niente, poi voglio vedere cosa dei programmatori più esperti riescono a fare con poco)
3) il programma deve dare in output tutti i numeri che calcola (non solo l'ultimo) e l'output deve essere di tipo standard (schermata nera con scritte bianche in parole povere)
4) il programma parte da 1 e si ferma a 999983
5) il programma lo devo poter copiare e incollare nel mio compilatore per poi compilarlo senza che mi dia errori (con alcuni dei codici che avete scritto sopra spesso mi dava errori che non sono riuscito a decifrare)
6) il mio processore è un intel(R) Core(TM) i5-2320 CPU @ 3.00GHz sistema operativo: Windows 7 ultimate 64 bit
spero di non essere troppo esigente...
perciò lancio una sfida più precisa che si adatta alle mie conoscenze per poter capire bene il codice:
1) il programma può contenere solo le librerie che conosco :
2)il programma può contenere solo variabili di tipo int, char, string (c++) sono ammessi anche vettori e matrici.
(magari per voi queste prime 2 regole sono poco efficenti ma questo è il mio mondo se usate altro non ci capirei niente, poi voglio vedere cosa dei programmatori più esperti riescono a fare con poco)
3) il programma deve dare in output tutti i numeri che calcola (non solo l'ultimo) e l'output deve essere di tipo standard (schermata nera con scritte bianche in parole povere)
4) il programma parte da 1 e si ferma a 999983
5) il programma lo devo poter copiare e incollare nel mio compilatore per poi compilarlo senza che mi dia errori (con alcuni dei codici che avete scritto sopra spesso mi dava errori che non sono riuscito a decifrare)
6) il mio processore è un intel(R) Core(TM) i5-2320 CPU @ 3.00GHz sistema operativo: Windows 7 ultimate 64 bit
spero di non essere troppo esigente...
Di quale compilatore si tratta? Vorrei solo farti notare che visto il problema, l'output su console sarà illeggibile e dominerà il tempo di esecuzione. Quello che vedrai non sarà il tempo per calcolare i numeri primi, ma il tempo per stamparli tutti.
"gianpierovignola":
1) il programma può contenere solo le librerie che conosco :(math.h) - (stdio.h) - (stdlib.h) -
2)il programma può contenere solo variabili di tipo int, char, string (c++) sono ammessi anche vettori e matrici.
(magari per voi queste prime 2 regole sono poco efficenti ma questo è il mio mondo se usate altro non ci capirei niente, poi voglio vedere cosa dei programmatori più esperti riescono a fare con poco)
In realtà il nucleo dei nostri programmi segue quasi queste regole, il resto serve per calcolare il tempo necessario e memorizzare in liste/vettori i numeri generati.
Ecco una versione "ripulita":
#include <vector>
#include <iostream>
void findAllPrimesLessThan(const int Max)
{
std::vector<bool> primes(Max, true);
primes[0] = false;
primes[1] = false;
std::cout << "Computing all primes less than " << Max << ":" << '\n';
for (int i = 2; i < Max; ++i) {
if (primes[i]) {
for (int j = 2*i; j < Max; j += i) {
primes[j] = false;
}
}
}
for (int i = 0; i < Max; ++i) {
if (primes[i]) {
std::cout << i << '\n';
}
}
}
int main()
{
const int Max = 1000;
findAllPrimesLessThan(Max);
}
Nota che ho usato lo stesso un std::vector
"gianpierovignola":
3) il programma deve dare in output tutti i numeri che calcola (non solo l'ultimo) e l'output deve essere di tipo standard (schermata nera con scritte bianche in parole povere)
Scrivere in output è un'operazione molto costosa, il motivo per cui l'abbiamo evitato era per diminuire il tempo di esecuzione. Comunque abbiamo generato tutti i numeri, basta stamparli alla fine.
"gianpierovignola":
5) il programma lo devo poter copiare e incollare nel mio compilatore per poi compilarlo senza che mi dia errori (con alcuni dei codici che avete scritto sopra spesso mi dava errori che non sono riuscito a decifrare)
Abbiamo usato chrono, che è un componente della libreria standard della versione più recente C++11. Se usi GCC devi specificare la versione da usare:
g++ -std=c++98 -pedantic primes.cpp # Usa C++ standard 1998 g++ -std=c++0x -pedantic primes.cpp # Usa C++ standard 2011 (vecchie versioni di GCC) g++ -std=c++11 -pedantic primes.cpp # Usa C++ standard 2011 g++ primes.cpp # Usa C++ NON STANDARD!!!
P.S.
1 non è un numero primo.
Trovo un po' difficile usare i vector senza includere , inoltre sicuramente cmath è inutile.
Data la natura, quasi didattica, del tuo esercizio direi di trasformare questa discussione in una lista di problemi di questo tipo per chi volesse cimentarsi nella programmazione.
Propongo due problemi basati sul crivello.
PROBLEMA 1:
Usare un metodo basato sul crivello di eratostene per trovare l'n-esimo primo. Il numero n è inserito dall'utente e deve essere inferiore a 1'000'000 (se è superiore richiedere il numero).
ATTENZIONE: non basta applicare la nostra versione del crivello!
PROBLEMA 2:
Usare un metodo basato sul crivello di eratostene per trovare la funzione totiente di n. Il numero n è inserito dall'utente e deve essere inferiore a 1'000'000 (se è superiore richiedere il numero).
Entrambi i problemi non sono facilissimi comunque.
Data la natura, quasi didattica, del tuo esercizio direi di trasformare questa discussione in una lista di problemi di questo tipo per chi volesse cimentarsi nella programmazione.
Propongo due problemi basati sul crivello.
PROBLEMA 1:
Usare un metodo basato sul crivello di eratostene per trovare l'n-esimo primo. Il numero n è inserito dall'utente e deve essere inferiore a 1'000'000 (se è superiore richiedere il numero).
ATTENZIONE: non basta applicare la nostra versione del crivello!
PROBLEMA 2:
Usare un metodo basato sul crivello di eratostene per trovare la funzione totiente di n. Il numero n è inserito dall'utente e deve essere inferiore a 1'000'000 (se è superiore richiedere il numero).
Entrambi i problemi non sono facilissimi comunque.
"apatriarca":
Ma questa non è una sfida, è un semplice esercizio di implementazione di un crivello di qualche tipo. Rilancio con qualcosa di più complicato. Si trovino i 1000 primi che precedono \(10^10.\) Il programma deve funzionare anche su sistemi a 32 bit (niente allocazioni di qualche GB insomma..).
Ecco, questo è più interessante. La soluzione è quasi banale, una volta che si è capito il trucco.
Io riesco a calcolarli in circa 0.28 secondi. in 6 secondi trovo i 1000 primi che precedono \(10^{13}\).
Nota che con tutta probabilità \(10^{10}\) non è rappresentabile con int o long int in C e C++. Bisognerà usare un long long int, o eventualmente limitarsi a \(10^9\) .
L'algoritmo naif è qualcosa del genere:
for p in [Max-N ... Max]
for i in [2 ... p-1]
if i divides p == 0
Not Prime
Continue with next p
end
p is prime
end
endIl trucco è modificare l'intestazione del ciclo interno (quello con la i).
Un paio di suggerimenti:
Infine il codice (C++11, vale quello che ho detto nel post precedente).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo