|
|
|
|
Strumenti |
14-10-2008, 23:00 | #81 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Prima di andare a nanna ho preso i tempi con i file grossi indicati da repne. Mi sa che sarà dura batterla:
2.687 secondi contro i 125.765 secondi della versione di Mesh. |
15-10-2008, 01:28 | #82 |
Senior Member
Iscritto dal: Oct 2001
Messaggi: 11471
|
Non riesco a prendere sonno così mi sono messo a fare qualche modifica. La nuova versione è circa il 39% più veloce.
Codice:
def benchmark(label) print "#{label}..." start_time = Time.now result = yield puts " completato. (#{(Time.now - start_time).to_s} secondi)" result end def compress(values) c = 0 values.each do |x| c |= 1 << x end c end def load_data(file_name) data = Array.new File.open(file_name, 'r') do |file| file.gets; file.gets # ignora le prime due righe while line = file.gets date, wheel, values = line.chop.split values = values.split(',').map { |x| x.to_i } data << { date: date, wheel: wheel, values: values, c: compress(values) } end end data end def load_find(file_name) data = Array.new File.open(file_name, 'r') do |file| file.gets # ignora la prima riga while line = file.gets values = line.chop.split(',').map { |x| x.to_i } data << { values: values, c: compress(values) } end end data end def search(data, find) find.each do |r| puts "-- #{r[:values].inspect} --" data.each do |e| puts "#{e[:date]} #{e[:wheel]} #{e[:values].inspect}" if (e[:c] & r[:c]) == r[:c] end end end data = benchmark('Caricamento delle estrazioni') { load_data('LottoDataSemplice.txt') } find = benchmark('Caricamento delle ricerche') { load_find('LottoFindSemplice.txt') } benchmark('Ricerca dei valori') { search(data, find) } |
15-10-2008, 02:00 | #83 | |
Senior Member
Iscritto dal: Jul 2002
Città: Reggio Calabria -> London
Messaggi: 12075
|
Quote:
..però ho potuto dedicarci solo un pò di tempo stasera prima di uscire e non ho trovato niente che faccia al caso mio.. ah.. ovviamente il mio primo algoritmo da 8 secondi sotto macchina virtuale non faceva altro che creare un'hashmap usando come chiave l'estratto e inserendo la lista di ruote come valore e facendo le intersezioni tra i vari insiemi ottenuti.. Ma ovviamente è un ordine di grandezza + lento di quello che sto cercando di tirare fuori... (anche se c'è da dire che in 25-30 minuti avevo risolto in quel modo il difficile di gugoxx in 11 secondi dato che c'erano un pò di ridondanze )
__________________
|
|
15-10-2008, 06:52 | #84 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:04. |
15-10-2008, 12:11 | #85 |
Senior Member
Iscritto dal: Dec 2005
Messaggi: 7077
|
@rеpne scasb
scusa la domanda ma.. il tuo algoritmo funziona se il numero di valori per ogni estrazione è diverso da 6? |
15-10-2008, 12:47 | #86 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:05. |
15-10-2008, 13:10 | #87 | |
Member
Iscritto dal: Dec 2006
Messaggi: 198
|
Quote:
Cmq sono ancora allibito dai tempi della tua soluzione, sembra una magia, che complessità ha? |
|
15-10-2008, 14:18 | #88 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Classifica aggiornata:
Ho escluso per il momento k0nt3. Aspettiamo che aggiusti l'output. Magix, per quel problema con Eclipse che ti avevo segnalato, sai dirmi niente? Ultima modifica di Vincenzo1968 : 15-10-2008 alle 14:23. |
15-10-2008, 14:21 | #89 | |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Quote:
so che ti sto scassando i cabasisi ma mi da errore. Puoi azzizzarmelo per la versione 1.8.7? Questo è il codice(non mi cambiare i percorsi dei file): Codice:
def benchmark(label) print "#{label}..." start_time = Time.now result = yield puts " completato. (#{(Time.now - start_time).to_s} secondi)" result end def compress(values) c = 0 values.each do |x| c |= 1 << x end c end def load_data(file_name) data = Array.new File.open(file_name, 'r') do |file| file.gets; file.gets # ignora le prime due righe while line = file.gets date, wheel, values = line.chop.split values = values.split(',').map { |x| x.to_i } data << { date: date, wheel: wheel, values: values, c: compress(values) } end end data end def load_find(file_name) data = Array.new File.open(file_name, 'r') do |file| file.gets # ignora la prima riga while line = file.gets values = line.chop.split(',').map { |x| x.to_i } data << { values: values, c: compress(values) } end end data end def search(data, find) find.each do |r| puts "-- #{r[:values].inspect} --" data.each do |e| puts "#{e[:date]} #{e[:wheel]} #{e[:values].inspect}" if (e[:c] & r[:c]) == r[:c] end end end #data = benchmark('Caricamento delle estrazioni') { load_data('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoPiccolo\LOTTO.D1') } #find = benchmark('Caricamento delle ricerche') { load_find('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoPiccolo\LOTTO.D2') } data = benchmark('Caricamento delle estrazioni') { load_data('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoGrosso\LOTTO.D1') } find = benchmark('Caricamento delle ricerche') { load_find('C:\Scaricamenti\Temp\Gugo\Contest 07 - Il Lotto\LottoGrosso\LOTTO.D2') } benchmark('Ricerca dei valori') { search(data, find) } |
|
15-10-2008, 15:08 | #90 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:05. |
15-10-2008, 15:14 | #91 | |
Member
Iscritto dal: Dec 2006
Messaggi: 198
|
Quote:
Ho buttato giù di un po' i tempi, anche se non dovrei arrivare nemmeno vicino a repne Codice:
#include <iostream> #include <bitset> #include <string> #include <vector> #include <ctime> using namespace std; struct Ruota { bitset<96> bitmask; string* data,* luogo; char* numeri; }; vector<Ruota> ruote; vector<int> indexed[91]; int lens[91]; int main() { FILE* fin = fopen("fin.txt", "r"); FILE* rin = fopen("rin.txt", "r"); FILE* out = fopen("out.out", "w"); int r, v, f, daCercare[9], index=0; char s[100]; clock_t start = clock(); fscanf(rin, "%s %d\n", s, &r); fscanf(rin, "%s %d\n", s, &v); fscanf(fin, "%s %d\n", s, &f); //Lettura ruote ruote.reserve(100010); lens[0] = 2000000000; while (!feof(rin)) { Ruota ruota; int n; ruota.numeri = new char[v]; fscanf(rin, "%s", s); ruota.data = new string(s); fscanf(rin, "%s", s); ruota.luogo = new string(s); for (int i = 0; i < v-1; i++) { fscanf(rin, "%d,", &n); ruota.bitmask[n] = 1; ruota.numeri[i] = (char)n; indexed[n].push_back(index); } fscanf(rin, "%d\n", &n); ruota.bitmask[n] = 1; ruota.numeri[v-1] = (char)n; indexed[n].push_back(index); ruote.push_back(ruota); index++; } for (int i = 1; i <= 90; i++) lens[i] = indexed[i].size(); cout << "Lettura input: " << (clock()-start)/1000.0 << " secondi" << endl; start = clock(); //Risoluzione for (int i = 0; i < f; i++) { int k = 1, luckyNumber = 0; char c; //Lettura find fscanf(fin, "%d", daCercare); while (true) { fscanf(fin, "%c", &c); if (c == ',') { fscanf(fin, "%d", daCercare+k); if (lens[luckyNumber] > lens[daCercare[k]]) luckyNumber = daCercare[k]; k++; } else break; } //Ricerca delle ruote vincenti bool first = true; for (int j = 0; j < lens[luckyNumber]; j++) { int n = indexed[luckyNumber][j]; bool OK = true; for (int h = 0; h < k; h++) { if (!ruote[n].bitmask[daCercare[h]]) { OK = false; break; } } if (first && OK) { fprintf(out, "-- "); for (int h = 0; h < k-1; h++) fprintf(out, "%d,", daCercare[h]); fprintf(out, "%d --\n", daCercare[k-1]); first = false; } if (OK) { fprintf(out, "%s %s ", ruote[n].data->c_str(), ruote[n].luogo->c_str()); for (int h = 0; h < v-1; h++) fprintf(out, "%d,", ruote[n].numeri[h]); fprintf(out, "%d\n", ruote[n].numeri[v-1]); } } } cout << "Tempo per la ricerca: " << (clock()-start)/1000.0 << " secondi" << endl; } Ultima modifica di Mesh89 : 15-10-2008 alle 15:16. |
|
15-10-2008, 16:00 | #92 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
|
15-10-2008, 16:42 | #93 |
Member
Iscritto dal: Sep 2004
Messaggi: 216
|
Io ottengo questi valori
LottoFindDifficile 0.185443 secondi LOTTO.D2 18.48295 secondi Nella prova con lotto.d2 ottento 30041 valori trovati, mii confermate se è giusto? |
15-10-2008, 16:46 | #94 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Classifica aggiornata:
Purtroppo non ho potuto inserire Vicius perchè, sul file grosso, dopo un po' se ne esce con questo messaggio: |
15-10-2008, 16:55 | #95 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:05. |
15-10-2008, 16:58 | #96 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:05. |
15-10-2008, 17:03 | #97 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:05. |
15-10-2008, 17:03 | #98 | |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Quote:
mesh: Codice:
-- 86,62,45,38,88 -- 14/05/1983 HXXZLVFGBQTQVXVH 86,38,88,62,65,45 -- 35,56,68,81,20 -- 01/12/2013 OSEFHKQANUTVSGPM 68,35,69,20,56,81 -- 38,71,27,78 -- 18/08/1989 ZLLBLMMKFAENJGGB 4,78,38,65,71,27 31/04/2019 PZKWKBDJISNDKDLI 27,31,71,78,90,38 22/03/1991 MWRLGZILPWGPNEHH 27,71,89,38,74,78 31/09/1988 ZIKUSRGGSEJTEHLG 71,78,38,27,36,56 13/04/2009 PBHXPVPWOZZGDOBP 27,78,4,63,38,71 25/11/2015 LGPCLZZFOFOGIUSM 36,27,28,71,38,78 Codice:
-- 38,45,62,86,88 -- 14/05/1983 HXXZLVFGBQTQVXVH 38,45,62,65,86,88 -- 20,35,56,68,81 -- 01/12/2013 OSEFHKQANUTVSGPM 20,35,56,68,69,81 -- 27,38,71,78 -- 25/11/2015 LGPCLZZFOFOGIUSM 27,28,36,38,71,78 13/04/2009 PBHXPVPWOZZGDOBP 4,27,38,63,71,78 31/09/1988 ZIKUSRGGSEJTEHLG 27,36,38,56,71,78 22/03/1991 MWRLGZILPWGPNEHH 27,38,71,74,78,89 31/04/2019 PZKWKBDJISNDKDLI 27,31,38,71,78,90 18/08/1989 ZLLBLMMKFAENJGGB 4,27,38,65,71,78 |
|
15-10-2008, 17:24 | #99 |
Bannato
Iscritto dal: Mar 2008
Città: Villabate(PA)
Messaggi: 2515
|
Qualcuno che s'intende di Eclipse/Java?
Con i file postati da magix2003 ho questo problema: |
15-10-2008, 17:27 | #100 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53967
|
Posto ormai il mio, fa cacare, lo so, ma ormai l'avevo fatto con un'altra idea in testa (che il numero di estratti per ruota non potesse variare). Comunque l'ho adattato al numero variabile di estratto ed ho trovato un modo molto carino (grazie al C++) per generare le combinazioni semplici dei numeri, spero interessi a qualcuno
Codice:
#include <iostream> #include <fstream> #include <map> #include <list> #include <string> #include <vector> #include <iomanip> using namespace std; #define DATAFILENAME "LottoDataDifficile.txt" #define SEARCHFILENAME "LottoFindDifficile.txt" void parseNumberString(const string &numbers, vector<int> &unsortedNumbers) { unsigned int i = 0; int items = 0; while(i < numbers.size()) { if(numbers[i] >= '0' && numbers[i] <= '9') { unsortedNumbers.push_back(numbers[i] - '0'); if(numbers[i+1] >= '0' && numbers[i+1] <= '9') { ++i; unsortedNumbers.at(items) = unsortedNumbers.at(items) * 10 + (numbers[i] - '0'); } ++items; } ++i; } } class Drawing { vector<int> sortedNumbers; const string city; const string date; const string numbers; public: Drawing(const string &city, const string &date, const string &numbers): city(city), date(date), numbers(numbers) { parseNumberString(numbers, sortedNumbers); sort(sortedNumbers.begin(), sortedNumbers.end()); } const string & getCity() { return city; } const string & getDate() { return date; } const string & getNumbersString() { return numbers; } const vector<int> & getNumbersVector() { return sortedNumbers; } }; class SimpleCombination { unsigned int count; vector<int> markers; vector<int> values; bool hasNextCombination; public: SimpleCombination(const vector<int> &values, unsigned int count): count(count), values(values) { for(unsigned int i = 0; i < values.size(); ++i) { markers.push_back((i < count) ? 1 : 0); } next_permutation(markers.begin(), markers.end()); hasNextCombination = true; } bool hasNext() { return hasNextCombination; } void nextCombination(vector<int> & combination) { combination.resize(values.size()); for(unsigned int i = 0; i < values.size(); i++) { combination.at(i) = values.at(i) * markers.at(i); } hasNextCombination = next_permutation(markers.begin(), markers.end()); } }; //#define INDEXTYPE long #define INDEXTYPE double class Database { map<INDEXTYPE, list<Drawing *> > drawings; int numberCount; INDEXTYPE computeIndex(const vector<int> v) { INDEXTYPE index = 0; INDEXTYPE multiplier = 1; for(unsigned int i = 0; i < v.size(); i++) { if(v.at(i) > 0) { index += v.at(i) * multiplier; multiplier *= 100; } } return index; } public: Database(int numberCount): numberCount(numberCount) { } void insertDrawing(Drawing *drawing) { for(int i = 1; i <= numberCount; ++i) { SimpleCombination sc(drawing->getNumbersVector(), i); do { vector<int> combination; sc.nextCombination(combination); drawings[computeIndex(combination)].push_back(drawing); } while(sc.hasNext()); } } list<Drawing *> & findDrawing(const string &numbers) { vector<int> sortedNumbers; parseNumberString(numbers, sortedNumbers); sort(sortedNumbers.begin(), sortedNumbers.end()); return drawings[computeIndex(sortedNumbers)]; } }; int main() { ifstream f(DATAFILENAME); string date, city, numbers; if(f.fail()) return 1; getline(f, numbers); getline(f, numbers, ' '); int numberCount; f >> numberCount; if(f.fail()) return 1; Database db(numberCount); getline(f, numbers); while(1) { getline(f, date, ' '); if(f.eof() || f.fail()) break; getline(f, city, ' '); getline(f, numbers); Drawing * d = new Drawing(city, date, numbers); db.insertDrawing(d); } f.close(); f.open(SEARCHFILENAME); if(f.fail()) return 1; int count; getline(f, date, ' '); f >> count; getline(f, numbers); for(int i = 0; i < count; ++i) { getline(f, numbers); list<Drawing *> &l = db.findDrawing(numbers); if(l.size() <= 0) continue; cout << "-- " << numbers << " --" << endl; for(list<Drawing *>::iterator it = l.begin(); it != l.end(); it++) { cout << (*it)->getDate() << " " << (*it)->getCity() << " " << (*it)->getNumbersString() << endl; } } return 0; } Ultima modifica di cionci : 15-10-2008 alle 17:29. |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 20:32.