[Vari] Contest 7: Il Lotto

[gugoXX]

1. Sia dato un file contentente un inseme di estrazioni del lotto.
Il formato del file e' il seguente:


Ruote 6
Valori 5
12/10/1999 Roma 1,4,2,10,12
12/10/1999 Torino 5,7,4,6,8
12/10/1999 Milano 3,7,5,4,7
12/10/1999 Napoli 66,9,54,55,4
12/10/1999 Venezia 33,9,45,4,55
12/10/1999 Bari 3,87,65,43,21

13/11/1999 Roma 1,6,4,7,2
13/11/1999 Torino 9,4,1,55,5
13/11/1999 Milano 3,34,33,36,37
13/11/1999 Napoli 4,47,45,44,48
13/11/1999 Venezia 5,9,55,4,58
13/11/1999 Bari 66,35,25,4,90



Dove il primo record enuncia il numero delle Ruote possibili (in questo esempio e' 6, ovvero 6 diverse citta')
Il secondo record enuncia quanti valori vengono estratti per ciascuna ruota (tipicamente nel lotto vero e' 5, ovvero 5 valori diversi estratti per ciascuna ruota)
Seguono una serie di estrazioni con questo formato
Data dell'estrazione - Ruota di estrazione - elenco dei valori estratti separati da virgola
E' ammessa l'esistenza di record completamente vuoti (tipicamente tra ogni estrazione) che saranno da ignorarsi
I 3 campi sono separati da uno spazio, e non sono presenti altri spazi nei 3 campi
Ogni estrazione verra' partecipanti tutte le ruote possibili, il cui numero e' enunciato nel primo record
I valori estratti per ciascuna ruota/estrazione saranno unici (estrazione senza reinserimento, come nel lotto vero)
I valori sono sempre nel range 1-90 estremi compresi (come il lotto vero)

2. Sia dato un insieme di valori target di ricerca


Find 4
1,4,3
2,4
1,7,5
55,4,9

Dove il primo record enuncia il numero di record successivi
Mentre ciascun record dei successivi e' una combinazione da ricercarsi in modo esaustivo tra le estrazioni precedentemente caricate.
Il numero di valori per ciascuna combinazione e' variabile, ma sara' sicuramente inferiore o uguale al numero di valori possibili di una estrazione.
2,4 significa che si conta di cercare l'ambo 2,4 all'interno delle estrazioni precedenti.

Il risultato per 2,4 sarebbe pertanto:
12/10/1999 Roma 1,4,2,10,12
13/11/1999 Roma 1,6,4,7,2
In quanto in entrambe le estrazioni sia il numero 2 che il numero 4 sono stati estratti.

Output desiderato:
Per ciascun insieme dei valori target di ricerca presente ALMENO UNA VOLTA nelle estrazioni del primo file, stampare
I valori target di ricerca stessi
E tutte le estrazioni che soddisfano tali valori target di ricerca.

L'output dell'esempio sarebbe pertanto:


-- 2,4 --
12/10/1999 Roma 1,4,2,10,12
13/11/1999 Roma 1,6,4,7,2
-- 55,4,9 --
12/10/1999 Napoli 66,9,54,55,4
13/11/1999 Torino 9,4,1,55,5
13/11/1999 Venezia 5,9,55,4,58

Nulla verrebbe quindi riportato per sia per i valori 1,4,3 che per i valori 1,7,5, in quanto non presenti in modo completo nemmeno una volta tra le estrazioni a disposizione.

Seguono 2 coppie di file di test.
Facile, Difficile
Provate anche solo prima con il test, ovvero le 12 estrazioni di esempio e le 4 combinazioni da ricercare gia' qui pronte.
http://www.usaupload.net/d/mhk196q7wok

[Vincenzo1968]

E il contest 6 che fine ha fatto? Me lo sono perso? :cry:

[gugoXX]

E il contest 6 che fine ha fatto? Me lo sono perso? :cry:

Nono, e' pronto in canna, un piccolo raffinamento e parte.
E' solo che per motivi storici ho pubblicato prima il 7 (il motivo storico e' che le soluzioni si chiamano rispettivamente Contest6.sln e Contest7.sln :fagiano: )

[wingman87]

Volevo fare una domanda, forse stupida: nel risolvere il contest tutto ciò che conta è la velocità del programma risolutivo?

[gugoXX]

Volevo fare una domanda, forse stupida: nel risolvere il contest tutto ciò che conta è la velocità del programma risolutivo?

Diciamo che conta il metodo, ovvero l'algoritmo.
Un buon algoritmo spesso si traduce in una migliore leggibilita' del codice e in una migliore performance.

Anche perche' se contasse solo la velocita' ci metteremmo tutti a farlo in assembly, impiegando grandi risorse per avere poco vantaggio (e soprattutto tanti svantaggi)

[VICIUS]

Primo tentativo con forza bruta. Riporto solo il codice della soluzione.
def benchmark(label)
print "#{label}..."
start_time = Time.now
result = yield
puts " completato. (#{(Time.now - start_time).to_s} secondi)"
result
end

def load_data(file_name)
estrazioni = Array.new
File.open(file_name, 'r') do |f|
f.gets; f.gets # ignora le prime due righe
while line = f.gets
data, ruota, valori = line.chop.split
estrazioni << { data: data, ruota: ruota, valori: valori.split(',').map { |x| x.to_i} }
end
end
estrazioni
end

def load_find(file_name)
ricerche = Array.new
File.open(file_name, 'r') do |f|
f.gets # ignora la prima riga
while line = f.gets
ricerche << line.chop.split(',').map { |x| x.to_i }
end
end
ricerche
end

def contains(e, r)
r.each do |v|
return false if !e.include? v
end
true
end

def search(estrazioni, ricerche)
ricerche.each do |r|
puts "-- #{r.inspect} --"
estrazioni.each do |e|
puts "#{e[:data]} #{e[:ruota]} #{e[:valori].inspect}" if contains(e[:valori], r)
end
end
end

estrazioni = benchmark('Caricamento delle estrazioni') { load_data('LottoDataDifficile.txt') }
ricerche = benchmark('Caricamento delle ricerche') { load_find('LottoFindDifficile.txt') }
benchmark('Ricerca dei valori') { search(estrazioni, ricerche) }
Ovviamente è lento da far paura. Circa 190 secondi per la soluzione difficile.

[Vincenzo1968]

Primo tentativo con forza bruta. Riporto solo il codice della soluzione.


Ciao Vicius,

puoi postare il codice per intero? (anzi, ti sarei grato se mi dessi qualche informazione sul funzionamento di Python. Dopo l'installazione per eseguire il tuo programma che devo fare? c'è qualche ide? riga di comando? Grazie :))

x Gugo: come dobbiamo strutturare il programma? I dati vanno interamente caricati in memoria prima di prendere i tempi di esecuzione dell'algoritmo?

[gugoXX]

Ciao Vicius,

puoi postare il codice per intero? (anzi, ti sarei grato se mi dessi qualche informazione sul funzionamento di Python. Dopo l'installazione per eseguire il tuo programma che devo fare? c'è qualche ide? riga di comando? Grazie :))

x Gugo: come dobbiamo strutturare il programma? I dati vanno interamente caricati in memoria prima di prendere i tempi di esecuzione dell'algoritmo?

Ciao Vincenzo.
Diciamo che stavolta facciamo tutto insieme, dato che tenere in memoria liste lunghe che magari non vengono effettivamente sfruttate puo' essere scomodo.
Per conto mio comunque separero' sempre la fase di input da quella di preparazione strutture dati e poi elaborazione.
Con la speranza che su tempi mediamente alti l'input/output non pesi piu' di tanto.

[Mesh89]

Purtroppo non ho tempo (ne voglia :P) di scrivere il codice, però un appunto che mi viene da fare (se ho capito bene il codice di vicius, non conosco il python) è che la tua ricerca è qualcosa di simile:

f = vettore find
r = vettore risultati

per ogni i in f
se i è contenuto in r, allora bene, altrimenti questa ruota è da scartare

le prestazioni (di una verifica ruota-find) sono quindi O(f*r)

penso che si possa trasformare in O(f+r) usando, per esempio, una bitmask sui 90 valori possibili (banalmente un array di 90 booleani), e una prima passata ad r per settare la bitmask, e una seconda a f per vedere se ogni valore è contenuto

[shinya]

Scusate eh, ma il codice di vicius era ruby, non python.
Non per fare il pedante, ma...

[VICIUS]

Ciao Vicius,

puoi postare il codice per intero? (anzi, ti sarei grato se mi dessi qualche informazione sul funzionamento di Python. Dopo l'installazione per eseguire il tuo programma che devo fare? c'è qualche ide? riga di comando? Grazie :))
Installa Ruby 1.9 poi metti il codice in un file e da linea di comando basta dare ruby file.rb. I File txt con i dati devono essere nella stessa cartella del file rb da cui lanci il programma.

[cionci]

Gugo: è questo il risultato "semplice" ?
--74,47,67
--86,16
23/06/2007 Cagliari 86,58,64,72,16
19/05/2007 Torino 24,43,16,86,50
10/02/2007 Bari 21,16,7,86,52
07/10/2006 Venezia 16,86,23,73,78
07/01/2006 Genova 45,86,16,77,13
03/12/2005 Milano 55,17,86,68,16
21/06/2003 Firenze 16,56,25,86,43
12/04/2003 Roma 16,28,5,22,86
18/05/2002 Napoli 19,16,61,28,86
14/04/2001 Venezia 42,86,16,77,14
10/02/2001 Torino 68,90,16,86,10
29/07/2000 Genova 48,86,75,16,40
15/05/1999 Torino 86,62,26,16,4
--89,57
17/09/2005 Palermo 89,14,27,17,57
09/07/2005 Genova 19,57,79,25,89
21/05/2005 Torino 89,78,44,1,57
26/02/2005 Firenze 20,56,57,89,67
29/05/2004 Bari 82,4,16,89,57
21/02/2004 Torino 89,32,60,73,57
07/06/2003 Milano 41,57,63,89,17
12/04/2003 Palermo 72,46,15,89,57
18/01/2003 Torino 34,77,89,57,74
09/11/2002 Napoli 57,89,10,31,11
29/06/2002 Firenze 71,46,89,83,57
04/05/2002 Bari 6,89,59,61,57
19/05/2001 Firenze 58,8,89,57,5
29/07/2000 Palermo 7,80,57,32,89
22/01/2000 Bari 57,18,89,44,15
--71,29,58
--73,16,30
23/08/2008 Venezia 30,53,73,16,66
--59,47,60
--46,67
06/09/2008 Napoli 6,39,67,78,46
05/04/2008 Roma 46,10,34,37,67
16/02/2008 Torino 46,38,51,80,67
31/03/2007 Torino 5,67,46,37,58
18/11/2006 Napoli 67,46,7,42,16
02/09/2006 Milano 41,30,6,67,46
10/06/2006 Palermo 67,39,4,11,46
03/07/2004 Cagliari 46,67,72,52,58
13/09/2003 Milano 55,46,67,45,51
13/09/2003 Napoli 46,67,18,90,32
24/05/2003 Palermo 30,67,66,39,46
15/06/2002 Torino 67,37,27,1,46
05/08/2000 Genova 89,30,67,46,5
11/03/2000 Milano 84,67,46,15,19
11/12/1999 Roma 46,89,31,82,67
15/05/1999 Venezia 52,44,46,13,67
--75,41,72
--80,6,22
--15,67,80
19/06/2004 Genova 80,89,15,67,70
--81,88
04/10/2008 Milano 32,22,88,75,81
21/04/2007 Venezia 32,43,88,46,81
28/10/2006 Napoli 19,81,88,55,27
12/06/2004 Napoli 81,88,48,8,13
17/05/2003 Bari 88,81,83,47,22
25/01/2003 Palermo 81,26,88,71,77
23/11/2002 Palermo 81,69,59,88,49
28/09/2002 Torino 30,78,18,88,81
29/06/2002 Napoli 81,2,32,88,44
20/10/2001 Cagliari 38,80,81,52,88
25/03/2000 Bari 81,15,52,88,2
11/03/2000 Cagliari 7,30,81,88,61
--45,11,41
--32,47
05/05/2007 Cagliari 24,47,1,38,32
14/04/2007 Torino 42,47,32,79,30
19/08/2006 Roma 47,52,36,24,32
22/04/2006 Cagliari 6,47,3,32,43
05/02/2005 Milano 32,84,47,25,21
17/07/2004 Genova 8,85,47,32,7
05/10/2002 Torino 47,77,1,32,84
08/12/2001 Firenze 32,47,49,8,38
18/08/2001 Roma 31,44,47,82,32
14/04/2001 Genova 32,5,21,47,58
16/12/2000 Milano 75,47,40,63,32
12/08/2000 Cagliari 47,20,30,32,31
13/05/2000 Genova 47,3,31,32,55
23/10/1999 Roma 29,32,24,86,47
23/10/1999 Venezia 47,32,41,16,69
18/09/1999 Milano 47,58,32,41,63
18/09/1999 Venezia 47,32,85,83,2
--17,57,70
--32,64,59
--70,2
19/07/2008 Bari 2,88,70,50,5
14/06/2008 Torino 4,2,70,8,21
03/05/2008 Firenze 2,70,35,28,20
26/05/2007 Firenze 2,70,88,1,24
28/04/2007 Venezia 60,2,36,70,21
31/03/2007 Firenze 7,57,71,70,2
17/03/2007 Genova 12,70,42,58,2
21/08/2004 Roma 36,22,28,2,70
08/05/2004 Venezia 63,2,70,20,49
22/02/2003 Genova 50,36,54,2,70
23/02/2002 Palermo 53,70,23,13,2
09/09/2000 Genova 59,42,2,70,8
28/08/1999 Genova 46,2,21,70,51
22/05/1999 Roma 70,13,2,47,78
--56,11,66
--32,68,85
--34,44,77
--8,40,75


Se è corretta, la soluzione difficile la trovo in:

real 0m2.446s
user 0m2.304s
sys 0m0.112s

[VICIUS]

Gugo: è questo il risultato "semplice" ?
[CODE] --74,47,67
--86,16
23/06/2007 Cagliari 86,58,64,72,16
19/05/2007 Torino 24,43,16,86,50[...]

L'output è identico alla mia versione quindi spero che sia quello corretto. :D

[Mesh89]

Penso ci sia un errore nell'output di esempio, esistono due Venezia che soddisfano 55,4,9

[cionci]

L'output è identico alla mia versione quindi spero che sia quello corretto. :D
Ok ;)

[gugoXX]

Penso ci sia un errore nell'output di esempio, esistono due Venezia che soddisfano 55,4,9

Indubbiamente.
Ma possibile che neppure con 3 record in croce non riesca mai a fare il lavoro di un computer? :help:

[cionci]

Indubbiamente.
Ma possibile che neppure con 3 record in croce non riesca mai a fare il lavoro di un computer? :help:
Mi sono reso conto solo ora di una cosa, perché sono stati inseriti 6 numeri per riga in quello difficile ?
Avevo fatto il conto a 5 e mi salta tutto l'algoritmo :muro: Era un ricerca O(1) :cry:

[gugoXX]

Mi sono reso conto solo ora di una cosa, perché sono stati inseriti 6 numeri per riga in quello difficile ?
Avevo fatto il conto a 5 e mi salta tutto l'algoritmo :muro: Era un ricerca O(1) :cry:

:p I valori per riga sono un parametro di input.
Ma dai, non penso che se al posto di 5 diventano 6 salti proprio tutto...

[Mesh89]

cionci: non vorrei risultare pedante, ma:

Per ciascun insieme dei valori target di ricerca presente ALMENO UNA VOLTA nelle estrazioni del primo file, stampare
I valori target di ricerca stessi

:P

[cionci]

Si parlava di lotto e credevo che fossero <= 5.
Ma dai, non penso che se al posto di 5 diventano 6 salti proprio tutto...
L'accesso alla lista di ruote non mi salta (uso un map con i double):

drawings[sortedNumbers[0] + sortedNumbers[1] * 100 + sortedNumbers[2] * 10000 + sortedNumbers[3] * 1000000 + sortedNumbers[4] * 100000000]

Però mi salta il calcolo delle disposizioni da inserire nel map, mi toccherebbe implementare un algoritmo per calcolare le combinazioni semplici :muro:

[Mesh89]

Alla fine mi sono lasciato tentare dallo scrivere una soluzione anch'io :P

La mia soluzione in C++ chiede 4s su un AMD Duron a 1600mhz
Confrontando le prime righe della soluzione facile con quella di cionci, la soluzione sembra corretta. Devo postare il codice?

[Vincenzo1968]

Scusate eh, ma il codice di vicius era ruby, non python.
Non per fare il pedante, ma...
:doh:

Installa Ruby 1.9 poi metti il codice in un file e da linea di comando basta dare ruby file.rb. I File txt con i dati devono essere nella stessa cartella del file rb da cui lanci il programma.

Grazie a entrambi :)

Un'ultima domanda: il sito ufficiale è questo?:

http://www.ruby-lang.org/en/

edit: la 1.9, leggo nel sito, è ancora in fase sperimentale(consigliano di scaricare la 1.8.7). Che mi consigli?

[Vincenzo1968]

Alla fine mi sono lasciato tentare dallo scrivere una soluzione anch'io :P

La mia soluzione in C++ chiede 4s su un AMD Duron a 1600mhz
Confrontando le prime righe della soluzione facile con quella di cionci, la soluzione sembra corretta. Devo postare il codice?

Si postalo che alla fine confrontiamo i tempi su un'unica macchina. Posta anche una breve spiegazione dell'algoritmo utilizzato.
Ciao

[Mesh89]

#include <iostream>
#include <bitset>
#include <string>
#include <vector>

using namespace std;


struct Ruota {
bitset<96> bitmask;
string* data,* luogo;
char* numeri;
};
vector <Ruota> ruote;


int main() {
FILE* fin = fopen("fin.in", "r");
FILE* rin = fopen("rin.in", "r");
FILE* out = fopen("out.out", "w");
int r, v, f, daCercare[90];
char s[100];

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);
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;
} fscanf(rin, "%d\n", &n);
ruota.bitmask[n] = 1;
ruota.numeri[v-1] = (char)n;

ruote.push_back(ruota);
} r = ruote.size();


//Risoluzione
for (int i = 0; i < f; i++) {
int k = 1;
char c;

//Lettura find
fscanf(fin, "%d", daCercare);
while (true) {
fscanf(fin, "%c", &c);

if (c == ',') {
fscanf(fin, "%d", daCercare+k);
k++;
}
else break;
}

//Ricerca delle ruote vincenti
bool first = true;
for (int j = 0; j < r; j++) {
bool OK = true;
for (int h = 0; h < k; h++) {
if (!ruote[j].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[j].data->c_str(), ruote[j].luogo->c_str());
for (int h = 0; h < v-1; h++)
fprintf(out, "%d,", ruote[j].numeri[h]);
fprintf(out, "%d\n", ruote[j].numeri[v-1]);
}
}
}
}

1 Carico la lista di ruote, e per ognuna creo una bitmask con i valori presenti sui 90 possibili
2 Per ogni find, passo ogni ruota memorizzata, in tempo O(find.length), ed eventualmente stampo

Praticamente il casino è la lettura dell'input :P

PS: alla fine è solo un gioco, però postando codice e soluzione permetto agli altri di attingervi a piene mani :)
PPS: mi affido molto alle ottimizzazioni del compilatore, quindi compilate con -O2 :P

[gugoXX]

Si parlava di lotto e credevo che fossero <= 5.

L'accesso alla lista di ruote non mi salta (uso un map con i double):

drawings[sortedNumbers[0] + sortedNumbers[1] * 100 + sortedNumbers[2] * 10000 + sortedNumbers[3] * 1000000 + sortedNumbers[4] * 100000000]

Però mi salta il calcolo delle disposizioni da inserire nel map, mi toccherebbe implementare un algoritmo per calcolare le combinazioni semplici :muro:

Eh gia'. Dire quante sono sono capaci tutti.
Dire quali sono non e' proprio da 2 secondi...

[ercand]

Ho notato che nel file LottoDataDifficile.txt forse c'è un errore, se lo leggete con un programma tipo UltraEdit il file inizia in questo modo

Ruote 100

Oppure era un trabocchetto di gugo:stordita: .

[Vincenzo1968]

Ohé,

ho scaricato i sorgenti di Ruby e sto dando un'occhiata alla documentazione. A prima vista pare proprio un gran bel linguaggio. Ho visto che utilizzano Bison per il parsing :D

[cdimauro]

Ho notato che nel file LottoDataDifficile.txt forse c'è un errore, se lo leggete con un programma tipo UltraEdit il file inizia in questo modo

Ruote 100

Oppure era un trabocchetto di gugo:stordita: .
Quei 3 caratteri mi sembrano il marker BOM dei file UTF8.

[^TiGeRShArK^]

questa è la mia soluzione (di quello semplice) con il file di dati che avevo già letto (e che quindi viene letto dalla cache):

