Algoritmo di Zakiya
- Autore discussione Pythoner
- Data d'inizio
- Stato
28 secondi per 200,000,000 come valore nel parametro della funzione
:EDIT:
purtroppo già con questi numeri si arriva ad usare 2GB di memoria virtuale, senza considerare che con numeri più elevati (per esempio 1.000.000.000) non riesce più ad allocare memoria. Al momento semplicemente finisce di aggiungere elementi.
Una possibile soluzione per estendere il numero di elementi è cambiare tipo di lista, ma se non è necessario così va bene
:EDIT:
purtroppo già con questi numeri si arriva ad usare 2GB di memoria virtuale, senza considerare che con numeri più elevati (per esempio 1.000.000.000) non riesce più ad allocare memoria. Al momento semplicemente finisce di aggiungere elementi.
Una possibile soluzione per estendere il numero di elementi è cambiare tipo di lista, ma se non è necessario così va bene
28 secondi a calcolarli e pochissimo di più a scriverli su FILE, mentre a video molto di più.
comunque dimmi più o meno qual'è l'ordine massimo del parametro della funzione, perchè se necessario modifico la lista cercando di far sprecare meno memoria.
comunque dimmi più o meno qual'è l'ordine massimo del parametro della funzione, perchè se necessario modifico la lista cercando di far sprecare meno memoria.
ho modifica il programma cambiando la lista (al momento solo per il c++).
100 secondi per eseguire la funzione passando come parametro 4.000.000.000, con uno spreco massimo di memoria di 1.8GB.
il mio sistema è:
Intel Core 2 Duo T8100 @2.10GHz
Memoria RAM 4GB
Windows a 64bit
Il programma è stato compilato con VisualStudio C++ 2010, senza ottimizzazioni per piattaforme a 32bit. l'ho eseguito in modalità debug e non ha superato il 50% dell'uso del processore (ha usato un core solo in pratica), con priorità normale
100 secondi per eseguire la funzione passando come parametro 4.000.000.000, con uno spreco massimo di memoria di 1.8GB.
il mio sistema è:
Intel Core 2 Duo T8100 @2.10GHz
Memoria RAM 4GB
Windows a 64bit
Il programma è stato compilato con VisualStudio C++ 2010, senza ottimizzazioni per piattaforme a 32bit. l'ho eseguito in modalità debug e non ha superato il 50% dell'uso del processore (ha usato un core solo in pratica), con priorità normale
le ottimizzazioni di gcc o le ottimizzazioni di vc++ non cambiano molto, almeno quelle che non riguardano il s.o.
per la memoria non credo ci siano miglioramenti, in quanto uso la memoria dinamica allocando strutture che hanno dimensione fissa.
per la velocità credo che il massimo si otterrebbe con il compilatore intel e con compilazione 64bit - ovviamente con le ottimizzazioni (per quest'ultimo la memoria richista aumenta perchè i puntatori delle liste sono di 8byte e non di 4byte).
In più il codice C++ usando le classi, riduce le prestazioni di 10 secondi al massimo-se non ho sbagliato nei test (cioè se metto come parametro 4294967295, il codice C ci mette 10 secondi circa in meno)
per la memoria non credo ci siano miglioramenti, in quanto uso la memoria dinamica allocando strutture che hanno dimensione fissa.
per la velocità credo che il massimo si otterrebbe con il compilatore intel e con compilazione 64bit - ovviamente con le ottimizzazioni (per quest'ultimo la memoria richista aumenta perchè i puntatori delle liste sono di 8byte e non di 4byte).
In più il codice C++ usando le classi, riduce le prestazioni di 10 secondi al massimo-se non ho sbagliato nei test (cioè se metto come parametro 4294967295, il codice C ci mette 10 secondi circa in meno)
Ho implementato l'hash (se cos' lo si può chiamare) come un array (x) di 210 elementi.
accedo a x[residues].
Non vedo nessuna difficoltà ... si spreca 210-48 elementi (so che al massimo inserisco 48 elementi), ma su 2GB ^^. In più l'accesso è O(1).
Se vogliamo vedere quell'array come hash, abbiamo che la funzione di hash --> f(x)=x
ma dobbiamo avere come k (elementi dell'hash)=n (possibili elementi assegnabili a x).
In questo esempio n = 211 (residues vanno da 0-minimo valore a 209-massimo valore )
:EDIT:
ci sono altri modi, con lista concatenata, ricerca lineare, doppio hash, ecc.
accedo a x[residues].
Non vedo nessuna difficoltà ... si spreca 210-48 elementi (so che al massimo inserisco 48 elementi), ma su 2GB ^^. In più l'accesso è O(1).
Se vogliamo vedere quell'array come hash, abbiamo che la funzione di hash --> f(x)=x
ma dobbiamo avere come k (elementi dell'hash)=n (possibili elementi assegnabili a x).
In questo esempio n = 211 (residues vanno da 0-minimo valore a 209-massimo valore )
:EDIT:
ci sono altri modi, con lista concatenata, ricerca lineare, doppio hash, ecc.
Ok, se mi descrivete l'algoritmo vedo di scrivere qualcosa di figo in C puro -ansi -pedantic -pedantic-errors che non segfaulti possibilmente xD dai su, sono curioso di cosa riesco a fare su 1Gb di ram e un processore pentium-m@900MHz 
EDIT: whivel, #include <stdint.h>, ci sono vari tipi
int32_t, int64_t, uint32_t, uint64_t, potrebbero farti comodo
EDIT: whivel, #include <stdint.h>, ci sono vari tipi
int32_t, int64_t, uint32_t, uint64_t, potrebbero farti comodo
shura ha detto:Ok, se mi descrivete l'algoritmo vedo di scrivere qualcosa di figo in C puro -ansi -pedantic -pedantic-errors che non segfaulti possibilmente xD dai su, sono curioso di cosa riesco a fare su 1Gb di ram e un processore pentium-m@900MHz
EDIT: whivel, #include <stdint.h>, ci sono vari tipi
int32_t, int64_t, uint32_t, uint64_t, potrebbero farti comodo
dovrei averlo fatto compatibile con il C puro.
sdtint è uno standard solo del C99
wiki ha detto:
Comunque vedrò di usarlo
http://www.megaupload.com/?d=YR57I68T
testato su gcc e g++ (gcc -ansi -pedantic -pedantic-error) e su visual studio c++ 2010 per Windows 32bit su Windows a 64bit
:EDIT:
chiedo scusa se in alcuni casi ho sbagliato a scrivere il nome zakiya...
:EDIT2:
rimane comunque troppo lento^^
http://cr.yp.to/primegen.html
la mia implementazione per 1mld ci mette circa 19 secondi
testato su gcc e g++ (gcc -ansi -pedantic -pedantic-error) e su visual studio c++ 2010 per Windows 32bit su Windows a 64bit
:EDIT:
chiedo scusa se in alcuni casi ho sbagliato a scrivere il nome zakiya...
:EDIT2:
rimane comunque troppo lento^^
http://cr.yp.to/primegen.html
la mia implementazione per 1mld ci mette circa 19 secondi
devi aggiungere il parametro -c in compilazione, altrimenti lo linka, e dopo linkeresti un programma già linkato dal primo comando. (infatti se digiti ./prova.o dovrebbe eseguirsi)
- Stato
DISCUSSIONI SIMILI
- In evidenza
-
- 2
-
- 1K