[Vari] Contest 7: Il Lotto

[banryu79]

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

[Vincenzo1968]

Originariamente inviato da rеpne scasb

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

[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 , e tu gia a 0 secondi .

[magix2003]

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

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]

Originariamente inviato da rеpne scasb

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

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


Redirezione su file:

[Vincenzo1968]

Originariamente inviato da magix2003

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

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]

Originariamente inviato da rеpne scasb

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

Originariamente inviato da Vincenzo1968

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