Reading time: 13ms
86,16
23/06/2007 Cagliari
19/05/2007 Torino
10/02/2007 Bari
07/10/2006 Venezia
07/01/2006 Genova
03/12/2005 Milano
21/06/2003 Firenze
12/04/2003 Roma
18/05/2002 Napoli
14/04/2001 Venezia
10/02/2001 Torino
29/07/2000 Genova
15/05/1999 Torino
89,57
17/09/2005 Palermo
09/07/2005 Genova
21/05/2005 Torino
26/02/2005 Firenze
29/05/2004 Bari
21/02/2004 Torino
07/06/2003 Milano
12/04/2003 Palermo
18/01/2003 Torino
09/11/2002 Napoli
29/06/2002 Firenze
04/05/2002 Bari
19/05/2001 Firenze
29/07/2000 Palermo
22/01/2000 Bari
73,16,30
23/08/2008 Venezia
46,67
06/09/2008 Napoli
05/04/2008 Roma
16/02/2008 Torino
31/03/2007 Torino
18/11/2006 Napoli
02/09/2006 Milano
10/06/2006 Palermo
03/07/2004 Cagliari
13/09/2003 Milano
13/09/2003 Napoli
24/05/2003 Palermo
15/06/2002 Torino
05/08/2000 Genova
11/03/2000 Milano
11/12/1999 Roma
15/05/1999 Venezia
15,67,80
19/06/2004 Genova
81,88
04/10/2008 Milano
21/04/2007 Venezia
28/10/2006 Napoli
12/06/2004 Napoli
17/05/2003 Bari
25/01/2003 Palermo
23/11/2002 Palermo
28/09/2002 Torino
29/06/2002 Napoli
20/10/2001 Cagliari
25/03/2000 Bari
11/03/2000 Cagliari
32,47
05/05/2007 Cagliari
14/04/2007 Torino
19/08/2006 Roma
22/04/2006 Cagliari
05/02/2005 Milano
17/07/2004 Genova
05/10/2002 Torino
08/12/2001 Firenze
18/08/2001 Roma
14/04/2001 Genova
16/12/2000 Milano
12/08/2000 Cagliari
13/05/2000 Genova
23/10/1999 Roma
23/10/1999 Venezia
18/09/1999 Milano
18/09/1999 Venezia
70,2
19/07/2008 Bari
14/06/2008 Torino
03/05/2008 Firenze
26/05/2007 Firenze
28/04/2007 Venezia
31/03/2007 Firenze
17/03/2007 Genova
21/08/2004 Roma
08/05/2004 Venezia
22/02/2003 Genova
23/02/2002 Palermo
09/09/2000 Genova
28/08/1999 Genova
22/05/1999 Roma
Time elapsed for processing: 34ms

EDIT:
è fatto in C# con alcune parti in LINQ ed è lanciato in modalità debug su un windows virtualizzato sul macbookpro con penryn a 2.4....
quello difficile non faccio in tempo che sto uscendo..
vedo quando torno se non ho troppa birra in corpo...
ma ad occhio non dovrei cambiare nulla, dovrei solo mettere il percorso dei due nuovi file e correggere l'eventuale errore del carattere che ha trovato qualcuno :p

ARIEDIT: Il tempo impiegato per stampare a video non l'ho contato, ma credo che sia praticamente ininfluente dato che è tutto inserito in liste, quindi non sto iterando su un IEnumerable..

[VICIUS]

:doh:



Grazie a entrambi :)

Un'ultima domanda: il sito ufficiale è questo?:

http://www.ruby-lang.org/en/

edit: la 1.9, leggo nel sito, è ancora in fase sperimentale(consigliano di scaricare la 1.8.7). Che mi consigli?
Se non ci devi fare cose in un ambiente di produzione puoi usare tranquillamente la 1.9

[k0nt3]

uhm è giusto il momento di esercitarmi con c++, mio malgrado sono costretto a usarlo :D

#include <iostream>
#include <fstream>
#include <sstream>
#include <set>

using namespace std;

class Ruota {
public:
Ruota(string data, string ruota, set<int> estrazioni) {
m_estrazioni = estrazioni;
m_data = data;
m_ruota = ruota;
}

string getData() {
return m_data;
}

string getRuota() {
return m_ruota;
}

bool contiene(set<int> valori) {
set<int>::iterator it;
for(it = valori.begin(); it != valori.end(); it++ ) {
if(m_estrazioni.count(*it) == 0) {
return false;
}
}
return true;
}

private:
set<int> m_estrazioni;
string m_data, m_ruota;
};

int main(int argc, char** argv) {
if(argc < 3)
return -1;

set<int>* valori;
int numRighe;

// leggi file con i target
ifstream findFile(argv[2]);
if(findFile.is_open()) {
string tmp;
char ch;
findFile >> tmp >> numRighe;
valori = new set<int>[numRighe];
for(int i=0; i<numRighe; ++i) {
char line[50];
findFile.getline(line, 50);

if(line[0] == 13) {
--i;
continue;
}

stringstream lineStream(line);
while(lineStream.good()) {
int valore;
lineStream >> valore >> ch;
valori[i].insert(valore);
}
}
findFile.close();
}
else
cout << "Unable to open file" << argv[2] << endl;

// leggi file con le estrazioni
ifstream dataFile(argv[1]);
if(dataFile.is_open()) {
string tmp;
int numRuote, numValori;
dataFile >> tmp >> numRuote;
dataFile >> tmp >> numValori;

while(dataFile.good()) {
string data, ruota;
set<int> estrazioni;
dataFile >> data >> ruota;

for(int i=0; i<numValori; ++i) {
int estrazione;
char sep;
dataFile >> estrazione >> sep;
estrazioni.insert(estrazione);
}

Ruota r(data, ruota, estrazioni);

for(int i=0; i<numRighe; ++i) {
if(r.contiene(valori[i])) {
cout << "Data: " << r.getData() << " Ruota: " << r.getRuota() << endl << "Valori:";
set<int>::iterator it;
for(it = valori[i].begin(); it != valori[i].end(); it++ ) {
cout << " " << (*it);
}
cout << " Estrazione:";
for(it = estrazioni.begin(); it != estrazioni.end(); it++ ) {
cout << " " << (*it);
}
cout << endl << endl;
}
}
}
dataFile.close();
}
else
cout << "Unable to open file" << argv[1] << endl;
}

[^TiGeRShArK^]

uhm è giusto il momento di esercitarmi con c++, mio malgrado sono costretto a usarlo :D

tempo e output dell'algoritmo? :fagiano:
..non mi va di compilare c++ su mac che non l'ho mai fatto... :Prrr:

[^TiGeRShArK^]

applicando lo stesso algoritmo al difficile ottengo:

Time elapsed for processing: 10820ms

in modalità release a batteria...
però devo vedere se si può migliorare qualcosa perchè l'algoritmo era il + semplice che mi era venuto in mente :p

[^TiGeRShArK^]

tempo e output dell'algoritmo? :fagiano:
..non mi va di compilare c++ su mac che non l'ho mai fatto... :Prrr:

Alla fine l'ho compilato col santo xcode...anche se non ho capito per quale assurdo motivo mi aveva incasinato il mac dato che alcune colonne dell'output della console uscivano completamente bianche e mi aveva incasinato il terminale e ho dovuto riavviare :mbe:
cmq..
come faccio a vedere il tempo di esecuzione sotto mac/linux? :fagiano:
Non hai messo nessuna stampa per vedere quanto dura..
Ho provato i file difficili e comunque ci mette molto + del mio, ma non so quanto ci mette di preciso.. :stordita:

[^TiGeRShArK^]

applicando lo stesso algoritmo al difficile ottengo:

Time elapsed for processing: 10820ms

in modalità release a batteria...
però devo vedere se si può migliorare qualcosa perchè l'algoritmo era il + semplice che mi era venuto in mente :p
Sono sugli 8 secondi eliminando una cavolata che ripetevo un fottio di volte..
Comunque ad occhio direi che posso scendere abbastanza agevolmente verso i valori di cionci ottimizzando per il difficile :p

EDIT: per ora sono a 85 LOC.. quello di Vicius mi sembra ben + compatto :D

[Mesh89]

Ma stai parlando da solo? O.o

Pe vedere il tempo sotto linux, avvia l'eseguibile scrivendoci time davanti

[Vincenzo1968]

Prima di mettere mano al codice vorrei fare una proposta.
Poiché per stampare i risultati a video si perde un sacco di tempo, direi di eliminare questa cosa dal calcolo dei tempi e strutturare il programma cosi: creiamo una funzione che accetti in input il nome dei due file e che restituisca l'output in un array di stringhe(o lista concatenata, vector, etc).

p.es. :


t1 = clock() //avvio il timer
Trova("LottoFind.txt", "LottoData.txt", &List); // chiamo la funzione
t2 = clock() //fermo il timer
print(...); // stampo il tempo di esecuzione t2 - t1
print(List) // stampo i risultati restituiti dalla funzione


Che ne pensate? Se siamo tutti d'accordo, coloro che hanno già postato il codice potrebbero apportarvi le modifiche e ripostarlo.

:)

[k0nt3]

tempo e output dell'algoritmo? :fagiano:
..non mi va di compilare c++ su mac che non l'ho mai fatto... :Prrr:

sul difficile ci mette circa 5 minuti con questo output


Data: 3/09/2008 Ruota: Vicenza Valori: 27 61 81 90 Estrazione: 12 27 61 66 81 90
Data: 1/06/2008 Ruota: Avellino Valori: 3 41 59 61 Estrazione: 3 10 41 59 61 63
Data: 5/04/2008 Ruota: Foggia Valori: 5 15 39 75 Estrazione: 5 15 39 63 65 75
Data: 5/04/2008 Ruota: Parma Valori: 6 16 30 80 Estrazione: 6 16 30 43 80 82
Data: 5/04/2008 Ruota: Ferrara Valori: 30 32 54 89 Estrazione: 1 12 30 32 54 89
Data: 9/03/2008 Ruota: Benevento Valori: 22 23 36 57 Estrazione: 10 19 22 23 36 57
Data: 2/03/2008 Ruota: Belluno Valori: 24 44 45 72 Estrazione: 19 24 41 44 45 72
Data: 6/02/2008 Ruota: Catania Valori: 6 19 40 87 Estrazione: 6 19 27 40 54 87
Data: 5/12/2007 Ruota: Asti Valori: 33 42 48 53 Estrazione: 30 33 42 46 48 53
Data: 3/11/2007 Ruota: Enna Valori: 2 26 37 77 Estrazione: 2 26 37 46 75 77
Data: 3/10/2007 Ruota: Lucca Valori: 62 66 74 76 82 Estrazione: 4 62 66 74 76 82
Data: 2/09/2007 Ruota: Treviso Valori: 22 26 38 75 Estrazione: 11 22 26 38 42 75
Data: 5/09/2007 Ruota: Aosta Valori: 6 12 50 71 Estrazione: 6 10 12 50 57 71
Data: 1/09/2007 Ruota: Cremona Valori: 4 38 65 70 Estrazione: 4 38 42 60 65 70
Data: 5/08/2007 Ruota: Arezzo Valori: 23 33 75 85 Estrazione: 23 33 43 67 75 85
Data: 1/07/2007 Ruota: Trieste Valori: 52 64 65 73 Estrazione: 7 32 52 64 65 73
Data: 4/07/2007 Ruota: Palermo Valori: 2 8 15 70 Estrazione: 2 8 13 15 62 70
Data: 3/06/2007 Ruota: Carbonia-Iglesias Valori: 23 24 37 47 Estrazione: 23 24 33 37 38 47
Data: 9/05/2007 Ruota: Cuneo Valori: 21 26 39 64 Estrazione: 21 26 39 64 70 80
Data: 2/05/2007 Ruota: Lecce Valori: 37 59 68 80 Estrazione: 22 37 59 68 80 89
Data: 5/05/2007 Ruota: Asti Valori: 22 27 35 57 Estrazione: 22 25 27 35 57 87
Data: 1/04/2007 Ruota: Trieste Valori: 17 21 43 57 Estrazione: 17 21 26 43 57 88
Data: 7/03/2007 Ruota: Salerno Valori: 12 32 71 83 Estrazione: 12 18 32 71 79 83
Data: 3/03/2007 Ruota: Caserta Valori: 1 40 42 74 Estrazione: 1 29 40 42 74 89
Data: 3/03/2007 Ruota: Padova Valori: 51 58 61 65 Estrazione: 5 51 58 61 65 73
Data: 4/02/2007 Ruota: Ragusa Valori: 52 64 65 73 Estrazione: 52 60 64 65 69 73
Data: 6/01/2007 Ruota: Pordenone Valori: 21 26 39 64 Estrazione: 21 26 39 57 64 68
Data: 6/12/2006 Ruota: Bergamo Valori: 1 32 42 73 Estrazione: 1 32 42 56 73 86
Data: 9/12/2006 Ruota: Ragusa Valori: 30 32 46 67 Estrazione: 30 32 35 46 50 67
Data: 4/11/2006 Ruota: Ancona Valori: 32 35 79 85 Estrazione: 32 34 35 75 79 85
Data: 4/10/2006 Ruota: Arezzo Valori: 9 13 41 87 Estrazione: 9 13 41 54 78 87
Data: 4/10/2006 Ruota: Pescara Valori: 1 32 42 73 Estrazione: 1 32 36 42 72 73
Data: 2/08/2006 Ruota: Agrigento Valori: 38 42 44 87 Estrazione: 38 42 44 72 74 87
Data: 1/07/2006 Ruota: Cagliari Valori: 3 40 59 81 Estrazione: 3 40 46 59 78 81
Data: 7/06/2006 Ruota: Firenze Valori: 32 36 41 56 83 Estrazione: 32 36 41 50 56 83
Data: 2/04/2006 Ruota: Catania Valori: 29 44 61 71 Estrazione: 29 44 61 66 71 82
Data: 8/03/2006 Ruota: Ancona Valori: 2 19 37 54 Estrazione: 2 3 19 37 54 82
Data: 1/02/2006 Ruota: MedioCampidano Valori: 23 41 53 70 Estrazione: 10 23 41 53 65 70
Data: 1/02/2006 Ruota: Ferrara Valori: 4 14 24 48 Estrazione: 4 14 19 24 40 48
Data: 7/01/2006 Ruota: Caserta Valori: 13 36 67 82 Estrazione: 13 30 36 67 77 82
Data: 7/01/2006 Ruota: Bergamo Valori: 19 46 73 76 Estrazione: 19 46 62 73 76 88
Data: 1/12/2005 Ruota: Prato Valori: 15 28 43 84 Estrazione: 15 28 36 43 57 84
Data: 6/11/2005 Ruota: Padova Valori: 21 26 39 64 Estrazione: 18 21 26 36 39 64
Data: 2/10/2005 Ruota: Latina Valori: 8 14 32 49 Estrazione: 8 14 32 40 49 73
Data: 5/10/2005 Ruota: Arezzo Valori: 23 24 37 47 Estrazione: 23 24 26 34 37 47
Data: 1/10/2005 Ruota: Massa-Carrara Valori: 57 64 69 70 Estrazione: 1 9 57 64 69 70
Data: 0/09/2005 Ruota: Isernia Valori: 58 82 83 84 Estrazione: 3 58 82 83 84 88
Data: 0/08/2005 Ruota: Perugia Valori: 3 52 75 88 Estrazione: 3 5 52 56 75 88
Data: 0/07/2005 Ruota: Brindisi Valori: 26 74 78 83 Estrazione: 5 26 63 74 78 83
Data: 8/05/2005 Ruota: Ferrara Valori: 15 50 65 66 Estrazione: 9 15 46 50 65 66
Data: 1/05/2005 Ruota: Taranto Valori: 13 29 42 78 Estrazione: 13 29 31 42 53 78
Data: 4/05/2005 Ruota: Treviso Valori: 20 34 46 80 Estrazione: 20 34 46 64 80 82
Data: 0/04/2005 Ruota: Chieti Valori: 31 51 52 72 Estrazione: 17 31 37 51 52 72
Data: 9/03/2005 Ruota: Novara Valori: 23 27 30 40 Estrazione: 1 23 27 29 30 40
Data: 2/03/2005 Ruota: Salerno Valori: 5 29 39 66 Estrazione: 5 15 23 29 39 66
Data: 9/01/2005 Ruota: Pordenone Valori: 1 38 50 55 Estrazione: 1 22 37 38 50 55
Data: 3/11/2004 Ruota: Firenze Valori: 2 13 23 70 Estrazione: 2 13 23 38 50 70
Data: 9/10/2004 Ruota: Pesaro-Urbino Valori: 26 32 72 90 Estrazione: 17 26 32 46 72 90
Data: 2/10/2004 Ruota: Trapani Valori: 1 10 44 87 Estrazione: 1 10 44 52 68 87
Data: 1/08/2004 Ruota: Pesaro-Urbino Valori: 14 17 50 69 Estrazione: 14 17 49 50 56 69
Data: 3/07/2004 Ruota: Piacenza Valori: 32 33 43 82 Estrazione: 32 33 43 58 63 82
Data: 6/06/2004 Ruota: Chieti Valori: 9 20 40 67 Estrazione: 7 9 20 40 56 67
Data: 2/06/2004 Ruota: Milano Valori: 19 23 31 63 Estrazione: 19 23 31 57 63 76
Data: 3/03/2004 Ruota: Udine Valori: 29 38 44 47 81 Estrazione: 29 38 44 47 68 81
Data: 6/03/2004 Ruota: Bologna Valori: 40 44 68 79 88 Estrazione: 40 41 44 68 79 88
Data: 8/02/2004 Ruota: Modena Valori: 5 51 79 87 Estrazione: 5 9 31 51 79 87
Data: 4/02/2004 Ruota: Venezia Valori: 8 14 68 77 Estrazione: 8 14 47 68 72 77
Data: 7/02/2004 Ruota: Bolzano Valori: 9 32 42 85 Estrazione: 9 17 23 32 42 85
Data: 7/01/2004 Ruota: Ravenna Valori: 4 21 55 82 Estrazione: 4 5 21 55 68 82
Data: 0/01/2004 Ruota: Belluno Valori: 12 46 59 74 Estrazione: 12 46 59 67 74 75
Data: 0/01/2004 Ruota: Catania Valori: 51 52 60 67 Estrazione: 11 24 51 52 60 67
Data: 6/12/2003 Ruota: Venezia Valori: 41 46 68 90 Estrazione: 9 35 41 46 68 90
Data: 8/11/2003 Ruota: Crotone Valori: 3 15 68 81 Estrazione: 3 5 15 49 68 81
Data: 8/11/2003 Ruota: Isernia Valori: 21 52 59 64 Estrazione: 7 13 21 52 59 64
Data: 8/10/2003 Ruota: Genova Valori: 8 11 19 90 Estrazione: 8 11 19 38 40 90
Data: 0/09/2003 Ruota: Treviso Valori: 17 38 61 68 Estrazione: 17 38 61 63 68 70
Data: 3/09/2003 Ruota: Padova Valori: 14 37 55 76 Estrazione: 5 14 37 54 55 76
Data: 2/07/2003 Ruota: Gorizia Valori: 9 59 71 89 Estrazione: 9 49 59 71 79 89
Data: 1/05/2003 Ruota: Trieste Valori: 43 56 76 85 Estrazione: 32 43 48 56 76 85
Data: 3/05/2003 Ruota: Rimini Valori: 28 46 80 81 Estrazione: 28 30 46 51 80 81
Data: 6/04/2003 Ruota: Messina Valori: 10 29 34 37 Estrazione: 10 29 34 37 40 78
Data: 2/04/2003 Ruota: Milano Valori: 5 15 39 75 Estrazione: 5 15 39 74 75 89
Data: 2/04/2003 Ruota: Prato Valori: 16 49 54 89 Estrazione: 7 9 16 49 54 89
Data: 5/03/2003 Ruota: Palermo Valori: 25 26 32 77 Estrazione: 5 25 26 30 32 77
Data: 1/03/2003 Ruota: Avellino Valori: 23 25 37 38 Estrazione: 23 25 37 38 59 90
Data: 2/02/2003 Ruota: Mantova Valori: 13 36 51 87 Estrazione: 13 36 51 64 78 87
Data: 5/02/2003 Ruota: Ogliastra Valori: 1 10 44 80 Estrazione: 1 10 36 44 52 80
Data: 8/02/2003 Ruota: Cuneo Valori: 16 40 76 87 Estrazione: 16 31 40 76 86 87
Data: 8/01/2003 Ruota: Brindisi Valori: 29 40 77 87 Estrazione: 6 27 29 40 77 87
Data: 4/01/2003 Ruota: Livorno Valori: 31 42 81 90 Estrazione: 31 42 55 81 86 90
Data: 2/10/2002 Ruota: Mantova Valori: 28 34 62 76 Estrazione: 28 34 46 48 62 76
Data: 8/09/2002 Ruota: Pistoia Valori: 13 29 42 78 Estrazione: 13 18 29 42 75 78
Data: 8/09/2002 Ruota: Salerno Valori: 42 53 62 75 Estrazione: 34 41 42 53 62 75
Data: 8/09/2002 Ruota: Oristano Valori: 43 63 77 90 Estrazione: 18 43 60 63 77 90
Data: 4/09/2002 Ruota: Lecco Valori: 33 42 47 69 Estrazione: 33 40 42 47 48 69
Data: 0/08/2002 Ruota: Novara Valori: 1 38 44 53 Estrazione: 1 2 38 44 53 84
Data: 3/08/2002 Ruota: Imperia Valori: 30 33 47 53 Estrazione: 30 31 33 47 53 81
Data: 5/06/2002 Ruota: LaSpezia Valori: 5 15 39 75 Estrazione: 5 15 18 39 75 89
Data: 0/04/2002 Ruota: Trapani Valori: 5 51 79 87 Estrazione: 5 51 71 73 79 87
Data: 6/04/2002 Ruota: Ragusa Valori: 15 21 26 68 Estrazione: 15 21 26 27 68 84
Data: 6/03/2002 Ruota: Pavia Valori: 23 33 75 85 Estrazione: 23 25 33 68 75 85
Data: 2/02/2002 Ruota: Biella Valori: 39 43 55 62 Estrazione: 4 39 43 55 62 66
Data: 2/12/2001 Ruota: Benevento Valori: 10 20 79 80 Estrazione: 10 20 57 69 79 80
Data: 6/10/2001 Ruota: Imperia Valori: 2 3 50 71 Estrazione: 2 3 32 50 71 76
Data: 9/09/2001 Ruota: Ancona Valori: 18 42 54 74 Estrazione: 18 42 54 55 74 84
Data: 8/09/2001 Ruota: Avellino Valori: 11 24 45 90 Estrazione: 11 24 45 52 60 90
Data: 4/07/2001 Ruota: Perugia Valori: 16 40 76 87 Estrazione: 14 16 40 71 76 87
Data: 7/07/2001 Ruota: Venezia Valori: 2 6 29 32 Estrazione: 2 5 6 29 32 74
Data: 2/06/2001 Ruota: Udine Valori: 28 46 80 81 Estrazione: 14 28 46 80 81 86
Data: 6/05/2001 Ruota: Grosseto Valori: 2 6 13 54 Estrazione: 2 6 13 23 54 81
Data: 4/04/2001 Ruota: Alessandria Valori: 18 46 58 68 Estrazione: 18 46 58 68 69 76
Data: 0/02/2001 Ruota: Bolzano Valori: 34 43 51 68 Estrazione: 5 34 38 43 51 68
Data: 8/11/2000 Ruota: Messina Valori: 42 53 62 75 Estrazione: 2 8 42 53 62 75
Data: 1/11/2000 Ruota: Massa-Carrara Valori: 2 26 37 68 Estrazione: 2 4 26 37 67 68
Data: 4/11/2000 Ruota: Lodi Valori: 8 64 71 81 Estrazione: 8 32 61 64 71 81
Data: 4/10/2000 Ruota: Lecco Valori: 30 48 68 83 Estrazione: 30 48 68 69 81 83
Data: 9/09/2000 Ruota: Lodi Valori: 1 10 44 80 Estrazione: 1 10 31 37 44 80
Data: 9/07/2000 Ruota: Lecco Valori: 11 34 49 64 Estrazione: 11 34 44 49 57 64
Data: 1/07/2000 Ruota: Sassari Valori: 57 64 69 70 Estrazione: 42 49 57 64 69 70
Data: 1/03/2000 Ruota: Terni Valori: 4 5 38 70 Estrazione: 4 5 17 38 67 70
Data: 1/03/2000 Ruota: Enna Valori: 20 28 66 69 Estrazione: 20 28 56 66 69 85
Data: 6/02/2000 Ruota: Macerata Valori: 28 34 62 76 Estrazione: 28 34 44 59 62 76
Data: 5/02/2000 Ruota: Biella Valori: 11 29 75 78 Estrazione: 11 29 57 75 78 81
Data: 8/12/1999 Ruota: Piacenza Valori: 13 44 52 57 Estrazione: 13 44 45 52 57 84
Data: 2/10/1999 Ruota: Pisa Valori: 35 42 45 85 Estrazione: 11 35 42 45 81 85
Data: 8/09/1999 Ruota: Pistoia Valori: 31 42 81 90 Estrazione: 7 31 32 42 81 90
Data: 7/08/1999 Ruota: Caltanissetta Valori: 12 23 28 53 56 Estrazione: 12 23 28 53 56 65
Data: 4/07/1999 Ruota: Udine Valori: 62 72 78 81 Estrazione: 40 53 62 72 78 81
Data: 5/06/1999 Ruota: Pisa Valori: 9 13 41 87 Estrazione: 9 13 19 40 41 87
Data: 9/05/1999 Ruota: Perugia Valori: 2 14 31 46 59 Estrazione: 2 8 14 31 46 59
Data: 2/05/1999 Ruota: Brindisi Valori: 15 26 76 77 Estrazione: 15 26 28 76 77 90
Data: 5/05/1999 Ruota: Genova Valori: 6 21 31 33 Estrazione: 6 21 31 33 42 85
Data: 7/03/1999 Ruota: Caserta Valori: 1 10 37 81 Estrazione: 1 10 37 70 74 81
Data: 6/03/1999 Ruota: Avellino Valori: 12 32 71 83 Estrazione: 12 32 33 69 71 83
Data: 3/02/1999 Ruota: Roma Valori: 15 22 56 64 Estrazione: 1 15 22 56 64 71
Data: 3/02/1999 Ruota: Frosinone Valori: 13 44 52 57 Estrazione: 13 39 44 52 57 62
Data: 9/01/1999 Ruota: Enna Valori: 5 15 39 75 Estrazione: 5 15 38 39 57 75
Data: 2/01/1999 Ruota: Pistoia Valori: 15 26 81 84 Estrazione: 15 26 31 48 81 84
Data: 2/12/1998 Ruota: Ferrara Valori: 3 50 86 89 Estrazione: 3 5 50 86 87 89
Data: 7/10/1998 Ruota: Messina Valori: 23 35 55 82 Estrazione: 23 35 47 55 81 82
Data: 2/08/1998 Ruota: Modena Valori: 22 27 50 52 Estrazione: 22 27 30 50 52 53
Data: 1/08/1998 Ruota: Verbano-Cusio-Ossola Valori: 14 17 50 69 Estrazione: 14 17 47 50 69 88
Data: 6/06/1998 Ruota: Enna Valori: 26 32 47 81 Estrazione: 17 26 28 32 47 81
Data: 0/05/1998 Ruota: MedioCampidano Valori: 1 40 42 74 Estrazione: 1 30 40 42 74 77
Data: 9/05/1998 Ruota: Latina Valori: 18 57 61 77 Estrazione: 18 19 57 61 62 77
Data: 8/03/1998 Ruota: Grosseto Valori: 6 65 71 82 Estrazione: 6 29 32 65 71 82
Data: 7/02/1998 Ruota: Gorizia Valori: 32 40 70 90 Estrazione: 28 32 40 48 70 90
Data: 9/11/1997 Ruota: Pesaro-Urbino Valori: 17 49 77 85 Estrazione: 17 23 49 61 77 85
Data: 1/11/1997 Ruota: Caltanissetta Valori: 32 35 66 76 90 Estrazione: 24 32 35 66 76 90
Data: 1/11/1997 Ruota: Piacenza Valori: 13 17 22 87 Estrazione: 13 17 22 24 79 87
Data: 5/10/1997 Ruota: Agrigento Valori: 16 32 60 90 Estrazione: 16 32 40 51 60 90
Data: 8/10/1997 Ruota: L'Aquila Valori: 18 42 54 74 Estrazione: 18 41 42 44 54 74
Data: 6/07/1997 Ruota: Pordenone Valori: 5 18 52 55 Estrazione: 5 14 18 52 55 73
Data: 9/03/1997 Ruota: Nuoro Valori: 29 36 47 82 Estrazione: 29 36 47 48 72 82
Data: 1/03/1997 Ruota: Perugia Valori: 14 46 51 59 Estrazione: 10 14 46 51 59 83
Data: 2/02/1997 Ruota: Roma Valori: 14 33 50 70 Estrazione: 14 33 50 52 70 81
Data: 4/01/1997 Ruota: Nuoro Valori: 13 51 57 65 Estrazione: 1 13 51 57 65 86
Data: 3/11/1996 Ruota: Avellino Valori: 34 62 63 64 Estrazione: 4 34 59 62 63 64
Data: 9/11/1996 Ruota: Bari Valori: 5 52 55 57 Estrazione: 5 52 55 57 84 85
Data: 9/10/1996 Ruota: Verbano-Cusio-Ossola Valori: 8 19 44 64 Estrazione: 8 19 44 64 69 88
Data: 7/08/1996 Ruota: Forlì-Cesena Valori: 23 27 37 49 Estrazione: 22 23 27 34 37 49
Data: 7/07/1996 Ruota: Caserta Valori: 20 38 72 75 Estrazione: 20 34 38 69 72 75
Data: 0/04/1996 Ruota: Savona Valori: 13 36 67 82 Estrazione: 13 25 36 46 67 82
Data: 3/04/1996 Ruota: Lodi Valori: 20 28 32 74 Estrazione: 11 20 28 32 64 74
Data: 0/03/1996 Ruota: Savona Valori: 5 19 52 56 Estrazione: 5 14 19 52 56 73
Data: 0/03/1996 Ruota: Udine Valori: 22 27 50 52 Estrazione: 22 27 50 52 54 73
Data: 7/02/1996 Ruota: Lecce Valori: 14 16 79 84 Estrazione: 1 14 16 27 79 84
Data: 3/01/1996 Ruota: Torino Valori: 39 44 52 90 Estrazione: 10 39 44 52 81 90
Data: 9/08/1995 Ruota: Olbia-Tempio Valori: 23 54 63 70 Estrazione: 23 54 55 63 70 80
Data: 2/08/1995 Ruota: Piacenza Valori: 38 42 44 87 Estrazione: 14 37 38 42 44 87
Data: 9/07/1995 Ruota: Trapani Valori: 6 39 64 86 Estrazione: 6 8 18 39 64 86
Data: 1/07/1995 Ruota: Imperia Valori: 1 10 44 80 Estrazione: 1 2 10 32 44 80
Data: 3/06/1995 Ruota: Bergamo Valori: 1 14 22 63 Estrazione: 1 14 22 55 63 76
Data: 9/04/1995 Ruota: Cosenza Valori: 39 44 52 90 Estrazione: 39 40 41 44 52 90
Data: 5/04/1995 Ruota: Rieti Valori: 34 48 70 76 Estrazione: 34 48 62 70 76 77
Data: 5/04/1995 Ruota: Roma Valori: 27 39 41 48 Estrazione: 27 39 41 48 50 88
Data: 5/03/1995 Ruota: Foggia Valori: 54 60 66 69 Estrazione: 22 54 55 60 66 69
Data: 8/03/1995 Ruota: Bolzano Valori: 29 44 61 71 Estrazione: 29 40 44 61 71 88
Data: 8/03/1995 Ruota: Nuoro Valori: 38 67 77 82 Estrazione: 13 38 50 67 77 82
Data: 5/02/1995 Ruota: Sondrio Valori: 19 46 73 76 Estrazione: 2 4 19 46 73 76
Data: 1/02/1995 Ruota: Catanzaro Valori: 17 33 82 89 Estrazione: 17 33 68 69 82 89
Data: 7/01/1995 Ruota: Carbonia-Iglesias Valori: 12 46 59 74 Estrazione: 7 12 27 46 59 74
Data: 7/01/1995 Ruota: Parma Valori: 6 20 30 36 38 Estrazione: 6 20 30 36 38 60
Data: 4/12/1994 Ruota: Piacenza Valori: 28 40 56 57 Estrazione: 28 35 40 56 57 76
Data: 9/11/1994 Ruota: Torino Valori: 2 39 40 42 Estrazione: 2 33 39 40 42 68
Data: 1/10/1994 Ruota: Lucca Valori: 1 31 64 83 Estrazione: 1 31 52 64 77 83
Data: 7/09/1994 Ruota: Cremona Valori: 27 61 81 90 Estrazione: 27 47 57 61 81 90
Data: 0/08/1994 Ruota: Latina Valori: 23 33 75 85 Estrazione: 5 23 33 75 82 85
Data: 3/08/1994 Ruota: Roma Valori: 22 26 35 49 Estrazione: 22 26 35 49 76 88
Data: 6/08/1994 Ruota: Siracusa Valori: 14 17 50 69 Estrazione: 14 17 50 69 75 82
Data: 0/07/1994 Ruota: Vercelli Valori: 21 52 59 64 Estrazione: 9 21 52 59 64 65
Data: 9/07/1994 Ruota: Venezia Valori: 14 60 82 84 Estrazione: 14 55 60 61 82 84
Data: 8/06/1994 Ruota: Lecco Valori: 7 24 78 89 Estrazione: 7 24 32 51 78 89
Data: 1/06/1994 Ruota: Salerno Valori: 15 19 42 66 Estrazione: 8 15 19 42 44 66
Data: 8/05/1994 Ruota: Crotone Valori: 56 62 75 81 Estrazione: 1 43 56 62 75 81
Data: 0/04/1994 Ruota: Taranto Valori: 1 52 68 79 Estrazione: 1 44 52 68 79 86
Data: 6/04/1994 Ruota: Chieti Valori: 7 18 21 46 Estrazione: 7 18 21 22 46 87
Data: 6/04/1994 Ruota: Perugia Valori: 1 40 42 74 Estrazione: 1 40 42 60 74 82
Data: 9/04/1994 Ruota: Massa-Carrara Valori: 4 51 60 74 Estrazione: 4 51 60 64 74 88
Data: 9/04/1994 Ruota: Perugia Valori: 17 33 82 89 Estrazione: 17 33 63 74 82 89
Data: 6/03/1994 Ruota: Treviso Valori: 1 4 30 34 Estrazione: 1 4 8 30 34 64
Data: 9/03/1994 Ruota: Novara Valori: 22 23 36 57 Estrazione: 22 23 36 57 60 73
Data: 9/03/1994 Ruota: Imperia Valori: 1 40 42 74 Estrazione: 1 40 42 52 74 75
Data: 5/02/1994 Ruota: Sondrio Valori: 13 17 22 87 Estrazione: 13 17 22 31 76 87
Data: 1/12/1993 Ruota: Taranto Valori: 15 19 45 76 Estrazione: 15 19 45 75 76 89
Data: 6/11/1993 Ruota: Perugia Valori: 16 20 60 63 Estrazione: 8 16 20 37 60 63
Data: 2/10/1993 Ruota: ViboValentia Valori: 18 22 76 84 Estrazione: 7 18 22 37 76 84
Data: 4/08/1993 Ruota: Como Valori: 10 26 33 56 Estrazione: 10 26 27 33 56 85
Data: 7/07/1993 Ruota: Pescara Valori: 5 22 34 60 Estrazione: 5 7 22 34 60 74
Data: 9/06/1993 Ruota: Latina Valori: 22 28 46 64 Estrazione: 22 28 46 64 77 88
Data: 2/06/1993 Ruota: Grosseto Valori: 36 47 62 89 Estrazione: 3 36 47 62 71 89
Data: 5/06/1993 Ruota: Lucca Valori: 11 24 45 90 Estrazione: 5 11 24 45 49 90
Data: 2/05/1993 Ruota: Bergamo Valori: 2 36 60 76 Estrazione: 2 36 37 60 67 76
Data: 0/04/1993 Ruota: Rimini Valori: 5 21 33 90 Estrazione: 5 14 21 33 57 90
Data: 0/03/1993 Ruota: Lucca Valori: 26 32 47 81 Estrazione: 24 26 32 47 55 81
Data: 7/02/1993 Ruota: Asti Valori: 8 10 54 85 Estrazione: 8 10 54 56 85 90
Data: 0/02/1993 Ruota: Sondrio Valori: 10 13 18 62 Estrazione: 10 13 18 29 58 62
Data: 3/01/1993 Ruota: Chieti Valori: 11 44 77 81 Estrazione: 11 44 68 69 77 81
Data: 3/01/1993 Ruota: Cosenza Valori: 19 23 41 69 Estrazione: 19 23 24 41 44 69
Data: 2/01/1993 Ruota: Cuneo Valori: 55 62 67 71 Estrazione: 6 55 62 67 71 82
Data: 6/12/1992 Ruota: Carbonia-Iglesias Valori: 4 39 47 82 Estrazione: 4 22 26 39 47 82
Data: 1/11/1992 Ruota: Trapani Valori: 23 30 72 78 Estrazione: 23 30 33 45 72 78
Data: 1/10/1992 Ruota: Forlì-Cesena Valori: 11 23 52 76 Estrazione: 11 23 52 65 76 82
Data: 6/09/1992 Ruota: Aosta Valori: 35 58 74 85 Estrazione: 14 24 35 58 74 85
Data: 9/09/1992 Ruota: Vercelli Valori: 16 46 66 75 Estrazione: 16 46 66 70 75 82
Data: 2/09/1992 Ruota: Napoli Valori: 69 70 76 82 Estrazione: 8 34 69 70 76 82
Data: 2/09/1992 Ruota: Massa-Carrara Valori: 21 22 34 54 Estrazione: 21 22 28 34 54 55
Data: 9/08/1992 Ruota: Carbonia-Iglesias Valori: 23 39 40 76 Estrazione: 7 23 39 40 62 76
Data: 5/07/1992 Ruota: Roma Valori: 11 35 40 83 Estrazione: 11 14 35 40 83 90
Data: 5/07/1992 Ruota: Udine Valori: 13 29 42 78 Estrazione: 13 23 29 42 44 78
Data: 8/07/1992 Ruota: Crotone Valori: 3 50 86 89 Estrazione: 3 29 50 70 86 89
Data: 1/07/1992 Ruota: Roma Valori: 30 37 50 79 Estrazione: 30 37 42 50 79 83
Data: 4/07/1992 Ruota: Asti Valori: 1 4 5 41 Estrazione: 1 4 5 36 41 47
Data: 3/06/1992 Ruota: ViboValentia Valori: 22 54 61 82 Estrazione: 21 22 32 54 61 82
Data: 6/05/1992 Ruota: Frosinone Valori: 14 17 50 69 Estrazione: 7 14 17 22 50 69
Data: 2/05/1992 Ruota: LaSpezia Valori: 13 29 42 78 Estrazione: 13 29 39 42 71 78
Data: 1/12/1991 Ruota: Bolzano Valori: 5 46 55 66 Estrazione: 5 17 34 46 55 66
Data: 7/12/1991 Ruota: Rimini Valori: 26 36 67 70 Estrazione: 4 26 36 67 70 83
Data: 6/11/1991 Ruota: Catania Valori: 22 34 57 76 Estrazione: 22 32 34 57 63 76
Data: 4/09/1991 Ruota: Olbia-Tempio Valori: 1 20 30 32 Estrazione: 1 18 20 30 32 44
Data: 1/08/1991 Ruota: Udine Valori: 33 51 61 77 Estrazione: 11 33 39 51 61 77
Data: 4/08/1991 Ruota: Oristano Valori: 46 47 49 67 Estrazione: 41 46 47 49 67 71
Data: 0/07/1991 Ruota: Sondrio Valori: 2 3 46 53 Estrazione: 2 3 15 17 46 53
Data: 8/06/1991 Ruota: Bari Valori: 1 20 30 32 Estrazione: 1 20 30 32 34 76
Data: 7/04/1991 Ruota: Pisa Valori: 18 47 74 88 Estrazione: 18 33 47 74 88 89
Data: 4/11/1990 Ruota: Asti Valori: 4 21 55 82 Estrazione: 4 21 34 55 82 86
Data: 7/10/1990 Ruota: Forlì-Cesena Valori: 42 47 63 80 Estrazione: 42 45 47 63 75 80
Data: 2/09/1990 Ruota: Chieti Valori: 1 3 65 78 Estrazione: 1 3 30 48 65 78
Data: 1/09/1990 Ruota: Bologna Valori: 15 22 56 64 Estrazione: 15 22 55 56 64 72
Data: 7/07/1990 Ruota: Caltanissetta Valori: 10 21 24 57 Estrazione: 10 21 24 40 55 57
Data: 6/05/1990 Ruota: Lecco Valori: 36 49 53 70 Estrazione: 20 26 36 49 53 70
Data: 8/04/1990 Ruota: Catania Valori: 1 4 43 63 Estrazione: 1 4 6 43 63 68
Data: 1/04/1990 Ruota: Chieti Valori: 16 23 48 74 Estrazione: 16 23 48 68 74 81
Data: 1/04/1990 Ruota: Catanzaro Valori: 10 44 55 64 Estrazione: 2 4 10 44 55 64
Data: 7/04/1990 Ruota: Parma Valori: 28 33 60 76 Estrazione: 2 28 33 56 60 76
Data: 0/03/1990 Ruota: Pistoia Valori: 9 19 41 89 Estrazione: 9 12 19 41 54 89
Data: 0/01/1990 Ruota: AscoliPiceno Valori: 2 3 46 53 Estrazione: 2 3 46 53 62 81
Data: 6/12/1989 Ruota: Verbano-Cusio-Ossola Valori: 4 18 29 42 Estrazione: 4 18 29 32 42 61
Data: 4/11/1989 Ruota: Ragusa Valori: 13 38 60 62 Estrazione: 6 13 38 43 60 62
Data: 6/09/1989 Ruota: Brescia Valori: 23 27 37 49 Estrazione: 8 23 27 37 49 83
Data: 9/09/1989 Ruota: Olbia-Tempio Valori: 5 29 39 66 Estrazione: 5 29 39 59 66 75

comunque io ho usato le STL non è colpa mia se ci mette di più :O :mc:

[Vincenzo1968]

Ohé Gugo,

una domanda: le date, in output, debbono rispettare un ordine particolare(crescente, decrescente) o va bene così come si trovano nel file di origine?

[rеpne scasb]

■

[banryu79]

Alè repne scasb :ave:
(seguo sempre i contest di GugoXX con interesse)

[Vincenzo1968]

...
*** Tempo per caricamento dati e creazione strutture: 0.890 secondi

*** Tempo per ricerca della soluzione difficile: 0.000 secondi

*** Tempo totale per l'intera elaborazione: 0.890 secondi
[/CODE]

Tempo per sviluppare il software 2 ore.

Sui tempi di calcolo, e' possibile aumentare le prestazioni di un ordine di grandezza con poche modifiche al codice, scendendo cosi' sotto il decimo di secondo. E' anche possibile andare assai piu' rapidi di cosi'.

Grande!

Puoi spiegare un po' l'algoritmo(e soprattutto le ottimizzazioni per scendere sotto il decimo di secondo)?

Ciao :)

[k0nt3]

ho ottimizzato un attimino il codice per non fare proprio schifo:

#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <time.h>
#include <vector>

using namespace std;

class Ruota {
public:
Ruota(string data, string ruota, map<int,int> &estrazioni) {
m_estrazioni = estrazioni;
m_data = data;
m_ruota = ruota;
}

string getData() {
return m_data;
}

string getRuota() {
return m_ruota;
}

bool contiene(vector<int> &valori) {
for(unsigned int i = 0; i<valori.size(); ++i ) {
if(m_estrazioni.count(valori[i]) == 0) {
return false;
}
}
return true;
}

private:
map<int,int> m_estrazioni;
string m_data, m_ruota;
};

vector<string> trova(ifstream &dataFile, ifstream &findFile) {
vector<string> results;
vector<int>* valori;
int numRighe;
string tmp;
char ch;

findFile >> tmp >> numRighe;
valori = new vector<int>[numRighe];

for(int i=0; i<numRighe; ++i) {
char line[50];
findFile.getline(line, 50);
if(line[0] == 13) {
--i;
continue;
}

stringstream lineStream(line);
while(lineStream.good()) {
int valore;
lineStream >> valore >> ch;
valori[i].push_back(valore);
}
}

int numRuote, numValori;
dataFile >> tmp >> numRuote;
dataFile >> tmp >> numValori;

while(dataFile.good()) {
string data, ruota;
map<int,int> estrazioni;
dataFile >> data >> ruota;

for(int i=0; i<numValori; ++i) {
int estrazione;
char sep;
dataFile >> estrazione >> sep;
estrazioni[estrazione] = 1;
}

Ruota r(data, ruota, estrazioni);
for(int i=0; i<numRighe; ++i) {
if(r.contiene(valori[i])) {
stringstream result;
result << "Data: " << r.getData() << " Ruota: " << r.getRuota() << " Valori:";
for(unsigned int j = 0; j<valori[i].size(); ++j ) {
result << " " << valori[i][j];
}
results.push_back(result.str());
}
}
}
return results;
}

int main(int argc, char** argv) {
if(argc < 3)
return -1;

ifstream dataFile(argv[1]);
ifstream findFile(argv[2]);
if(findFile.is_open() && dataFile.is_open()) {
clock_t start, end;
start = clock();
vector<string> results = trova(dataFile, findFile);
end = clock();
dataFile.close();
findFile.close();

ofstream out("output.txt");
vector<string>::iterator it;
for(it = results.begin(); it != results.end(); it++ ) {
out << (*it) << endl;
}
cout << "Ci ho messo ben " << ((end-start)*1000)/CLOCKS_PER_SEC << "millisecondi" << endl;
}
else
cout << "Unable to open file" << endl;
}

ora con il difficile ci vogliono circa 7 secondi (su un pentium M 1,7Ghz)
su linux con le stesse ottimizzazioni (-O2) ci mette 5 secondi :fagiano:

[rеpne scasb]

■

[ercand]

*** Tempo per ricerca della soluzione difficile: 0.000 secondi


Il mio a trovare la soluzione il mio ci mette 1.9 secondi per il file difficile, e non so come migliorarla:fagiano: , e tu gia a 0 secondi:cry: .

[magix2003]

La mia soluzione da 20 sec netti la posto, o faccio solo brutta figura?? :cool:

La posto e chissenefrega, almeno è semplice da capire!


/**
* laRicerca: ArrayList ordinato dei numeri da ricercare
* tramite funzione sort offerta da Collections
* estrazione: idem qui per i valori dell'estrazione
*
* Poi uso il metodo containsAll per vedere se i valori da cercare
* sono contenuti
*/
private void bruteForce() {
Ricerca laRicerca;
Estrazione estrazione ;
for(int i = 0; i < findList.size(); i++) {
laRicerca = findList.get(i);
System.out.println(laRicerca);
for(int j = 0; j < theList.size(); j++) {
estrazione = theList.get(j);
if(estrazione.getTheValues().containsAll(laRicerca.getTheList())) {
System.out.println(estrazione);
}
}
}
}


Ok, probabilmente la funzione ContainsAll è il collo di bottiglia, visto che non credo sia implementata decentemente.

[rеpne scasb]

■

[okay]

Nuova versione:

*** Tempo per caricamento dati e creazione strutture: 0.047 secondi

*** Tempo per ricerca della soluzione difficile: 0.000 secondi

*** Tempo totale per l'intera elaborazione: 0.047 secondi
[/CODE]

Tempo utilizzato per modificare il codice: 15 min.

Mi sono accorta che la versione precedente, nonostante non avesse bachi visibili, non era accurata, oltre che ridondante. Posso scendere di un altro ordine di grandezza, senza utilizzare 4Gb di RAM+64-bit.

Buongiorno, è proprio un grande piacere leggerti...:)

[k0nt3]

@rеpne scasb
a me dice che il file non è corretto (ho modificato le define in modo da caricare i miei file)

[rеpne scasb]

■

[rеpne scasb]

■

[ndakota]

repne ho provato ad eseguire quest'ultimo sul mio pc. questi i risultati:
*** Tempo per caricamento dati e creazione strutture: 0.365 secondi

*** Tempo per ricerca della soluzione difficile: 0.399 secondi

*** Tempo totale per l'intera elaborazione: 0.764 secondi

Process returned 0 (0x0) execution time : 0.788 s
Press any key to continue.

[rеpne scasb]

■

[ndakota]

mi chiedi troppo sono un novellino :p
comunque il mio pc è una via di mezzo tra i due da te postati: intel core 2 duo t5500(1.66 Ghz) 2 gb ddr2 windows vista 32 bit.

[rеpne scasb]

■

[ndakota]

eccoli

*** Tempo per caricamento dati e creazione strutture: 0.363 secondi

*** Tempo per ricerca della soluzione difficile: 0.007 secondi

*** Tempo totale per l'intera elaborazione: 0.370 secondi


:p

[Vincenzo1968]

Questi sono i tempi di repne sulla mia macchina(compilatore: visual studio 2008):

La mia macchina:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 3


Output a video:
http://www.guidealgoritmi.it/images/ImgForums/contest07repne1.jpg

Redirezione su file:
http://www.guidealgoritmi.it/images/ImgForums/contest07repne2.jpg

[Vincenzo1968]

La mia soluzione da 20 sec netti la posto, o faccio solo brutta figura?? :cool:

La posto e chissenefrega, almeno è semplice da capire!
...
Ok, probabilmente la funzione ContainsAll è il collo di bottiglia, visto che non credo sia implementata decentemente.

Ciao magix,

puoi postare il codice per intero?
Vorrei fare un confronto fra le varie soluzioni proposte prendendo i tempi su un'unica macchina(invito tutti gli altri a fare lo stesso).

[Vincenzo1968]

...
L'algoritmo, non e' nulla di speciale, tranne una considerazione sulla disposizione degli elementi di una funzione discreta crescente a piu' variabili (che nonostante i paroloni non e' nulla di speciale).
...


Repne ciao,

scusa se insisto ma di matematica non ci capisco niente(proprio il niente che è niente).
Conservo in una cartella che ho chiamato "programming pearls" (il nome l'ho preso in prestito dal bel libro di Jon Bentley) il tuo intervento nel contest 3 e la tua spiegazione sul teorema del limite centrale. Mi piacerebbe aggiungere un'altra "pearl" a quella cartella. :)

[banryu79]

Repne ciao,

scusa se insisto ma di matematica non ci capisco niente(proprio il niente che è niente).
Conservo in una cartella che ho chiamato "programming pearls" (il nome l'ho preso in prestito dal bel libro di Jon Bentley) il tuo intervento nel contest 3 e la tua spiegazione sul teorema del limite centrale. Mi piacerebbe aggiungere un'altra "pearl" a quella cartella. :)
Quoto in toto dato che anch'io ho conservato e consultato a suo tempo quella soluzione.
Una spiegazione matematica sarebbe veramente interessante :)

[magix2003]

Come richiesto:

il codice è un po' cambiato, ora ci mette di meno.

[rеpne scasb]

■

[Vincenzo1968]

Come richiesto:

il codice è un po' cambiato, ora ci mette di meno.

Grazie magix ;)

Approfitto per rinnovare il mio invito: oltre a postare il codice per intero, ognuno di noi potrebbe confrontare le versioni proposte sulla propria macchina e postare i risultati(possibilmente incolonnati in una bella tabella contenente nome dell'autore, linguaggio, compilatore e tempi di esecuzione).

[Vincenzo1968]

Preparo un file dove commento il mio ultimo codice riga per riga spiegando, con il maggiore dettaglio di cui sono capace (che non e' molto) il tutto. Sono sicura, che dopo aver chiarito come funziona il software, apparira' piu' che altro come un uovo di Colombo.

Vorrei pero' aspettare, in quanto qualcuno potrebbe avere un idea decisamente migliore, qui comincerebbe un contest interessante. Sto preparando in questo caso un file con 10.000.000 di estrazioni e 1.000 ruote 7 numeri estratti a ruota, e un file di ricerca con da 100.000 elementi con 4,5,6 numeri giocati.

Perfetto. Grazie mille :)

[Vincenzo1968]

ho ottimizzato un attimino il codice
...
ora con il difficile ci vogliono circa 7 secondi (su un pentium M 1,7Ghz)
su linux con le stesse ottimizzazioni (-O2) ci mette 5 secondi :fagiano:

Ciao Kont,

sulla mia macchina impiega poco più di 6 secondi. Solo, dovresti aggiustare un attimo l'output, come specificato nel post iniziale di Gugo.

Ciao

[Vincenzo1968]

Installa Ruby 1.9 poi metti il codice in un file e da linea di comando basta dare ruby file.rb. I File txt con i dati devono essere nella stessa cartella del file rb da cui lanci il programma.

Ho provato il tuo codice. Mi da questi errori:
http://www.guidealgoritmi.it/images/ImgForums/ErroreRuby.jpg

Questo è il contenuto del file Lotto.rb:


def benchmark(label)
print "#{label}..."
start_time = Time.now
result = yield
puts " completato. (#{(Time.now - start_time).to_s} secondi)"
result
end

def load_data(file_name)
estrazioni = Array.new
File.open(file_name, 'r') do |f|
f.gets; f.gets # ignora le prime due righe
while line = f.gets
data, ruota, valori = line.chop.split
estrazioni << { data: data, ruota: ruota, valori: valori.split(',').map { |x| x.to_i} }
end
end
estrazioni
end

def load_find(file_name)
ricerche = Array.new
File.open(file_name, 'r') do |f|
f.gets # ignora la prima riga
while line = f.gets
ricerche << line.chop.split(',').map { |x| x.to_i }
end
end
ricerche
end

def contains(e, r)
r.each do |v|
return false if !e.include? v
end
true
end

def search(estrazioni, ricerche)
ricerche.each do |r|
puts "-- #{r.inspect} --"
estrazioni.each do |e|
puts "#{e[:data]} #{e[:ruota]} #{e[:valori].inspect}" if contains(e[:valori], r)
end
end
end

estrazioni = benchmark('Caricamento delle estrazioni') { load_data('LottoDataDifficile.txt') }
ricerche = benchmark('Caricamento delle ricerche') { load_find('LottoFindDifficile.txt') }
benchmark('Ricerca dei valori') { search(estrazioni, ricerche) }

[magix2003]

ho ottimizzato un attimino il codice per non fare proprio schifo:
cut code
ora con il difficile ci vogliono circa 7 secondi (su un pentium M 1,7Ghz)
su linux con le stesse ottimizzazioni (-O2) ci mette 5 secondi :fagiano:

Da me ci mette due secondi. Comunque il risultato non mi pare corretto.
Con quell'algoritmo tu listi semplicemente tutte le ruote che soddisfano il criterio di ricerca. L'output invece dovrebbe essere:

(RICERCA) 45,32

Insieme delle estrazione che presentano l'ambo 45,32

e così via.

[Vincenzo1968]

Questo è un primo confronto:
http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica01.jpg

La macchina è questa:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 2


Manca il risultato di Vicius e di Magix2003.
Magix, compilando con Eclipse mi da il seguente errore:

The declared package "lotto" does not match the expected package ""

Probabilmente saranno errori facili da correggere ma non m'intendo né di Java, né di Ruby. Illuminatemi :)

[Mesh89]

Questo è un primo confronto:
http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica01.jpg

La macchina è questa:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 2


Manca il risultato di Vicius e di Magix2003.
Magix, compilando con Eclipse mi da il seguente errore:

The declared package "lotto" does not match the expected package ""

Probabilmente saranno errori facili da correggere ma non m'intendo né di Java, né di Ruby. Illuminatemi :)

Però ha poco senso confrontare i tempi tra C++ e ruby...

[rеpne scasb]

■

[rеpne scasb]

■

[VICIUS]

Ho provato il tuo codice. Mi da questi errori:
http://www.guidealgoritmi.it/images/ImgForums/ErroreRuby.jpg

Questo è il contenuto del file Lotto.rb:


Non mi ero accorto di aver usato la sintassi breve per gli hash presente solo su 1.9.

Sostituisci questo:
estrazioni << { data: data, ruota: ruota, valori: valori.split(',').map { |x| x.to_i} }
Con questo:
estrazioni << { :data => data, :ruota => ruota, :valori => valori.split(',').map { |x| x.to_i} }

[cdimauro]

Ma tu guarda: hanno copiato pari pari la sintassi di Python per i dizionari. :p

[Vincenzo1968]

Però ha poco senso confrontare i tempi tra C++ e
ruby...

Ehm Mesh,

non saprei... solitamente in un contest si confrontano i tempi. Potremmo dividere le classifiche in due parti: una per i linguaggi compilati e un'altra per i linguaggi interpretati. In questo caso, Java e C#(a causa del JIT, dico) dove dovrebbero stare? :confused:

[Vincenzo1968]

Forse e' il caso di passare ad una coppia di file piu' pesanti per capire il comportamendo dei vari algoritmi. A questo link: http://www.usaupload.net/d/1fzh7nkp97s ci sono due nuovi file il primo ha 250 ruote 4000 estrazioni per un totale di 1.000.000 di elementi; il secondo ha un "Find" di 10.000 elementi. I due file sono circa 10 volte piu' grandi dei precedenti.

Questo sono i tempo ottenuti sulla mia macchina:


*** Tempo per caricamento dati e creazione strutture: 0.594 secondi

*** Tempo per ricerca della soluzione difficile: 0.250 secondi

*** Tempo totale per l'intera elaborazione: 0.844 secondi


Ok, provvedo ad aggiornare la classifica.

[cdimauro]

Ehm Mesh,

non saprei... solitamente in un contest si confrontano i tempi. Potremmo dividere le classifiche in due parti: una per i linguaggi compilati e un'altra per i linguaggi interpretati. In questo caso, Java e C#(a causa del JIT, dico) dove dovrebbero stare? :confused:
E' meglio parlare di implementazione interpretata / compilata di un linguaggio.

Un linguaggio definisce una sintassi e una sematica. Poi le sue implementazioni possono essere interpretate o compilate, è indifferente (esistono interpreti C, ad esempio).

Java, C#, Python e altre implementazioni di linguaggi che provvedono a compilare in bytecode / forma intermedia sono... compilati. Per definizione. ;)

[Vincenzo1968]

Non mi ero accorto di aver usato la sintassi breve per gli hash presente solo su 1.9.

Sostituisci questo:
estrazioni << { data: data, ruota: ruota, valori: valori.split(',').map { |x| x.to_i} }
Con questo:
estrazioni << { :data => data, :ruota => ruota, :valori => valori.split(',').map { |x| x.to_i} }

Grazie Vicius,

non ho scaricato la versione 1.9 perché non è ancora stabile. Come ho già scritto, a una prima lettura della documentazione l'ho trovato interessante come linguaggio. Mi piace, per esempio, la chiusura dei blocchi con end piuttosto che a colpi di tab o spazi :fiufiu:. È solo la mia opinione, questione di gusti. Può darsi che decida in seguito di utilizzarlo per qualche progetto e ho preferito, dunque, scaricare la versione stabile.

[Vincenzo1968]

E' meglio parlare di implementazione interpretata / compilata di un linguaggio.

Un linguaggio definisce una sintassi e una sematica. Poi le sue implementazioni possono essere interpretate o compilate, è indifferente (esistono interpreti C, ad esempio).

Java, C#, Python e altre implementazioni di linguaggi che provvedono a compilare in bytecode / forma intermedia sono... compilati. Per definizione. ;)

Ok, allora li metto tra i linguaggi compilati.

[rеpne scasb]

■

[Vincenzo1968]

E' possibile normalizzare, a parita' di hardware ed eseguibile, tutti i software presenti nel contest epurando i risultati dal linguaggio di programmazione. Ad esempio vuoi testare il software xxx dell'utente yyy, allora:

1) Sia t1 il tempo registrato sulla tua macchina per la generazione della soluzione con i file originari.
2) Sia t2 il tempo registrato sulla tua macchina con i nuovi file che ho sottoposto.
3) Considera la quantita t2/t1. Piu' e' bassa migliore e' l'algoritmo.
4) Stila la classifica dal piu' basso rapporto t2/t1 al piu' alto.

In questo modo contera' solo l'algoritmo e non il linguaggio o le ottimizzazioni del compilatore.

Ottimo!

Se ne parla domani sera però, ché domattina mi debbo alzare alle prime luci dell'alba :cry:

:)

[Vincenzo1968]

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.

:)

[VICIUS]

Non riesco a prendere sonno così mi sono messo a fare qualche modifica. La nuova versione è circa il 39% più veloce.
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) }
Molto semplicemente ho sostituito il ciclo che cercava se i valori erano contenuti nelle estrazioni con un confronto tra due integer.

[^TiGeRShArK^]

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.

:)

io sto ancora cercando un'operazione commutativa che dato un insieme di numeri restituisca un risultato univoco..che immagino sia la cosa + efficiente da fare..:fagiano:
..però ho potuto dedicarci solo un pò di tempo stasera prima di uscire e non ho trovato niente che faccia al caso mio.. :sob:
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... :muro:
(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 :p)

[rеpne scasb]

■

[k0nt3]

@rеpne scasb
scusa la domanda ma.. il tuo algoritmo funziona se il numero di valori per ogni estrazione è diverso da 6?

[rеpne scasb]

■

[Mesh89]

Brutto segno. I nuovi due file sono circa 100 volte piu' pesanti, cio' indica che la versione di mesh ha una complessita' rispetto al tempo poco meno che lineare (probabilmente lineare), la complessita' del mio algoritmo e' decisamente piu' bassa si muove probabilmente con l'inverso del quadrato. Per fare un esempio, se utilizzassimo due nuovi file ancora 100 volte piu' pesanti, la mia versione impiegherebbe una 30 di secondi, quella di mesh, probabilmente, oltre 10.000.

Si, la mia soluzione dovrebbe essere a occhio lineare in f*r
Cmq sono ancora allibito dai tempi della tua soluzione, sembra una magia, che complessità ha?

[Vincenzo1968]

Classifica aggiornata:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica02.jpg

Ho escluso per il momento k0nt3. Aspettiamo che aggiusti l'output.

Magix, per quel problema con Eclipse che ti avevo segnalato, sai dirmi niente?

[Vincenzo1968]

Non riesco a prendere sonno così mi sono messo a fare qualche modifica. La nuova versione è circa il 39% più veloce.
...
Molto semplicemente ho sostituito il ciclo che cercava se i valori erano contenuti nelle estrazioni con un confronto tra due integer.

Vicius ehm...

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):


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) }


:)

[rеpne scasb]

■

[Mesh89]

La complessita' dovrebbe essere 1*r, ossia non dipende da Find, o meglio dipende pochissimo da f. Ad esempio, nei nuovi due file se invece di aumentare per 10 sia le estrazioni totali che Find, avessi aumentato di 100 volte solo find, il tuo algoritmo avrebbe fatto ugualmente 125 secondi, il mio sarebbe rimasto fermo a 0.2 secondi.

Un altra osservazione: il mio algoritmo e' praticamente indipendente (o meglio leggermente dipendente), da "valori", ossia dai numero degli estratti che nel nostro caso e' 6. Se i valori fossero stati 7,8,9, e il numero dei valori da testare 3,4,5,6,7 non ci sarebbero state praticamente differenze sui tempi misurati*.

* Non e' propriamente cosi', ma nel nostro caso, operando con piccole quantita' di dati, e praticamente vero.

Wow... Mi sembra abbastanza incredibile che non dipenda dal numero di find, a contest finito sarebbe carina una spiegazioncina :)
Ho buttato giù di un po' i tempi, anche se non dovrei arrivare nemmeno vicino a repne

#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;
}

[Vincenzo1968]

Vicius ehm...

so che ti sto scassando i cabasisi ma mi da errore. Puoi azzizzarmelo per la versione 1.8.7?
...


Come non detto. Ho scaricato la versione 1.9. Fra un po' posto la classifica aggiornata(tenendo conto anche della nuova versione di Mesh89).

[ercand]

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?

[Vincenzo1968]

Classifica aggiornata:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica03.jpg

Purtroppo non ho potuto inserire Vicius perchè, sul file grosso, dopo un po' se ne esce con questo messaggio:

http://www.guidealgoritmi.it/images/ImgForums/ErroreRuby2.jpg

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[Vincenzo1968]

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?

non so se siano 30041. Ti posto la parte finale dei risultati di Mesh e Repne:

mesh:

-- 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


repne:

-- 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

[Vincenzo1968]

Qualcuno che s'intende di Eclipse/Java?
Con i file postati da magix2003 ho questo problema:

http://www.guidealgoritmi.it/images/ImgForums/ErroreJava.jpg

[cionci]

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 ;)

#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;
}

[magix2003]

Probabilmente è perché hai importato i file senza creare il package. I file vanno inseriti all'interno di un package chiamato lotto.

Comunque eviterei di fare il nuovo test con il mio algoritmo, la complessità è troppo alta.

[cionci]

Qualcuno che s'intende di Eclipse/Java?
Con i file postati da magix2003 ho questo problema:
Devi creare il package Lotto ed spostare i file all'interno del package.

[Vincenzo1968]

Grazie :)

purtroppo anche Java, sul file grosso, ha problemi(su quello piccolo, il tempo registrato è di 24 secondi):

http://www.guidealgoritmi.it/images/ImgForums/ErroreJava2.jpg

[Vincenzo1968]

Ohé Cionci,

per sort e next_permutation mi dice "identifier not found" :cry:

[cionci]

Metti #include <algorithm> in cima.

Comunque non lo stare a testare...è lento ;)

[Vincenzo1968]

Metti #include <algorithm> in cima.

Comunque non lo stare a testare...è lento ;)

Eh no!
Alla fine chi perde dovrà indossare il sambenito per un mese intero :Perfido:

Tu sai di cosa parlo...

Un attimo e aggiorno la classifica ;)

[cionci]

Eh no!
Alla fine chi perde dovrà indossare il sambenito per un mese intero :Perfido:

Tu sai di cosa parlo...
:asd:

[rеpne scasb]

■

[^TiGeRShArK^]

come si può fare per ottenere un codice hash di un insieme? :mbe:
in java la funzione hashcode restituisce semplicemente la somma degli elementi (nel caso di interi o di stringhe), mentre in C# restituisce un codice univoco che è diverso per ogni insieme anche se ha gli stessi elementi.. :stordita:
a me servirebbe un codice hash che sia uguale per ogni insieme con gli stessi elementi e che sia univoco e quindi diverso per insiemi con elementi differenti.. :fagiano:
E algoritmi di hashing del genere non mi vengono in mente.. :stordita:

[gugoXX]

come si può fare per ottenere un codice hash di un insieme? :mbe:
in java la funzione hashcode restituisce semplicemente la somma degli elementi (nel caso di interi o di stringhe), mentre in C# restituisce un codice univoco che è diverso per ogni insieme anche se ha gli stessi elementi.. :stordita:
a me servirebbe un codice hash che sia uguale per ogni insieme con gli stessi elementi e che sia univoco e quindi diverso per insiemi con elementi differenti.. :fagiano:
E algoritmi di hashing del genere non mi vengono in mente.. :stordita:

Se ho ben capito puoi provare a pensare ad utilizzare la mia MultiDictionary, che e' un template con chiave multidimensionale...
Se vuoi la recupero e te la passo.
Prima o poi scrivero' anche io qualcosa per risolvere l'esercizio. Vedremo...
Questo weekend Ikea e olio di gomito.

[^TiGeRShArK^]

Se ho ben capito puoi provare a pensare ad utilizzare la mia MultiDictionary, che e' un template con chiave multidimensionale...
Se vuoi la recupero e te la passo.
Prima o poi scrivero' anche io qualcosa per risolvere l'esercizio. Vedremo...
Questo weekend Ikea e olio di gomito.
mmm..nel senso che a diverse chiavi assegna lo stesso hash?
beh...potrebbe andare bene, ma alza di un pò il tempo di calcolo mi sa..
passamela che la provo :D

[Mesh89]

Classifica aggiornata:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica03.jpg

Purtroppo non ho potuto inserire Vicius perchè, sul file grosso, dopo un po' se ne esce con questo messaggio:

http://www.guidealgoritmi.it/images/ImgForums/ErroreRuby2.jpg

C'è qualcosa che non quadra, il file grosso deve essere particolarmente sfigato e avere una distribuzione di valori non uniforme, perchè in linea teorica dovrebbe diminuire di 15-20 volte, ovviamente teoria e pratica differiscono, ma non è possibile che perda solo un 20%...

EDIT: effettivamente anche il piccolo si dimezza e basta... Programmare in winzozz mi nausea, appena il pc con linux finisce di ripartizionare ricontrollo e faccio un po' di test, può darsi che abbia sbagliato qualcosa nell'implementazione...

[gugoXX]

mmm..nel senso che a diverse chiavi assegna lo stesso hash?
beh...potrebbe andare bene, ma alza di un pò il tempo di calcolo mi sa..
passamela che la provo :D

No, forse non mi sono spiegato (o non ho capito la risposta)
La chiave puo' essere p.es 2 interi e una stringa, e il valore a piacere.

var dict = new MultiDictionary<int,int,string,string>();

dict[5,6,"pippo"] = "Pluto";
dict[4,7,"rosso"] = "Verde";


Il tempo e' un po' piu' alto della dictionary normale

[Vincenzo1968]

C'è qualcosa che non quadra, il file grosso deve essere particolarmente sfigato e avere una distribuzione di valori non uniforme, perchè in linea teorica dovrebbe diminuire di 15-20 volte, ovviamente teoria e pratica differiscono, ma non è possibile che perda solo un 20%...

Ciao Mesh,

non so se dipenda da questo ma, nelle classifiche iniziali, riportavo erroneamente solo il tempo di ricerca(parlo del tuo codice). Nelle ultime ho sommato il tempo di lettura input con il tempo di ricerca:


Lettura input: 18.172 secondi
Tempo per la ricerca: 85.61 secondi

Totale -> 103.782


Invito, come ho già fatto in precedenza, anche gli altri a stilare le stesse classifiche(meglio avere risultati su più macchine e/o sistemi operativi, no?) ;)

[Vincenzo1968]

Ohé Cionci,

purtroppo anche il tuo codice da problemi sul file grosso. Non da errori ma sembra non terminare mai e, alla fine, mi blocca tutto il sistema e mi tocca riavviare(e questo, caro Cionci, ti costerà caro: mo chiamo il Mons. e ti faccio raddoppiare la pena: due mesi, anziché uno, di sambenito :Perfido:).

La mia macchina è questa:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 3

[magix2003]

Questo è il vantaggio di avere una virtual machine, non ti fa bloccare il sistema se succhia tutta la RAM!

[Vincenzo1968]

Prima o poi scrivero' anche io qualcosa per risolvere l'esercizio. Vedremo...
Questo weekend Ikea e olio di gomito.

Il Mons. mi comunica che, visto che sei tu il promotore dell'iniziativa, se non posti una soluzione entro sette giorni... sambenito per sei mesi :Perfido:)

[gugoXX]

Il Mons. mi comunica che, visto che sei tu il promotore dell'iniziativa, se non posti una soluzione entro sette giorni... sambenito per sei mesi :Perfido:)

Orp... che e' sambenito?
Non mi suona leggero.

[rеpne scasb]

■

[Mesh89]

In effetti, sono curiosa: cos'e' questo sambenito?

Ti senti a rischio? :D

[Mesh89]

Ciao Mesh,

non so se dipenda da questo ma, nelle classifiche iniziali, riportavo erroneamente solo il tempo di ricerca(parlo del tuo codice). Nelle ultime ho sommato il tempo di lettura input con il tempo di ricerca:


Lettura input: 18.172 secondi
Tempo per la ricerca: 85.61 secondi

Totale -> 103.782


Invito, come ho già fatto in precedenza, anche gli altri a stilare le stesse classifiche(meglio avere risultati su più macchine e/o sistemi operativi, no?) ;)

Cmq, restando così le cose, il mio nuovo codice è più efficiente, ma per il contest andrebbe meglio l'altro? O.o

[rеpne scasb]

■

[rеpne scasb]

■

[Mesh89]

No, in quanto sono sicura che non starei male neache con il Sambenito. :sofico:

Quindi sai cos'è?

[Mesh89]

C'e' un particolare che e' necessario considerare. E' possibile che alcune strutture dati possano risiedere completamente nella cache di 1° o 2° livello di un processore soprattutto nei file meno complessi. E' per questo che apparentemente nonostante abbia ottimizzato il codice esso appare di maggiore complessita'. Sarebbe necessario avere 3 set di test con aumento della pesantezza del test di 3 per find e 3 per le estrazioni, con il primo test gia' pesante per evitare l'effetto ottimizzante della cache del processore. Sarebbe anche necessario non generare piu' alcun output (se non quello dei tempi), e non considerare neanche il tempo necessario per caricare in memoria i files. Se interessa posso preparare i 3 set standardizzati.

Sarebbe ottimo, grazie...
Cmq non sono convintissimo di questo metodo del dividere... Ad esempio, guardando l'andamento delle due soluzioni da me proposte, si potrebbe dedurre che continuando ad aumentare l'input la prima risulti infine più veloce, ma in realtà è uno scenario che non dovrebbe accadere mai

[cdimauro]

a me servirebbe un codice hash che sia uguale per ogni insieme con gli stessi elementi e che sia univoco e quindi diverso per insiemi con elementi differenti.. :fagiano:
E algoritmi di hashing del genere non mi vengono in mente.. :stordita:
Non penso sia difficile crearlo, ma vista l'univocità che imponi bisogna definire bene il dominio del problema.

Gli elementi dell'insieme in questione sono compresi soltanto fra 1 e 90? Di quanti elementi minimo dev'essere formato l'insieme? E massimo?

[Vincenzo1968]

Quindi sai cos'è?

In effetti, sono curiosa: cos'e' questo sambenito?

EDIT: trovato - Il sambenito

L'eretico o la strega che abiurava e che si rimetteva alla fede cristiana era costretto ad indossare il sambenito, un abito scapolare, consistente in due pezzi di tela che ricadevano davanti e dietro e con un apertura per la testa. Generalmente era di colore giallo con disegni che ricordavano le fiamme eterne dell'inferno, in modo da far sì che il graziato ricordasse vita natural durante la magnanimità della Chiesa e che tenesse bene a mente ciò da cui la Chiesa lo avesse salvato. Era di uso comune far camminare l'eretico tra la gente della città a piedi nudi e con un copricapo a forma di cono in testa (coroca), a monito per tutti.

-------------
...

Aggiungo questo:

Tratto da Morte dell'Inquisitore (http://www.ibs.it/code/9788845908774/sciascia-leonardo/morte-dell-inquisitore.html) di Leonardo Sciascia:


L'abito cui riferisce il povero notaro è il
cosiddetto sambenito: un sacco benedetto, una
specie di corta tunica, gialla e biffata da due strisce
a croce di sant'Andrea. Ed era l'abito dell'infamia(e
anche se oggi, nei paesi siciliani, ciascuno porta,
pirandellianamente, il proprio sambenito, cosa ben più
atroce doveva essere nel passato portare realmente
l'abito della vergogna).


Infine, chiedi a Cionci che attualmente sta scontando la pena(È una lunga storia, non sto qui a raccontartela). Fatti raccontare degli sguardi dei suoi colleghi quando si reca all'università :fiufiu:

[DanieleC88]

Cioè io non m'ero minimamente accorto di questo Contest... Vabbe', sarà per il prossimo. :D

[Mesh89]

Aggiungo questo:

Tratto da Morte dell'Inquisitore (http://www.ibs.it/code/9788845908774/sciascia-leonardo/morte-dell-inquisitore.html) di Leonardo Sciascia:



Infine, chiedi a Cionci che attualmente sta scontando la pena(È una lunga storia, non sto qui a raccontartela). Fatti raccontare degli sguardi dei suoi colleghi quando si reca all'università :fiufiu:

Immagini?

[Vincenzo1968]

Immagini?

http://www.cortescontenti.it/tortura.htm

Occhio che la pagina contiene immagini crude(anche se si tratta solo di manichini di cera). L'immagine del sambenito la trovi alla fine della pagina.

P.S.
Penso si sia capito ma lo dico lo stesso: su Cionci sto scherzando ;)

[Vincenzo1968]

Sarebbe ottimo, grazie...
Cmq non sono convintissimo di questo metodo del dividere... Ad esempio, guardando l'andamento delle due soluzioni da me proposte, si potrebbe dedurre che continuando ad aumentare l'input la prima risulti infine più veloce, ma in realtà è uno scenario che non dovrebbe accadere mai

Penso che dipenda dalla complessità. Su un algoritmo con complessità O(n^2), raddoppiando l'input il tempo di esecuzione quadruplica. Su uno con complessità O(n^3), raddoppiando l'input, il tempo di esecuzione viene moltiplicato per otto.

Non sono bravo in matematica. Attendiamo lumi dai più esperti ;)

[DanieleC88]

Penso che dipenda dalla complessità. Su un algoritmo con complessità O(n^2), raddoppiando l'input il tempo di esecuzione quadruplica. Su uno con complessità O(n^3), raddoppiando l'input, il tempo di esecuzione viene moltiplicato per otto.
Sì, l'ordine è quello. :)

[Vincenzo1968]

Sì, l'ordine è quello. :)

Grazie Daniele :)

avevo paura di avere scritto delle minchiate :Prrr:

[Mesh89]

Penso che dipenda dalla complessità. Su un algoritmo con complessità O(n^2), raddoppiando l'input il tempo di esecuzione quadruplica. Su uno con complessità O(n^3), raddoppiando l'input, il tempo di esecuzione viene moltiplicato per otto.

Non sono bravo in matematica. Attendiamo lumi dai più esperti ;)

Ho una certa esperienza in questo campo, tranquillo ;)
Non intendevo quello. Mettiamo ad esempio di fare un'ottimizzazione fissa (in questo caso è un po' dura), o anche che non è proporzionale all'output: in casi piccoli dimezzo, ma man mano che salgo arrivo a guadagnare solo un terzo. Questa ottimizzazione effettivamente aumenta il ratio (come è successo per me). Potrei addirittura vincere se progettassi un algoritmo terribilmente lento sui casi piccoli..

PS: Ho visto il sito, carino quel coso :D

[VICIUS]

Colpo di genio mentre mangiavo una fetta di saker. Ho raggruppato le varie estrazioni in gruppi di N elementi e sempre con il mascheramento controllo se i numeri sono presenti nel gruppo e solo allora eseguo la ricerca estesa tra le singole ruote del gruppetto. La dimensione ottima sembra essere 8 per il file difficile e 10 per quello semplice. Grazie a questa modifica sono passato da 115 secondi a 12 secondi netti su quello difficile con un aumento di cerca 10x.
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 |v|
c |= 1 << v
end
c
end

def compress_all(wheels)
c = 0
wheels.each do |w|
c |= w[:c]
end
c
end

def load_data(file_name)
data = Array.new
wheels = 0
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
process_data(data, 8)
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 process_data(data, wheels)
processed = []
0.step(data.size, wheels) do |i|
slice = data[i, wheels]
processed << { wheels: slice, c: compress_all(slice) }
end
processed
end

def search(data, finds)
finds.each do |f|
puts "-- #{f[:values].inspect} --"
data.each do |d|
if (d[:c] & f[:c]) == f[:c]
d[:wheels].each do |w|
if (w[:c] & f[:c]) == f[:c]
puts "#{w[:date]} #{w[:wheel]} #{w[:values].inspect}"
end
end
end
end
end
end

data = benchmark('Caricamento delle estrazioni') { load_data('LottoDataDifficile.txt') }
find = benchmark('Caricamento delle ricerche') { load_find('LottoFindDifficile.txt') }
benchmark('Ricerca dei valori') { search(data, find) }

[^TiGeRShArK^]

Non penso sia difficile crearlo, ma vista l'univocità che imponi bisogna definire bene il dominio del problema.

Gli elementi dell'insieme in questione sono compresi soltanto fra 1 e 90? Di quanti elementi minimo dev'essere formato l'insieme? E massimo?
gli elementi sono interi tra 1 e 90 e il numero di elementi va da 3 a 6 mi pare.. :p
Il problema è che non sono riuscito a trovare una funzione commutativa che dia un risultato univoco abbastanza veloce...
Per ora stavo usando un abominio del tipo produttoria * sommatoria + sommatoria + numero elementi (o qualcosa del genere.. :fagiano: )
Ma ovviamente impiego 4 secondi solo per creare la mappa del quesito difficile...
anche se c'è da dire che poi la soluzione la trovo in 12 ms :p

La cosa che mi sta spiazzando di questa funzione hash è che non posso usare coefficienti diversi per i vari elementi dell'insieme altrimenti se ne va a quel paese la commutatività nonostante l'utilizzo di operazioni commutative.. :fagiano:

[cdimauro]

gli elementi sono interi tra 1 e 90 e il numero di elementi va da 3 a 6 mi pare.. :p
Il problema è che non sono riuscito a trovare una funzione commutativa che dia un risultato univoco abbastanza veloce...
Per ora stavo usando un abominio del tipo produttoria * sommatoria + sommatoria + numero elementi (o qualcosa del genere.. :fagiano: )
Ma ovviamente impiego 4 secondi solo per creare la mappa del quesito difficile...
anche se c'è da dire che poi la soluzione la trovo in 12 ms :p

La cosa che mi sta spiazzando di questa funzione hash è che non posso usare coefficienti diversi per i vari elementi dell'insieme altrimenti se ne va a quel paese la commutatività nonostante l'utilizzo di operazioni commutative.. :fagiano:
Il problema principale che vedo è l'univocità. Dell'insieme di funzioni hash che t'interessano praticamente queste devono essere pure biettive.

Purtroppo questo significa doverti trascinare dietro tutta l'informazione rappresentata da quell'insieme di valori, e nel caso di insiemi con più di 4 elementi questo significa che un intero a 32 bit non è più sufficiente, e quindi servirà un valore a 64 bit.

Tre possibili funzioni hash che mi sono venute in mente sono le seguenti (le prime due richiedono che gli elementi dell'insieme siano ordinati; comunque ordinare fino a 6 elementi dovrebbe essere facile e poco dispendioso; al limite si possono realizzare 4 funzioni, ottimizzate una per ogni caso per gli elementi che vanno da 3 a 6).

1) Utilizzare le potenze di 90 per rappresentare gli elementi dell'insieme. Questo richiede di moltiplicare ogni elemento per una potenza di 90. Supponendo che ci siano 3 elementi x, y e z, il valore hash risulterebbe questo: hash = x + y * 90 + z * 8100. Questa funzione hash ha il vantaggio di "compattare" l'informazione (al contrario di quella successiva).

2) Per eliminare le moltiplicazioni per 90 si può passare alla potenza di 2 più vicina, che è 128, e sfruttare le ben più veloci operazioni di shift. Quindi l'esempio di cui sopra diventerebbe questo: hash = x + y << 7 + z << 14.

3) In questo caso utilizziamo un vettore di 96 bit = 12 byte per memorizzare gli elementi dell'insieme (non ci sono più limiti di massimo 6 elementi: si possono memorizzare da 0 a 96 elementi). Non è richiesto nemmeno l'ordinamento dei valori, perché è sufficiente azzerare l'array e settare i bit corrispondenti agli elementi. Il confronto ovviamente richiede la comparazione dei 12 byte del vettore (oppure 3 confronti se "raggruppiamo" i 12 byte prendendoli 32 bit alla volta).

Al momento non mi viene in mente altro.

[cionci]

purtroppo anche il tuo codice da problemi sul file grosso. Non da errori ma sembra non terminare mai e, alla fine, mi blocca tutto il sistema e mi tocca riavviare(e questo, caro Cionci, ti costerà caro: mo chiamo il Mons. e ti faccio raddoppiare la pena: due mesi, anziché uno, di sambenito :Perfido:).
Sicuramente è un problema di allocazione di memoria ;)

[^TiGeRShArK^]

Il problema principale che vedo è l'univocità. CUT
però se uso queste funzioni avrò che:
hash = x + y * 90 + z * 8100 != hash = y + x * 90 + z * 8100
che è proprio il problema con cui mi sto scontrando :fagiano:

[cionci]

1) Utilizzare le potenze di 90 per rappresentare gli elementi dell'insieme. Questo richiede di moltiplicare ogni elemento per una potenza di 90. Supponendo che ci siano 3 elementi x, y e z, il valore hash risulterebbe questo: hash = x + y * 90 + z * 8100. Questa funzione hash ha il vantaggio di "compattare" l'informazione (al contrario di quella successiva).

Io ho utilizzato questa...anche se per una questione di maggiore praticità ho utilizzato le potenze di 100. Poi le ho messe in un double. Ovviamente il double avendo una mantissa a 52 bit permetti di avere una rappresentazione certa fino a 7 estrazioni per ruota. In alternativa sulle macchine a 64 bit è possiible usare il long a 64 bit per un totale di 9 estrazioni per ruota.

[cionci]

però se uso queste funzioni avrò che:
hash = x + y * 90 + z * 8100 != hash = y + x * 90 + z * 8100
che è proprio il problema con cui mi sto scontrando :fagiano:
Ordina i numeri ;)

[^TiGeRShArK^]

Ordina i numeri ;)

...vero :fagiano:

[cdimauro]

però se uso queste funzioni avrò che:
hash = x + y * 90 + z * 8100 != hash = y + x * 90 + z * 8100
che è proprio il problema con cui mi sto scontrando :fagiano:
Ti ha risposto cionci (e l'avevo scritto all'inizio del messaggio): ordina i numeri. :)
Io ho utilizzato questa...anche se per una questione di maggiore praticità ho utilizzato le potenze di 100. Poi le ho messe in un double. Ovviamente il double avendo una mantissa a 52 bit permetti di avere una rappresentazione certa fino a 7 estrazioni per ruota. In alternativa sulle macchine a 64 bit è possiible usare il long a 64 bit per un totale di 9 estrazioni per ruota.
Sì, il double per macchine a 32 bit potrebbe essere una buona soluzione. Non c'avevo pensato. :)

In alternativa puoi usare la funzione 2), che usando le potenze di 128 permette di evitare le moltiplicazioni ricorrendo agli shift; anche in questo caso arriveresti a rappresentare 7 estrazioni per ruota usando i double.

Può darsi, comunque, che l'uso di interi a 64 bit rimanga più efficiente. Per impaccare insiemi di più di 4 elementi si può procedere divendoli in 2 gruppi (ad esempio i primi 4 e gli ultimi 2), ed eseguendo soltanto alla fine l'ultimo shift a 64 bit + la somma.

Sono idee buttate così. Tutte da verificare ovviamente.

P.S. Ci sarebbe la carta SIMD/SSE con interi a 128 bit per la soluzione 3) che avevo proposto. Anche questa da verificare. :fagiano:

[rеpne scasb]

■

[cionci]

Per evitare l'onta del sambenito posto questo che mi pare mi faccia guadagnare un bel po' ;)

PS: non ho provato con il file molto grande
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>

using namespace std;

#define DATAFILENAME "LottoDataDifficile.txt"
#define SEARCHFILENAME "LottoFindDifficile.txt"

//#define DATAFILENAME "data.txt"
//#define SEARCHFILENAME "find.txt"

void parseNumbersString(const string &numbers, bitset<90> & bits)
{
unsigned int i = 0;
int items = 0;
while(i < numbers.size())
{
if(numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if(numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
bits[item] = 1;
++items;
}
++i;
}
}

class Drawing
{
bitset<91> bits;
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)
{
parseNumbersString(numbers, bits);
}

const string & getCity()
{
return city;
}

const string & getDate()
{
return date;
}

const string & getNumbersString()
{
return numbers;
}

bool isMatching(bitset<90> &toBeTested)
{
return (bits & toBeTested) == toBeTested;
}

};


class Database
{
vector<Drawing *> drawings;
int numberCount;
public:
Database(int numberCount): numberCount(numberCount)
{
}

void insertDrawing(Drawing * drawing)
{
drawings.push_back(drawing);
}

bool findDrawings(const string &numbers, vector<Drawing *> & matchingDrawings)
{
bitset<91> bits;
parseNumbersString(numbers, bits);

for(vector<Drawing *>::iterator it = drawings.begin(); it != drawings.end(); it++)
{
Drawing * d = *it;
if(d->isMatching(bits))
matchingDrawings.push_back(d);
}

return matchingDrawings.size() > 0;
}
};


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);

vector<Drawing *> matchingDrawings;
if(!db.findDrawings(numbers, matchingDrawings))
continue;

cout << "-- " << numbers << " --" << endl;

for(vector<Drawing *>::iterator it = matchingDrawings.begin(); it != matchingDrawings.end(); it++)
{
cout << (*it)->getDate() << " " << (*it)->getCity() << " " << (*it)->getNumbersString() << endl;
}
}
return 0;
}

[cionci]

Se proprio devo...spacchetto il bitset e tolgo i vector :D

[rеpne scasb]

■

[cionci]

Conta anche le soluzioni per verifica sono 263 per i file difficili e 30041 per i file piu' difficili.
Attualmente la ricerca singola è O(n), con n uguale alle estrazioni.

[cionci]

Con il file grosso:

--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

real 2m45.929s
user 2m45.574s
sys 0m0.308s

Intel Core 2 Duo 2.166 Ghz

[ndakota]

cionci sto cercando di imparare il C++ e guardando il tuo codice ho una domanda per te. vedo che hai usato le define come 'costanti' per il nome dei file, avevo letto da qualche parte che questo si fa in C che in C++ si usa const, ha qualche eccezione questa regola? in definitiva, quando si usano le define in C++?

[Mesh89]

@Tigershark: se stai provando a generare per ogni ruota un hash per i 2^v subset, per poi fare la ricerca in tempo costante, ci ho già provato io, i tempi di lettura e rielaborazione input diventano così mastodontici che non ne vale la pena, anche se la ricerca è istantanea... Se hai in mente qualcosa di più elaborato invece ignora ciò che ho detto ;)

[DanieleC88]

cionci sto cercando di imparare il C++ e guardando il tuo codice ho una domanda per te. vedo che hai usato le define come 'costanti' per il nome dei file, avevo letto da qualche parte che questo si fa in C che in C++ si usa const, ha qualche eccezione questa regola? in definitiva, quando si usano le define in C++?
Non mi risulta ci sia una regola scritta per fare una cosa del genere. Semplicemente, con le direttive del preprocessore il testo viene inserito fisicamente nel file quando viene trovato il nome della macro. :)

[cionci]

cionci sto cercando di imparare il C++ e guardando il tuo codice ho una domanda per te. vedo che hai usato le define come 'costanti' per il nome dei file, avevo letto da qualche parte che questo si fa in C che in C++ si usa const, ha qualche eccezione questa regola? in definitiva, quando si usano le define in C++?
E' uno dei brutti vizi che mi sono portato dietro dal C :D In ogni caso trovo che le define risaltino molto meglio all'interno del codice, per questo le uso. Se devo definire una costante numerica molto spesso uso i const, ma sempre che abbiano una visibilità locale. Se hanno visibilità globale uso comunque il define sempre per il solito motivo.

[cionci]

Vediamo se riesco a dire definitivamente addio al sambenito :D

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

real 1m18.809s
user 1m17.513s
sys 0m0.436s


#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <iomanip>
#include <map>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
memset(bits, 0, sizeof(bits));
}

void set(int n)
{
bits[n / 32] |= 1 << (n % 32);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


void parseNumbersString(const string &numbers, vector<int> &v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while(i < numbers.size())
{
if(numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if(numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
v.push_back(item);
bits.set(item);
++items;
}
++i;
}
}


class Drawing
{
MyBitSet bits;
const string city;
const string date;
const string numbers;
vector<int> v;

public:
Drawing(const string &city, const string &date, const string &numbers): city(city), date(date), numbers(numbers)
{
parseNumbersString(numbers, v, bits);
}

const string & getCity()
{
return city;
}

const string & getDate()
{
return date;
}

const string & getNumbersString()
{
return numbers;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v.at(i);
}

};


class Database
{
vector<Drawing *> drawings[91];
int numberCount;
public:
Database(int numberCount): numberCount(numberCount)
{
}

void insertDrawing(Drawing * drawing)
{
for(int i = 0; i < numberCount; ++i)
{
drawings[drawing->getNumber(i)].push_back(drawing);
}
}

bool findDrawings(const string &numbers, map<Drawing *, char> & matchingDrawings)
{
MyBitSet bits;
vector<int> v;
parseNumbersString(numbers, v, bits);

for(unsigned int i = 0; i < v.size(); ++i)
{
for(vector<Drawing *>::iterator it = drawings[v.at(i)].begin(); it != drawings[v.at(i)].end(); it++)
{
Drawing * d = *it;
if(d->isMatching(bits))
matchingDrawings[d] = 1;
}
}

return matchingDrawings.size() > 0;
}
};


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);

map<Drawing *, char> matchingDrawings;
if(!db.findDrawings(numbers, matchingDrawings))
continue;

cout << "-- " << numbers << " --" << endl;

for(map<Drawing *, char>::iterator it = matchingDrawings.begin(); it != matchingDrawings.end(); it++)
{
cout << (*it).first->getDate() << " " << (*it).first->getCity() << " " << (*it).first->getNumbersString() << endl;
}
}
return 0;
}

Si basa su una osservazione molto semplice...le soluzioni stanno fra tutte le estrazioni che contengono almeno uno dei numeri da ricercare :eek: :D
Uso un map per escludere tutti i doppi, ma ora mi è venuto in mente che potrei escluderli prima i doppi :eek:

[Vincenzo1968]

Vediamo se riesco a dire definitivamente addio al sambenito :D
...
Si basa su una osservazione molto semplice...le soluzioni stanno fra tutte le estrazioni che contengono almeno uno dei numeri da ricercare :eek: :D
Uso un map per escludere tutti i doppi, ma ora mi è venuto in mente che potrei escluderli prima i doppi :eek:

Ohé Cionci,

mi dava 25 errori perché non c'era #include <map>. Il sambenito, dunque, te lo sei aggiudicato per un mese intero :Perfido:
Aggiorno la classifica tra un attimo.

x Vicius: la tua nuova versione è molto più veloce ma dà, sulla mia macchina, sempre problemi di memoria sul file grosso.

[Vincenzo1968]

Ohé Cionci,

mi dava 25 errori perché non c'era #include <map>. Il sambenito, dunque, te lo sei aggiudicato per un mese intero :Perfido:
Aggiorno la classifica tra un attimo.



Non stampa né output né tempi di esecuzione? Ti sei assicurato un altro mese di sambenito :D

[cionci]

Non stampa né output né tempi di esecuzione? Ti sei assicurato un altro mese di sambenito :D
L'output lo stampa, i tempi di esecuzione no. Io penso che sia un bene stamparli dall'inizio alla fine, altrimenti dipende troppo da come sono implementati.
Comunque un attimino che mi sonoa ccorto di un errore grossolano :eek:

[cionci]

Che testa, cercavo la soluzione in tutti i vettori relativi ai numeri da cercare, invece bastava cercarla in uno soltanto ;)
Mi sono rifatto dai...

--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

Tempo di esecuzione: 18570ms

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
memset(bits, 0, sizeof(bits));
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1FF);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


void parseNumbersString(const string &numbers, vector<int> &v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while(i < numbers.size())
{
if(numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if(numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
v.push_back(item);
bits.set(item);
++items;
}
++i;
}
}


class Drawing
{
MyBitSet bits;
string text;
vector<int> v;

public:
Drawing(const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

parseNumbersString(numbers, v, bits);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v.at(i);
}
};


class Database
{
vector<Drawing *> drawings[91];
int numberCount;
public:
Database(int numberCount): numberCount(numberCount)
{
}

void insertDrawing(Drawing * drawing)
{
for(int i = 0; i < numberCount; ++i)
{
drawings[drawing->getNumber(i)].push_back(drawing);
}
}

bool findDrawings(const string &numbers, vector<Drawing *> & matchingDrawings)
{
MyBitSet bits;
vector<int> v;
parseNumbersString(numbers, v, bits);

for(vector<Drawing *>::iterator it = drawings[v.at(0)].begin(); it != drawings[v.at(0)].end(); it++)
{
Drawing * d = *it;
if(d->isMatching(bits))
matchingDrawings.push_back(d);
}

return matchingDrawings.size() > 0;
}
};


int main()
{
clock_t start = clock();

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);

vector<Drawing *> matchingDrawings;
if(!db.findDrawings(numbers, matchingDrawings))
continue;

cout << "-- " << numbers << " --" << endl;

for(vector<Drawing *>::iterator it = matchingDrawings.begin(); it != matchingDrawings.end(); it++)
{
cout << (*it)->toString() << endl;
}
}

cout << endl << "Tempo di esecuzione: " << ((clock()-start)*1000)/CLOCKS_PER_SEC << "ms" << endl;

return 0;
}

[^TiGeRShArK^]

@Tigershark: se stai provando a generare per ogni ruota un hash per i 2^v subset, per poi fare la ricerca in tempo costante, ci ho già provato io, i tempi di lettura e rielaborazione input diventano così mastodontici che non ne vale la pena, anche se la ricerca è istantanea... Se hai in mente qualcosa di più elaborato invece ignora ciò che ho detto ;)
La mia idea originaria era di creare un subset per le varie combinazioni di 4 e di 5 estratti e inserire in un hashmap l'hash come chiave e la ruota con le estrazioni come valore...
Però nè il C# nè Java restituiscono un codice hash corretto (c# ne assegna uno univoco per ogni insieme, mentre java da semplicemente la somma degli elementi.. :mbe: ).
Calcolando l'hash a mano in effetti ci metto troppo tempo... :fagiano:

[VICIUS]

x Vicius: la tua nuova versione è molto più veloce ma dà, sulla mia macchina, sempre problemi di memoria sul file grosso.
Probabilmente è colpa dei Bignum che uso per rappresentare integer da 90bit che uniti a tutte quelle stringhe per le ruote e le date non devono di certo richiedere poca ram. Sono troppo pigro per mettermi a fare profiling e modificare il codice e ridurre l'uso di ram :p

[Vincenzo1968]

L'output lo stampa, i tempi di esecuzione no. Io penso che sia un bene stamparli dall'inizio alla fine, altrimenti dipende troppo da come sono implementati.
Comunque un attimino che mi sonoa ccorto di un errore grossolano :eek:

Anche con l'ultima versione che hai postato non visualizza nulla:
http://www.guidealgoritmi.it/images/ImgForums/OutputCionci.jpg

:confused:

[cionci]

Molto strano...non è che abbia fatto un'ottima gestione degli errori, diciamo che non è molto comunicativo :D Ci aggiungo un po' di messaggi così vediamo.

[cionci]

Ecco qua:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
memset(bits, 0, sizeof(bits));
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1F);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


void parseNumbersString(const string &numbers, vector<int> &v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while(i < numbers.size())
{
if(numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if(numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
v.push_back(item);
bits.set(item);
++items;
}
++i;
}
}


class Drawing
{
MyBitSet bits;
string text;
vector<int> v;

public:
Drawing(const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

parseNumbersString(numbers, v, bits);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v.at(i);
}
};


class Database
{
vector<Drawing *> drawings[91];
int numberCount;
public:
Database(int numberCount): numberCount(numberCount)
{
}

void insertDrawing(Drawing * drawing)
{
for(int i = 0; i < numberCount; ++i)
{
drawings[drawing->getNumber(i)].push_back(drawing);
}
}

bool findDrawings(const string &numbers, vector<Drawing *> & matchingDrawings)
{
MyBitSet bits;
vector<int> v;
parseNumbersString(numbers, v, bits);

for(vector<Drawing *>::iterator it = drawings[v.at(0)].begin(); it != drawings[v.at(0)].end(); it++)
{
Drawing * d = *it;
if(d->isMatching(bits))
matchingDrawings.push_back(d);
}

return matchingDrawings.size() > 0;
}
};


int main()
{
clock_t start = clock();

ifstream f(DATAFILENAME);

string date, city, numbers;

if(f.fail())
{
cout << "Errore apertura file dati" << endl;
return 1;
}

getline(f, numbers);
getline(f, numbers, ' ');

int numberCount;
f >> numberCount;

if(f.fail())
{
cout << "Errore parametri file dati" << endl;
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.clear();
f.open(SEARCHFILENAME);

if(f.fail())
{
cout << "Errore apertura file di ricerca" << endl;
return 1;
}

int count;
getline(f, date, ' ');
f >> count;

if(f.fail())
{
cout << "Errore parametri file di ricerca" << endl;
return 1;
}

getline(f, numbers);
for(int i = 0; i < count; ++i)
{
getline(f, numbers);

vector<Drawing *> matchingDrawings;
if(!db.findDrawings(numbers, matchingDrawings))
continue;

cout << "-- " << numbers << " --" << endl;

for(vector<Drawing *>::iterator it = matchingDrawings.begin(); it != matchingDrawings.end(); it++)
{
cout << (*it)->toString() << endl;
}
}

cout << endl << "Tempo di esecuzione: " << ((clock()-start)*1000)/CLOCKS_PER_SEC << "ms" << endl;

return 0;
}

[Vincenzo1968]

Ecco qua:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"
...


Adesso mi dice "errore apertura file di ricerca". Pensavo fosse un problema di percorsi e ho messo i due file nella stessa cartella dell'eseguibile:


/#define DATAFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoPiccolo\\LOTTO.D1"
//#define SEARCHFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoPiccolo\\LOTTO.D2"

//#define DATAFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrosso\\LOTTO.D1"
//#define SEARCHFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrosso\\LOTTO.D2"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"


ma il problema permane :cry:

[cionci]

Aspetta...correggo e riprova. Non pensavo che aprendo un altro file con lo stessa istanza di ifstream si dovessero resettare i flag...su Linux no...

Correzione fatta sopra. Riprova ;)

[||ElChE||88]

Ho provato il programma di cionci (compilato con g++)... a me funziona bene (pero ho dovuto aggiungere gli include a cstring e ctime).
Il risultato è 480ms.
Quello di repne scasb = 202ms.

[Vincenzo1968]

Aspetta...correggo e riprova. Non pensavo che aprendo un altro file con lo stessa istanza di ifstream si dovessero resettare i flag...su Linux no...

Correzione fatta sopra. Riprova ;)

OK :)

Questo è l'output sui file piccoli con redirezione su file(come ho fatto in tutti gli altri casi):


...
-- 69,42,47,33 --
14/09/2002 Lecco 42,47,48,69,40,33
-- 39,17,66,65 --
12/07/2003 LaSpezia 39,65,66,25,82,17
16/02/2002 Enna 65,7,66,44,17,39

Tempo di esecuzione: 1546ms


Vedrò di mettere una buona parola col tribunale della "Santa" Inquisizione per farti togliere qualche giorno di sambenito ;)

[cionci]

Ho provato il programma di cionci (compilato con g++)... a me funziona bene (pero ho dovuto aggiungere gli include a cstring e ctime).
Il risultato è 480ms.
Quello di repne scasb = 202ms.
Prova con questi file: http://www.usaupload.net/d/1fzh7nkp97s

[cionci]

Questo è l'output sui file piccoli con redirezione su file(come ho fatto in tutti gli altri casi):
Mi aspettavo meglio :(
Con g++ ottengo 290 ms...certo che è blelo ottimizzato g++ :eek: Negli ultimi anni ha fatto passi da gigante ;)

[||ElChE||88]

Mi aspettavo meglio :(
Con g++ ottengo 290 ms...certo che è blelo ottimizzato g++ :eek: Negli ultimi anni ha fatto passi da gigante ;)
Dici? Io trovo che Visual Studio sia più veloce.

Coi file grandi che mi hai linkato:
cionci: 26091ms
repne: 1763ms

Una bella differenza. :fagiano:

[Vincenzo1968]

Classifica aggiornata:
http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica04.jpg

La mia macchina è questa:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 3


Ohé Cionci,

il Sant'Uffizio ha deciso, per il fatto che il programma non ha bloccato il sistema sui file grossi, di toglierti un mese intero di sambenito ;)

[rеpne scasb]

■

[Vincenzo1968]

Un bel miglioramento, ma ancora non ci siamo. Link a nuovi file per il lotto http://www.usaupload.net/d/pjpovf64vku questi sono 4 volte piu' pesanti (2 volte sulle estrazioni che ora sono 2.000.000 e 2 volte sui Find che ora sono 20.000):

Mi tocca rifare tutti i test :cry:

Provvedo subito :)

[Vincenzo1968]

Un bel miglioramento, ma ancora non ci siamo. Link a nuovi file per il lotto http://www.usaupload.net/d/pjpovf64vku questi sono 4 volte piu' pesanti (2 volte sulle estrazioni che ora sono 2.000.000 e 2 volte sui Find che ora sono 20.000):

7-Zip mi dà errore quando cerco di scompattare i file:

File is broken :confused:

[rеpne scasb]

■

[Vincenzo1968]

Ho provato a scaricarlo, e non mi da problemi. Il file e' grande esattamente: 20.760.340 Byte. Decompresso con 7-Zip 4.57.

Ho provato a riscaricarlo, ma ho gli stessi problemi. Puoi utilizzare il formato rar, come i precedenti?

[VICIUS]

Ho provato a riscaricarlo, ma ho gli stessi problemi. Puoi utilizzare il formato rar, come i precedenti?
Prova con questo link: https://dl.getdropbox.com/u/35475/lotto-repne.rar

[Vincenzo1968]

Prova con questo link: https://dl.getdropbox.com/u/35475/lotto-repne.rar

Niente da fare:

http://www.guidealgoritmi.it/images/ImgForums/ErroreZip.jpg

:cry:

edit: La versione di 7-Zip che utilizzo è quella indicata da repne, la 4.57.

[Vincenzo1968]

Potete postarmeli nel formato zip?

[||ElChE||88]

Potete postarmeli nel formato zip?
http://www.usaupload.net/d/57zzs7n2dvx

[cionci]

Dici? Io trovo che Visual Studio sia più veloce
Di g++ 4.2 su Linux ?

[cionci]

Quello di repne su Linux mi crea problemi:

001 - Allocati: 46400029 Byte
002 - Allocati: 1000 Byte
003 - Allocati: 9000000 Byte
004 - Allocati: 160000000 Byte
005 - Allocati: 2850840 Byte
006 - Allocati: 4250 Byte
*** glibc detected *** ./provacpp: munmap_chunk(): invalid pointer: 0x00007f376ce4422d ***
======= Backtrace: =========
/lib/libc.so.6(cfree+0x1b6)[0x7f376cebcd46]
./provacpp[0x40133d]
/lib/libc.so.6(__libc_start_main+0xf4)[0x7f376ce631c4]
./provacpp[0x4009c9]
======= Memory map: ========
00400000-00403000 r-xp 00000000 08:11 1158886 /home/cionci/Contest7/bin/Release/provacpp
00602000-00603000 rw-p 00002000 08:11 1158886 /home/cionci/Contest7/bin/Release/provacpp
00603000-00624000 rw-p 00603000 00:00 0 [heap]
7f375fe1e000-7f376ce45000 rw-p 7f375fe1e000 00:00 0
7f376ce45000-7f376cf9d000 r-xp 00000000 08:21 1004517 /lib/libc-2.7.so
7f376cf9d000-7f376d19d000 ---p 00158000 08:21 1004517 /lib/libc-2.7.so
7f376d19d000-7f376d1a0000 r--p 00158000 08:21 1004517 /lib/libc-2.7.so
7f376d1a0000-7f376d1a2000 rw-p 0015b000 08:21 1004517 /lib/libc-2.7.so
7f376d1a2000-7f376d1a7000 rw-p 7f376d1a2000 00:00 0
7f376d1a7000-7f376d1b4000 r-xp 00000000 08:21 1002272 /lib/libgcc_s.so.1
7f376d1b4000-7f376d3b4000 ---p 0000d000 08:21 1002272 /lib/libgcc_s.so.1
7f376d3b4000-7f376d3b5000 rw-p 0000d000 08:21 1002272 /lib/libgcc_s.so.1
7f376d3b5000-7f376d435000 r-xp 00000000 08:21 1004522 /lib/libm-2.7.so
7f376d435000-7f376d634000 ---p 00080000 08:21 1004522 /lib/libm-2.7.so
7f376d634000-7f376d636000 rw-p 0007f000 08:21 1004522 /lib/libm-2.7.so
7f376d636000-7f376d725000 r-xp 00000000 08:21 1970558 /usr/lib/libstdc++.so.6.0.9
7f376d725000-7f376d925000 ---p 000ef000 08:21 1970558 /usr/lib/libstdc++.so.6.0.9
7f376d925000-7f376d92b000 r--p 000ef000 08:21 1970558 /usr/lib/libstdc++.so.6.0.9
7f376d92b000-7f376d92e000 rw-p 000f5000 08:21 1970558 /usr/lib/libstdc++.so.6.0.9
7f376d92e000-7f376d941000 rw-p 7f376d92e000 00:00 0
7f376d941000-7f376d95e000 r-xp 00000000 08:21 1002263 /lib/ld-2.7.so
7f376db3e000-7f376db41000 rw-p 7f376db3e000 00:00 0
7f376db59000-7f376db5a000 rw-p 7f376db59000 00:00 0
7f376db5b000-7f376db5e000 rw-p 7f376db5b000 00:00 0
7f376db5e000-7f376db60000 rw-p 0001d000 08:21 1002263 /lib/ld-2.7.so
7fff75b4b000-7fff75b60000 rw-p 7ffffffea000 00:00 0 [stack]
7fff75bfe000-7fff75c00000 r-xp 7fff75bfe000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted

Compresi una marea di warning:

||=== provacpp, Release ===|
/home/cionci/provacpp/main.c||In function ‘main’:|
/home/cionci/provacpp/main.c|92|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|100|warning: format ‘%d’ expects type ‘int’, but argument 3 has type ‘long unsigned int’|
/home/cionci/provacpp/main.c|104|warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘long unsigned int’|
/home/cionci/provacpp/main.c|113|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|158|warning: format ‘%d’ expects type ‘int’, but argument 3 has type ‘long unsigned int’|
/home/cionci/provacpp/main.c|162|warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘long unsigned int’|
/home/cionci/provacpp/main.c|169|warning: format ‘%d’ expects type ‘int’, but argument 3 has type ‘long unsigned int’|
/home/cionci/provacpp/main.c|173|warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘long unsigned int’|
/home/cionci/provacpp/main.c|181|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|182|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|183|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|205|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|231|warning: cast from pointer to integer of different size|
/home/cionci/provacpp/main.c|305|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|315|warning: dereferencing type-punned pointer will break strict-aliasing rules|
/home/cionci/provacpp/main.c|339|warning: cast to pointer from integer of different size|
/home/cionci/provacpp/main.c|380|warning: cast to pointer from integer of different size|
/home/cionci/provacpp/main.c|381|warning: cast from pointer to integer of different size|
||=== Build finished: 0 errors, 18 warnings ===|

[rеpne scasb]

■

[cionci]

Ora va in segfault:

001 - Allocati: 46400029 Byte
002 - Allocati: 1000 Byte
003 - Allocati: 9000000 Byte
004 - Allocati: 160000000 Byte
005 - Allocati: 2850840 Byte
006 - Allocati: 4250 Byte
007 - Deallocati: 46400029 Byte
008 - Allocati: 140422 Byte

Segmentation fault

Dal sorgente devo togliere mem.h e sostituire CLK_TCK con CLOCKS_PER_SEC.

[cionci]

Il segmentation fault lo genera in questo pezzo di codice:

if(e_arry[m])
{
l_arry=(int *)e_arry[m];
do
{
element=*l_arry;

for(k=element*(DATA_LEN+valori),l=E_ZN;l<=j;l++)

[rеpne scasb]

■

[cionci]

Stai su Linux a 64-bit?
Sì, gli int sono a 32 bit, i long a 64.

[rеpne scasb]

■

[cionci]

Sì:

gcc -m32 -O2 main.c -o repne

$ ./repne
[...cut...]
-- 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

*** Soluzioni trovate: 30041

*** Tempo per caricamento dati e creazione strutture: 1.220 secondi

*** Tempo per ricerca della soluzione difficile: 0.610 secondi

*** Tempo totale per l'intera elaborazione: 1.830 secondi

[cionci]

Però mi sembra o non stai contando l'output dei risultati ?

$ time ./repne
*** Tempo totale per l'intera elaborazione: 1.830 secondi

real 0m7.137s
user 0m1.696s
sys 0m0.224s

[rеpne scasb]

■

[rеpne scasb]

■

[cionci]

Allora in ogni caso qualcosa non torna. Il tempo di esecuzione si vede anche ad occhio che è superiore a quello che dai in output.

Questo è il mio:

$ time ./Contest7

--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

Tempo di esecuzione: 18200ms

real 0m18.605s
user 0m17.877s
sys 0m0.348s

L'istruzione time misura proprio il tempo di esecuzione ;)

[rеpne scasb]

■

[cionci]

Ci sta che la differenza si perda nei meandri del buffering dell'output ???

[rеpne scasb]

■

[cionci]

Chiarisci? Secondo te starei barando in qualche modo?
No, secondo me c'è qualche fattore che mi perdo, probabilmente nel buffering dell'output della console. Fatto sta che la misurazione del tempo reale di esecuzione (non quello misurato all'interno del programma) da quando si lancia il programma a quando il controllo ritorna all'utente è diverso da quello misurato nel programma. Imho l'unica spiegazione possibile è che l'output venga tutto bufferizzato e non mostrato in uscita istantaneamente (compreso il calcolo del tempo). Poi viene visualizzato tutto insieme al termine del programma quando tutto quello che è nel buffer viene visualizzato.
Non stai barando te, ma sta barando il SO ;)

In pratica il tempo di output viene tutto spostato in fondo ad esecuzione del programma terminata.

[caurusapulus]

Figata il contest :eek:

[cionci]

Non stai barando te, ma sta barando il SO ;)
Provo a spiegarmi ancora meglio: nel computo del tempo che calcoli in fondo, anche se sembra, non è compreso l'output (syscall e passaggio in kernel mode), ma solo il trasferimento del testo nel buffer.
Togliendo anche il trasferimento del testo nel buffer (commentando le printf) il tuo programma infatti continua a misurare tempi nello stesso ordine (chiaramente un piccola variazione è dovuta a questo), ma come vedi il risultato riportato da time è questa volta coerente:

$ time ./repne
001 - Allocati: 46400029 Byte
002 - Allocati: 1000 Byte
003 - Allocati: 9000000 Byte
004 - Allocati: 160000000 Byte
005 - Allocati: 2850840 Byte
006 - Allocati: 4250 Byte
007 - Deallocati: 46400029 Byte
008 - Allocati: 140422 Byte


*** Soluzioni trovate: 30041

*** Tempo per caricamento dati e creazione strutture: 1.210 secondi

*** Tempo per ricerca della soluzione difficile: 0.280 secondi

*** Tempo totale per l'intera elaborazione: 1.490 secondi

real 0m1.566s
user 0m1.412s
sys 0m0.152s

In sostanza il tempo di esecuzione della tua applicazione, almeno sul mio sistema, è 7 secondi e non 1.8 se si va a prendere il tempo utente reale. Altrimenti per confrontarlo con altri linguaggi bisognerebbe andare prendere il tempo di esecuzione senza considerare l'output.
Questo per ricollegarmi al ragionamento fatto qualche pagina fa su come il conteggio del tempo di esecuzione all'interno dell'applicazione possa risultare falsato dal SO, dal linguaggio utilizzato e del metodo di esecuzione.

[rеpne scasb]

■

[rеpne scasb]

■

[cionci]

Per fare misurazioni corrette ci vorrebbe quindi (e non basta la redirezione del testo su file perché anche qui agisce il buffering) una misurazione dall'esterno del programma che si esegue, come appunto la time di Linux.

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[Mesh89]

Dovrebbe essere un po' più veloce

#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <ctime>

using namespace std;

#define TOT_RUOTE 2000000


struct Ruota {
bitset<96> bitmask;
int data, luogo;
int* numeri;
};
vector<char*> luoghi, date;
vector<Ruota> ruote;
vector<int> indexed[91];
int lens[91];


int main() {
FILE* fin = fopen("LOTTO.D2", "r");
FILE* rin = fopen("LOTTO.D1", "r");
FILE* out = fopen("out.out", "w");
int r, v, f, daCercare[9], index=0;
char* s;
clock_t start = clock();

//Lettura luoghi
fscanf(rin, "%s %d\n", s, &r);
fscanf(rin, "%s %d\n", s, &v);
fscanf(fin, "%s %d\n", s, &f);

for (int i = 0; i < r; i++) {
s = new char[20];
fscanf(rin, "%s %*s %*s", s);
luoghi.push_back(s);
}

fclose(rin);
rin = fopen("LOTTO.D1", "r");
fscanf(rin, "%s %d\n", s, &r);
fscanf(rin, "%s %d\n", s, &v);

//Lettura ruote
ruote.reserve(TOT_RUOTE);
while (!feof(rin)) {
Ruota ruota; int n;
ruota.numeri = new int[v];

if (index%r == 0) {
s = new char[11];
fscanf(rin, "%s", s);
date.push_back(s);
}
else
fscanf(rin, "%*s");
fscanf(rin, "%*s");
ruota.data = index/r;
ruota.luogo = index%r;

for (int i = 0; i < v-1; i++) {
fscanf(rin, "%d,", &n);
ruota.bitmask[n] = 1;
ruota.numeri[i] = n;

indexed[n].push_back(index);
} fscanf(rin, "%d\n", &n);
ruota.bitmask[n] = 1;
ruota.numeri[v-1] = 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++) { //long long int ricerche = 0;
int k = 1, luckyNumber;
char c;

//Lettura find
fscanf(fin, "%d", daCercare);
luckyNumber = daCercare[0];
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;
int len = lens[luckyNumber];
for (int j = 0; j < lens[luckyNumber]; j++) {
//ricerche++;
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 (OK) {
if (first) {
fprintf(out, "-- ");
for (int h = 0; h < k-1; h++)
fprintf(out, "%d,", daCercare[h]);
fprintf(out, "%d --\n", daCercare[k-1]);
}
first = false;
fprintf(out, "%s %s ", date[ruote[n].data], luoghi[ruote[n].luogo]);
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 << ricerche << endl;
}

cout << "Tempo per la ricerca: " << (clock()-start)/1000.0 << " secondi" << endl;
}

Ora faccio un po' di test...

[rеpne scasb]

■

[Mesh89]

Ho fatto i test su repne, cionci e me, solo sui file postati da repne.

Macchina: AMD Duron 1600mhz, 1,5gb di ram, Linux 32bit
Tempi presi con la time (real) di sistema (non fidandosi dunque di ciò che dicono i programmi)

File "piccolo":
repne: 0m5.493s
cionci: 0m51.189s
mesh: 0m52.829s

File grande:
repne: 0m10.687s
mesh: 1m44.317s (:P)
cionci: 1m44.435s

[Tommo]

Ho fatto i test su repne, cionci e me, solo sui file postati da repne.

Macchina: AMD Duron 1600mhz, 1,5gb di ram, Linux 32bit
Tempi presi con la time (real) di sistema (non fidandosi dunque di ciò che dicono i programmi)

File "piccolo":
repne: 0m5.493s
cionci: 0m51.189s
mesh: 0m52.829s

File grande:
repne: 0m10.687s
mesh: 1m44.317s (:P)
cionci: 1m44.435s

Che mostruosità repne :D
Avevo iniziato a scrivere qualcosa poi ho visto i suoi risultati... e ho smesso :asd:
Non riesco nemmeno a capire come fa ad andare così, devo studiarmi bene il codice.

[Mesh89]

Che mostruosità repne :D
Avevo iniziato a scrivere qualcosa poi ho visto i suoi risultati... e ho smesso :asd:
Non riesco nemmeno a capire come fa ad andare così, devo studiarmi bene il codice.

Siamo in due :D
Cmq a quanto ho capito è molto matematico, e io ho appena iniziato il primo anno di università, avendo alle spalle una matematica da ITIS, quindi dubito potrei capire...

PS: dimenticavo, alle olimpiadi si compilava con -static e -O2, ho fatto lo stesso anch'io

[cionci]

Mi sono accorta che la spiegazioni forse e' troppo complessa. Allora... numerini come alle elementari:
Un po' permalosetta ??? Siamo qui per parlare non sono certo qui per farmi dare del deficiente.

Sto dicendo un'altra cosa: se l'output del C (che sia su file che su video) è bufferizzato fino alla fine dell'esecuzione, mentre quello del linguaggio X è bufferizzato a livello di linea, prendendo il tempo dall'inizio alla fine dell'esecuzione tramite codice con il linguaggio C misurerai comunque un intervallo di tempo fra istanti "diversi" rispetto a quanto ottenuto con il linguaggio X. "Diverso" nel senso che non tiene conto dell'output, mentre nel linguaggio X se ne dovrà tenere conto comunque. Quindi mi pare più corretto A PRIORI, senza tenere conto del caso specifico, ma facendo un discorso più generale, andare ad utilizzare un programma esterno che misura il tempo di esecuzione in modo da tenere conto anche dello svuotamento del buffer di output.
A me sinceramente non interessa niente se il tuo programma è più veloce del mio, non mi sono nemmeno messo ad ottimizzare togliendo i vector, ne sto facendo semplicemente una disquisizione TECNICA, mentre tu mi sembra sia passata sul livello PERSONALE.

[Vincenzo1968]

Per fare misurazioni corrette, redirigi l'output su file che e' alcuni ordini di grandezza piu' veloce che l'output a video. In sostanza se

t1 = tempo effettivo di esecuzione del software
t2a = tempo per generare l'output a video
t2b= tempo per generare l'output su file.

ka = t2a/t1 (quota del tempo dipendente dall'output
kb = t2b/t1 (quota del tempo dipendente dall'output

poiche' t2b<<t2a segue che kb<<ka, da cui si evince che e' sufficiente minimizzare il tempo dell'output per renderlo trascurabile rispetto a t1.

Lo stesso risultatolo hai se prendi i tempi con linux e redirigi l'output su file.

I tempi li ho presi, in tutti e tre i casi(Cionci, Mesh e Repne), con redirezione dell'input su file.
Esempio:

NomeEseguibile > output.txt

Ho problemi con gli ultimi file che hai indicato(anche nel formato zip messo a disposizione da ElChE, che ringrazio).
Vorrei crearmeli a mano con i sorgenti che hai postato. Come debbo impostare le costanti all'inizio dei file?

[Tommo]

Siamo in due :D
Cmq a quanto ho capito è molto matematico, e io ho appena iniziato il primo anno di università, avendo alle spalle una matematica da ITIS, quindi dubito potrei capire...

PS: dimenticavo, alle olimpiadi si compilava con -static e -O2, ho fatto lo stesso anch'io
Idem anche io... solo che vengo da una fumosa matematica da sperimentale :asd:
Cmq finora ho visto che usa un accesso pesantemente casuale basandosi sulla data: estrae a caso g m a. Forse riesce ad escludere gran parte del file usando una specie di sorting alfabetico ma per le date.

dell'ottimo OT:
Avevo già notato che il cout a video è una delle istruzioni che più rallentano l'esecuzione del programma... per quale motivo?
Sincronizzazione programma - Windows - driver GPU?

ulteriore OT:
repne, ma tu dove hai studiato, così per curiosità? :D

[cionci]

I tempi li ho presi, in tutti e tre i casi(Cionci, Mesh e Repne), con redirezione dell'input su file.
Come dicevo prendendo i tempi con redirezione dell'output su file non si prendono comunque i tempi corretti. Bisogna prenderli con un programma esterno. Non che questo certo cambi gli ordini di grandezza dei risultati.

[cionci]

Avevo già notato che il cout a video è una delle istruzioni che più rallentano l'esecuzione del programma... per quale motivo?
Ogni volta che si usa endl viene fatto il flush del buffer di output.

[Vincenzo1968]

Come dicevo prendendo i tempi con redirezione dell'output su file non si prendono comunque i tempi corretti. Bisogna prenderli con un programma esterno. Non che questo certo cambi gli ordini di grandezza dei risultati.

E se prendessimo i tempi della sola ricerca, senza contare il caricamento dei dati e l'output?(Altrimenti, dove lo trovo un programma per windows?) :confused:

edit: prima ho scritto redirezione dell'input. Invece è: redirezione dell'output. ;)

[cionci]

Altrimenti, dove lo trovo un programma per windows? :confused:
Sei un programmatore ? :D
E' facile, su Visual C++: prendi il tempo con clock prima di eseguire il file, poi usi la spawn (una delle varie incarnazioni) e dopo riprendi il clock e stampi a video il risultato.

[cionci]

Ecco qui: http://msdn.microsoft.com/it-it/library/20y988d2(VS.80).aspx
Con l'opzione _P_WAIT

[Vincenzo1968]

Sei un programmatore ? :D
E' facile, su Visual C++: prendi il tempo con clock prima di eseguire il file, poi usi la spawn (una delle varie incarnazioni) e dopo riprendi il clock e stampi a video il risultato.

Sono un programmatore scarsissimo ;)
Che è sto spawn?

edit: come non detto(per spawn, dico). Mentre scrivevo questo post non c'era ancora il tuo con il link. Grazie ;)

[||ElChE||88]

Di g++ 4.2 su Linux ?
No... di g++ 4.2 su Windows.

[fek]

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

#define N_CLK 10
#define N_MAGIC 3
#define MAX_N_DIM 10
#define MAX_N 90
#define E_ZN 3
#define DATA_LEN 3
#define Y_ZERO 1900
#define INPUT_FILE_NAME_D1 "LOTTO.D1"
#define INPUT_FILE_NAME_D2 "LOTTO.D2"

#if E_ZN==2
#define TABLE_C table_disp[15][E_ZN]={{0,1},{0,2},{0,3},{0,4},{0,5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}}
#elif E_ZN==3
#define TABLE_C table_disp[20][E_ZN]={{0,1,2},{0,1,3},{0,1,4},{0,1,5},{0,2,3},{0,2,4},{0,2,5},{0,3,4},{0,3,5},{0,4,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}}
#elif E_ZN==4
#define TABLE_C table_disp[15][E_ZN]={{0,1,2,3},{0,1,2,4},{0,1,2,5},{0,1,3,4},{0,1,3,5},{0,1,4,5},{0,2,3,4},{0,2,3,5},{0,2,4,5},{0,3,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}
#endif

int Get_Number(char *,long *);

int main()

{
clock_t clk[N_CLK];
char *buffer_file_d1,*buffer_file_d2,*buffer_file_tmp,*end_buffer_file,*st_arry,*st_arry_tmp,**rt_name,*magic[N_MAGIC]={"Ruote","Valori","Find"},f_elem[MAX_N];
FILE *input_file_handle_d1,*input_file_handle_d2;
int i,j,k,l,sol=0,m,n,mem_name=0,e_find,find,element,sp,rt_name_size,disp,disp_t,n_estr=0,input_file_size_d1,input_file_size_d2,ruote,valori,*e_arry,*l_arry;

int TABLE_C;

if((input_file_handle_d1=fopen(INPUT_FILE_NAME_D1,"rb"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D1 "\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 001\n");
return 1;
}

if((input_file_size_d1=ftell(input_file_handle_d1))==-1)
{
fprintf(stderr,"Errore interno: 002\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 003\n");
return 1;
}

if((buffer_file_d1=malloc(input_file_size_d1))==NULL)
{
fprintf(stderr,"Memoria insufficiente (001 : %d Byte)\n",input_file_size_d1);
return 1;
}
else
printf("001 - Allocati: %d Byte\n",input_file_size_d1);

if(fread(buffer_file_d1,input_file_size_d1,1,input_file_handle_d1)==0)
{
fprintf(stderr,"Errore interno: 004\n");
return 1;
}

if(fclose(input_file_handle_d1))
{
fprintf(stderr,"Errore interno: 005\n");
return 1;
}

clk[0]=clock();

end_buffer_file=buffer_file_d1+input_file_size_d1;

if(memcmp(magic[0],buffer_file_d1,strlen(magic[0])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (001)\n");
return 1;
}

buffer_file_d1+=strlen(magic[0]);
if((ruote=Get_Number(buffer_file_d1,(long *)&buffer_file_d1))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (002)\n");
return 1;
}

if((rt_name=malloc(ruote*sizeof(int)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (002 : %d Byte)\n",ruote*sizeof(int));
return 1;
}
else
printf("002 - Allocati: %d Byte\n",ruote*sizeof(int));

if(memcmp(magic[1],buffer_file_d1,strlen(magic[1])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (003)\n");
return 1;
}

buffer_file_d1+=strlen(magic[1]);
if((valori=Get_Number(buffer_file_d1,(long *)&buffer_file_d1))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (004)\n");
return 1;
}

buffer_file_tmp=buffer_file_d1;

while(buffer_file_tmp<end_buffer_file)
{
if((*buffer_file_tmp==0x0A)||(*buffer_file_tmp==0x0D))
{
n_estr++;
buffer_file_tmp++;
if((*buffer_file_tmp==0x0A)||(*buffer_file_tmp==0x0D))
buffer_file_tmp++;
}
else
buffer_file_tmp++;
}

if(n_estr%ruote)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (005)\n");
return 1;
}
else
{
if((st_arry=malloc(n_estr*(DATA_LEN+valori)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (003 : %d Byte)\n",n_estr*(DATA_LEN+valori));
return 1;
}
else
printf("003 - Allocati: %d Byte\n",n_estr*(DATA_LEN+valori));
n_estr/=ruote;
}

for(disp_t=valori,i=valori-1;i>(valori-E_ZN);i--)
disp_t*=i;
for(i=2;i<=E_ZN;i++)
disp_t/=i;

if((l_arry=malloc(disp_t*n_estr*ruote*(sizeof(int)<<1)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (004 : %d Byte)\n",disp_t*n_estr*ruote*(sizeof(int)<<1));
return 1;
}
else
printf("004 - Allocati: %d Byte\n",disp_t*n_estr*ruote*(sizeof(int)<<1));

for(j=1,disp=i=0;i<E_ZN;i++,j*=MAX_N)
disp+=(MAX_N-i-1)*j;

if((e_arry=malloc(++disp*sizeof(int)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (005 : %d Byte)\n",disp*sizeof(int));
return 1;
}
else
printf("005 - Allocati: %d Byte\n",disp*sizeof(int));

memset(e_arry,0,disp*sizeof(int));

for(st_arry_tmp=st_arry,element=sp=i=0;i<n_estr;i++)
{
for(j=0;j<ruote;j++)
{
st_arry[0]=Get_Number(buffer_file_d1,(long *)&buffer_file_d1);
st_arry[1]=Get_Number(buffer_file_d1,(long *)&buffer_file_d1);
st_arry[2]=Get_Number(buffer_file_d1,(long *)&buffer_file_d1)-Y_ZERO;

buffer_file_d1++;
if(sp==0)
{
buffer_file_tmp=buffer_file_d1;
while (*buffer_file_tmp++!=' ');
rt_name_size=buffer_file_tmp-buffer_file_d1;
*(buffer_file_tmp-1)=0;
if((rt_name[j]=malloc(rt_name_size))==NULL)
{
fprintf(stderr,"Memoria insufficiente (006 : %d Byte)\n",rt_name_size);
return 1;
}
mem_name+=rt_name_size;
memcpy(rt_name[j],buffer_file_d1,rt_name_size);
buffer_file_d1+=rt_name_size;
}
else
while (*buffer_file_d1++!=' ');

for(k=0;k<valori;k++)
st_arry[DATA_LEN+k]=Get_Number(buffer_file_d1,(long *)&buffer_file_d1);

do
{
l=0;
for(k=0;k<(valori-1);k++)
{
if(st_arry[DATA_LEN+k]>st_arry[DATA_LEN+k+1])
{
l=st_arry[DATA_LEN+k];
st_arry[DATA_LEN+k]=st_arry[DATA_LEN+k+1];
st_arry[DATA_LEN+k+1]=l;
l=1;
}
}
} while (l);

for(k=0;k<disp_t;k++)
{
for(m=st_arry[DATA_LEN+table_disp[k][0]]-1,l=1;l<E_ZN;l++)
m=m*MAX_N+st_arry[DATA_LEN+table_disp[k][l]]-1;

if(e_arry[m])
l_arry[1]=e_arry[m];
else
l_arry[1]=-1;
e_arry[m]=(int)l_arry;
*l_arry=element;
l_arry+=2;
}
element++;

st_arry+=DATA_LEN+valori;
}
if(sp==0)
{
printf("006 - Allocati: %d Byte\n",mem_name);
sp=1;
}
}

st_arry=st_arry_tmp;

buffer_file_d1=end_buffer_file-input_file_size_d1;

free(buffer_file_d1);
printf("007 - Deallocati: %d Byte\n",input_file_size_d1);

clk[1]=clock();

if((input_file_handle_d2=fopen(INPUT_FILE_NAME_D2,"rb"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D2 "\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 006\n");
return 1;
}

if((input_file_size_d2=ftell(input_file_handle_d2))==-1)
{
fprintf(stderr,"Errore interno: 007\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 008\n");
return 1;
}

if((buffer_file_d2=malloc(input_file_size_d2))==NULL)
{
fprintf(stderr,"Memoria insufficiente (007 : %d Byte)\n",input_file_size_d2);
return 1;
}
else
printf("008 - Allocati: %d Byte\n\n",input_file_size_d2);

if(fread(buffer_file_d2,input_file_size_d2,1,input_file_handle_d2)==0)
{
fprintf(stderr,"Errore interno: 009\n");
return 1;
}

if(fclose(input_file_handle_d2))
{
fprintf(stderr,"Errore interno: 010\n");
return 1;
}

if(memcmp(magic[2],buffer_file_d2,strlen(magic[2])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (001)\n");
return 1;
}

buffer_file_d1+=strlen(magic[0]);

if((find=Get_Number(buffer_file_d2,(long *)&buffer_file_d2))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (002)\n");
return 1;
}

for(i=0;i<find;i++)
{
for(j=0;j<MAX_N;j++)
{
f_elem[j]=Get_Number(buffer_file_d2,(long *)&buffer_file_d2);
if(*buffer_file_d2!=',')
break;
}

do
{
l=0;
for(k=0;k<j;k++)
{
if(f_elem[k]>f_elem[k+1])
{
l=f_elem[k];
f_elem[k]=f_elem[k+1];
f_elem[k+1]=l;
l=1;
}
}
} while (l);

for(e_find=0,m=f_elem[0]-1,l=1;l<E_ZN;l++)
m=m*MAX_N+f_elem[l]-1;
if(e_arry[m])
{
l_arry=(int *)e_arry[m];
do
{
element=*l_arry;

for(k=element*(DATA_LEN+valori),l=E_ZN;l<=j;l++)
{
for(n=m=0;m<valori;m++)
{
if(st_arry[DATA_LEN+m+k]==f_elem[l])
n=1;
}
if(n==0)
break;
}

if(l==(j+1))
{
if(e_find==0)
{
printf("-- ");
for(k=0;k<=j;k++)
{
printf("%d",f_elem[k]);
if(k!=j)
printf(",");
}
printf(" --\n");
e_find=1;
}
printf("%.2d/%.2d/%.4d %s ",st_arry[element*(DATA_LEN+valori)],st_arry[element*(DATA_LEN+valori)+1],st_arry[element*(DATA_LEN+valori)+2]+Y_ZERO,rt_name[element%ruote]);
for(k=0;k<valori;k++)
{
printf("%d",st_arry[element*(DATA_LEN+valori)+DATA_LEN+k]);
if(k!=(valori-1))
printf(",");
}
printf("\n");
sol++;
}

l_arry=(int *)*(l_arry+1);
} while ((int)l_arry!=-1);
}
}

clk[2]=clock();

printf("\n*** Soluzioni trovate: %d\n",sol);
printf("\n*** Tempo per caricamento dati e creazione strutture: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);
printf("\n*** Tempo per ricerca della soluzione difficile: %7.3f secondi\n",(double)(clk[2]-clk[1])/CLK_TCK);
printf("\n*** Tempo totale per l'intera elaborazione: %7.3f secondi\n",(double)(clk[2]-clk[0])/CLK_TCK);

return 0;
}

int Get_Number(buffer,offset)
char *buffer;
long *offset;

{
int rnum=-1,i=0;
char numero[MAX_N_DIM];

for(;;buffer++)
{
if((*buffer==0x0A)||(*buffer==0x0D))
{
buffer++;
break;
}
if((*buffer>='0')&&(*buffer<='9'))
{
do
{
numero[i++]=*buffer++;
} while ((*buffer>='0')&&(*buffer<='9'));
numero[i]=0;
rnum=atoi(numero);
if((*buffer==0x0A)||(*buffer==0x0D))
buffer++;
break;
}
}
if((*buffer==0x0A)||(*buffer==0x0D))
buffer++;

*offset=(long)buffer;
return(rnum);
}



Per chi si avvicina da poco alla programmazione e per chi programma gia' da tanto.
Leggete attentatemente questo codice. Poi rileggetelo. Poi chiudete il forum. Tornate fra qualche giorno e rileggetevelo. Poi stampatene una copia e appendetela al muro di fronte al letto: deve essere la prima cosa che guardate la mattina.

Perche' cosi' NON si programma.

[Tommo]

Per chi si avvicina da poco alla programmazione e per chi programma gia' da tanto.
Leggete attentatemente questo codice. Poi rileggetelo. Poi chiudete il forum. Tornate fra qualche giorno e rileggetevelo. Poi stampatene una copia e appendetela al muro di fronte al letto: deve essere la prima cosa che guardate la mattina.

Perche' cosi' NON si programma.

E' chiaro che è brutto.
Ma sono convinto che se tu sai fare na roba così sai anche fare una roba elegante.
Mentre se sai fare una roba elegante puoi benissimo non capire un cavolo di quel codice :asd:

PS: è un contest di velocità, e quindi non dovrebbe contare granchè :asd:

[Vincenzo1968]

Per chi si avvicina da poco alla programmazione e per chi programma gia' da tanto.
Leggete attentatemente questo codice. Poi rileggetelo. Poi chiudete il forum. Tornate fra qualche giorno e rileggetevelo. Poi stampatene una copia e appendetela al muro di fronte al letto: deve essere la prima cosa che guardate la mattina.

Perche' cosi' NON si programma.

E si potrebbe, di grazia, sapere il perché?

[Mesh89]

E' chiaro che è brutto.
Ma sono convinto che se tu sai fare na roba così sai anche fare una roba elegante.
Mentre se sai fare una roba elegante puoi benissimo non capire un cavolo di quel codice :asd:

PS: è un contest di velocità, e quindi non dovrebbe contare granchè :asd:

Quoto, anche il mio codice è abbastanza una porcata, ma è così che si programma nei contest :)

[Vincenzo1968]

Quoto, anche il mio codice è abbastanza una porcata, ma è così che si programma nei contest :)

Mesh ciao,

purtroppo ho problemi con la tua nuova versione. Il programma va in crash.
L'ho modificato leggermente(ho messo i nomi dei percorsi dei file in due variabili):


#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <ctime>

using namespace std;

#define TOT_RUOTE 2000000


struct Ruota {
bitset<96> bitmask;
int data, luogo;
int* numeri;
};
vector<char*> luoghi, date;
vector<Ruota> ruote;
vector<int> indexed[91];
int lens[91];


int main()
{
char *szFileD1 = "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoPiccolo\\LOTTO.D1";
char *szFileD2 = "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoPiccolo\\LOTTO.D2";

//char *szFileD1 = "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrosso\\LOTTO.D1";
//char *szFileD2 = "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrosso\\LOTTO.D2";

FILE* fin = fopen(szFileD2, "r");
FILE* rin = fopen(szFileD1, "r");

FILE* out = fopen("out.out", "w");
int r, v, f, daCercare[9], index=0;
char* s;
clock_t start = clock();

//Lettura luoghi
fscanf(rin, "%s %d\n", s, &r);
fscanf(rin, "%s %d\n", s, &v);
fscanf(fin, "%s %d\n", s, &f);

for (int i = 0; i < r; i++) {
s = new char[20];
fscanf(rin, "%s %*s %*s", s);
luoghi.push_back(s);
}

fclose(rin);
rin = fopen(szFileD1, "r");
fscanf(rin, "%s %d\n", s, &r);
fscanf(rin, "%s %d\n", s, &v);

//Lettura ruote
ruote.reserve(TOT_RUOTE);
while (!feof(rin)) {
Ruota ruota; int n;
ruota.numeri = new int[v];

if (index%r == 0) {
s = new char[11];
fscanf(rin, "%s", s);
date.push_back(s);
}
else
fscanf(rin, "%*s");
fscanf(rin, "%*s");
ruota.data = index/r;
ruota.luogo = index%r;

for (int i = 0; i < v-1; i++) {
fscanf(rin, "%d,", &n);
ruota.bitmask[n] = 1;
ruota.numeri[i] = n;

indexed[n].push_back(index);
} fscanf(rin, "%d\n", &n);
ruota.bitmask[n] = 1;
ruota.numeri[v-1] = 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++) { //long long int ricerche = 0;
int k = 1, luckyNumber;
char c;

//Lettura find
fscanf(fin, "%d", daCercare);
luckyNumber = daCercare[0];
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;
int len = lens[luckyNumber];
for (int j = 0; j < lens[luckyNumber]; j++) {
//ricerche++;
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 (OK) {
if (first) {
fprintf(out, "-- ");
for (int h = 0; h < k-1; h++)
fprintf(out, "%d,", daCercare[h]);
fprintf(out, "%d --\n", daCercare[k-1]);
}
first = false;
fprintf(out, "%s %s ", date[ruote[n].data], luoghi[ruote[n].luogo]);
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 << ricerche << endl;
}

cout << "Tempo per la ricerca: " << (clock()-start)/1000.0 << " secondi" << endl;
}


Ho visto che definisci la costante TOT_RUOTE impostandola a 2000000. Ma così non posso fare il test sui file più piccoli.

[VICIUS]

Se volete continuare a parlare di come si dovrebbe programmare è meglio se aprite una discussione a parte perché potrebbe andare avanti per pagine e pagine. Qui continuiamo a parlare solamente del contest.

[Vincenzo1968]

Se volete continuare a parlare di come si dovrebbe programmare è meglio se aprite una discussione a parte perché potrebbe andare avanti per pagine e pagine. Qui continuiamo a parlare solamente del contest.

Quoto. Quoto, straquoto e stracataquoto.

[cionci]

Se volete continuare a parlare di come si dovrebbe programmare è meglio se aprite una discussione a parte perché potrebbe andare avanti per pagine e pagine. Qui continuiamo a parlare solamente del contest.
Concordo.

Ecco qua Vincenzo:

#include <iostream>
#include <process.h>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
if(argc == 1)
return 1;

clock_t start = clock();
char **argv2 = &argv[1];
spawnvp(_P_WAIT, argv2[0], argv2);
cerr << endl << "User time: " << ((double)(clock() - start)*1000)/CLOCKS_PER_SEC << "ms" << endl;
return 0;
}


Ah...l'uso è, supponendo che si chiami simpletime l'eseguibile creato dal codice sopra:

simpletime nomeeseguibile eventuali parametri

Ovviamente puoi anche redirezionare l'output su file.

[cionci]

Quoto, anche il mio codice è abbastanza una porcata, ma è così che si programma nei contest :)
Attenzione che questo non credo sia corretto, a meno che non mi sia perso qualcosa:

cout << "Tempo per la ricerca: " << (clock()-start)/1000.0 << " secondi" << endl;

[Vincenzo1968]

Concordo.

Ecco qua Vincenzo:

#include <iostream>
#include <process.h>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
if(argc == 1)
return 1;

clock_t start = clock();
char **argv2 = &argv[1];
spawnvp(_P_WAIT, argv2[0], argv2);
cerr << endl << "User time: " << ((double)(clock() - start)*1000)/CLOCKS_PER_SEC << "ms" << endl;
return 0;
}


Grazie mille ;)

[Vincenzo1968]

Classifica aggiornata col metodo Cionci:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica05.jpg

Ho escluso, per il momento, Mesh, per i problemi che ho segnalato prima.

edit: dimenticavo, la mia macchina:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 3

[Vincenzo1968]

Figata il contest :eek:

I links ai precedenti:

http://www.hwupgrade.it/forum/showthread.php?t=1784948&highlight=%5Bvari%5D+Context

http://www.hwupgrade.it/forum/showthread.php?t=1785752&highlight=%5Bvari%5D+Contest

http://www.hwupgrade.it/forum/showthread.php?t=1787500&highlight=%5Bvari%5D+Contest

http://www.hwupgrade.it/forum/showthread.php?t=1791293&highlight=%5Bvari%5D+Contest

http://www.hwupgrade.it/forum/showthread.php?t=1799059&highlight=%5Bvari%5D+Contest

Ciao ;)

[cionci]

Vincenzo prova l'ultimo:
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
#include <ctime>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
memset(bits, 0, sizeof(bits));
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1F);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


void parseNumbersString(const string &numbers, vector<int> &v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while(i < numbers.size())
{
if(numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if(numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
v.push_back(item);
bits.set(item);
++items;
}
++i;
}
}


class Drawing
{
MyBitSet bits;
string text;
vector<int> v;

public:
Drawing(const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

parseNumbersString(numbers, v, bits);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v.at(i);
}
};


class Database
{
vector<Drawing *> drawings[91][91];
int numberCount;
public:
Database(int numberCount): numberCount(numberCount)
{
}

void insertDrawing(Drawing * drawing)
{
for(int i = 0; i < numberCount; ++i)
{
for(int j = 0; j < numberCount; ++j)
{
if(j != i)
{
drawings[drawing->getNumber(i)][drawing->getNumber(j)].push_back(drawing);
}
}
}
}

bool findDrawings(const string &numbers, vector<Drawing *> & matchingDrawings)
{
MyBitSet bits;
vector<int> v;
parseNumbersString(numbers, v, bits);

for(vector<Drawing *>::iterator it = drawings[v.at(0)][v.at(1)].begin(); it != drawings[v.at(0)][v.at(1)].end(); it++)
{
Drawing * d = *it;
if(d->isMatching(bits))
matchingDrawings.push_back(d);
}

return matchingDrawings.size() > 0;
}
};


int main()
{
ifstream f(DATAFILENAME);

string date, city, numbers;

if(f.fail())
{
cout << "Errore apertura file dati" << endl;
return 1;
}

getline(f, numbers);
getline(f, numbers, ' ');

int numberCount;
f >> numberCount;

if(f.fail())
{
cout << "Errore parametri file dati" << endl;
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())
{
cout << "Errore apertura file di ricerca" << endl;
return 1;
}

int count;
getline(f, date, ' ');
f >> count;

if(f.fail())
{
cout << "Errore parametri file di ricerca" << endl;
return 1;
}

getline(f, numbers);
for(int i = 0; i < count; ++i)
{
getline(f, numbers);

vector<Drawing *> matchingDrawings;
if(!db.findDrawings(numbers, matchingDrawings))
continue;

cout << "-- " << numbers << " --" << endl;

for(vector<Drawing *>::iterator it = matchingDrawings.begin(); it != matchingDrawings.end(); it++)
{
cout << (*it)->toString() << endl;
}
}

return 0;
}

Niente a che vedere con i tempi di repne, ma sicuramente un netto miglioramento (circa 1/4 del tempo sulla mia macchina).

[caurusapulus]

Beh davvero una bella iniziativa :D
Cmq vi seguo dalle retrovie anche se non scrivo ;)

[Vincenzo1968]

Vincenzo prova l'ultimo:
...
Niente a che vedere con i tempi di repne, ma sicuramente un netto miglioramento (circa 1/4 del tempo sulla mia macchina).

Esatto. Purtroppo peggiora il rapporto:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica06.jpg

[Mesh89]

@cionci: in effetti da il tempo in millesimi, ma va bene cmq

@vincenzo: non preoccuparti, funziona ugualmente se la metti a 10 e 2strabiliardi, in teoria dovrebbe velocizzare col reserve del vector, ma tutto ciò in teoria (almeno dai miei ultimi esperimenti), perchè g++ fa magie.
Per quanto riguarda il crash non ne ho idea, a me va...

[Vincenzo1968]

@cionci: in effetti da il tempo in millesimi, ma va bene cmq

@vincenzo: non preoccuparti, funziona ugualmente se la metti a 10 e 2strabiliardi, in teoria dovrebbe velocizzare col reserve del vector, ma tutto ciò in teoria (almeno dai miei ultimi esperimenti), perchè g++ fa magie.
Per quanto riguarda il crash non ne ho idea, a me va...

Ehm Mesh, si lo so.
La mia preghiera era, ed è, quella di strutturare il programma in modo da non dovere modificare, ogni volta che si esegue un test, i parametri(tranne, eventualmente, i nomi e i percorsi dei due file).

Ciao :)

[cionci]

Pensavo migliorasse di più...certo che le differenze fra i compilatori sono abissali :eek:
Sul mio scendeva da 16 secondi a 4 ;)

[Vincenzo1968]

Pensavo migliorasse di più...certo che le differenze fra i compilatori sono abissali :eek:
Sul mio scendeva da 16 secondi a 4 ;)

Si, mi pare che avessimo riscontrato la stessa differenza, tra visual studio e GCC, in un'altra discussione.
Comunque, in termini assoluti, il guadagno mi sembra sostanzioso: sui file grossi, da circa un minuto e mezzo a meno di un minuto ;)
Ne approfitto per rinnovare l'invito a postare delle classifiche su diversi sistemi operativi/macchine/compilatori.

:)

[cionci]

@cionci: in effetti da il tempo in millesimi, ma va bene cmq
Ma non si faceva così per calcolare il tempo ?

((end - start)*1000.0)/CLOCKS_PER_SEC

Ora se CLOCKS_PER_SEC è uguale a un milione allora torna, ma non credo che sia un valore imposto dallo standard, ma dal sistema operativo.

Edit: ecco perché funziona: CLOCK_PER_SEC è pari a 1000 su Windows.

[||ElChE||88]

Ne approfitto per rinnovare l'invito a postare delle classifiche su diversi sistemi operativi/macchine/compilatori.

:)
Se mi spieghi quali test fare/come calcolare il rapporto, lo faccio volentieri. :)

[Vincenzo1968]

Se mi spieghi quali test fare/come calcolare il rapporto, lo faccio volentieri. :)

1) Prendi i tempi coi file più piccoli
2) Prendi i tempi coi file più grossi.
3) se t1 indica il tempo coi file più piccoli e t2 quello coi file più grossi, il rapporto è semplicemente:

t2/t1

Usa il codice che ha postato Cionci per prendere i tempi. Redireziona l'output su file. Per esempio, se l'eseguibile del codice di Cionci lo chiami "Tempi.exe", dal prompt dei comandi digita questo:


Tempi NomeFileDaEseguire > output.txt


In questo modo l'output viene creato sul file piuttosto che stampato a video.

Ciao

P.S. Non ti dimenticare di postare i dati relativi alla macchina/sistema operativo con la quale effettui i test.

[||ElChE||88]

1) Prendi i tempi coi file più piccoli
2) Prendi i tempi coi file più grossi.
Ultimo favore, poi lo faccio. :D
Mi linkeresti i file esatti, ci sono abbastanza versioni che girano.
Grazie

[Vincenzo1968]

Ultimo favore, poi lo faccio. :D
Mi linkeresti i file esatti, ci sono abbastanza versioni che girano.
Grazie

Sarebbe meglio effettuare i test con gli ultimi file che ha indicato repne(io ho problemi :cry: nello scompattarli; ho utilizzato quelli precedenti). Vai a ritroso nei post e scarica gli ultimi indicati da repne(lo faccio anch'io e vedo di postare i link, comunque).

[Vincenzo1968]

Ecco i due link:

File piccoli:
http://www.usaupload.net/d/1fzh7nkp97s

File grossi:
http://www.usaupload.net/d/pjpovf64vku

[shinya]

Quoto, anche il mio codice è abbastanza una porcata, ma è così che si programma nei contest :)

E per quale motivo si dovrebbero scrivere porcate nei contest?
Posso capire contest a tempo, tipo Topcoder, ma qui?

[DanieleC88]

E per quale motivo si dovrebbero scrivere porcate nei contest?
Infatti io sono contrario. Leggibilità prima, performance poi. :O

[Vincenzo1968]

E per quale motivo si dovrebbero scrivere porcate nei contest?
Posso capire contest a tempo, tipo Topcoder, ma qui?

Più che altro, nei contest, si dovrebbe scrivere del codice, porcata o non porcata. Non abbiamo bisogno del guru di turno che ci impartisca la lezioncina su come si deve scrivere un programma, non credi? :)
Come ha scritto Vicius, aprite un'altra discussione e impartiteci tutte le lezioncine che volete ;)

[shinya]

Più che altro, nei contest, si dovrebbe scrivere del codice, porcata o non porcata. Non abbiamo bisogno del guru di turno che ci impartisca la lezioncina su come si deve scrivere un programma, non credi? :)
Come ha scritto Vicius, aprite un'altra discussione e impartiteci tutte le lezioncine che volete ;)

Infatti non rispondevo a fek. Non ho detto che il codice di tizio e caio fa schifo.
Chiedevo il senso della frase: "Il mio codice è una porcata, lo so. Ma nei contest va cosi...".
E ho aggiunto, che posso capire se si tratta di un contest a tempo, ma non quando uno ha tutto il tempo di pensare a fondo a quello che scrive.

Forse, per stimolare, si può decidere di dare diversi premi ad ogni contest. Premio per la velocità, premio per l'eleganza, premio della giuria, ecc...

All'ICFP e all'OCCC, se non sbaglio, si fa circa cosi.

[||ElChE||88]

autore (compilatore): tempo (piccoli ~50MB) / tempo (grandi ~90MB) - rapporto

cionci (GCC): 6058ms / 11930ms - 1.97
cionci (VS): 5753ms / 11461ms - 1.99
repne (GCC): 1563ms / 3186ms - 2.03
repne (VS): 1541ms / 3006ms - 1.95

Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM

I file che hai linkato pero erano abbastanza grandini... anche i piccoli. :fagiano:

Edit: VS = Visual Studio 2008, GCC = GCC 4.3.2-tdm-1