[Vari] Contest 7: Il Lotto

[Vincenzo1968]

Ecco il link:

http://www.microsoft.com/downloads/d...displaylang=en

[||ElChE||88]

Compilato, ma:

BadImageFormatException
An attempt was made to load a program with an incorrect format. (Exception from HRESULT: 0x8007000B)



Edit: Risolto, compilava un pezzo in x86 e l'altro in x64.

[||ElChE||88]

Quello di gugoXX occupa 600MB di RAM con i file "piccoli", 1300MB con i file grandi.

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

cionci (C++ - GCC): 6058ms / 11930ms - 1.97
cionci (C++ - VS): 5753ms / 11461ms - 1.99
repne (C - GCC): 1563ms / 3186ms - 2.03
repne (C - VS): 1541ms / 3006ms - 1.95
gugoXX (C# / C++ - VS): 38577ms / 98240ms - 2.54

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

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

[DanieleC88]

Originariamente inviato da ||ElChE||88

4.00GB RAM

Quanto sto invidiando la tua RAM, stasera non riesco a fare nulla per quanto mi swappa tutto...

[gugoXX]

Scusate, ci sono per caso delle altre versioni di file grandi?
A me con quello che pensavo essere il piu' grande ci mette 33secondi (e ho solo 2GB di ram), come mai tutta questa differenza?
Elche, Ma il tuo e' un dual core o core singolo?

[Vincenzo1968]

Originariamente inviato da gugoXX

Scusate, ci sono per caso delle altre versioni di file grandi?
A me con quello che pensavo essere il piu' grande ci mette 33secondi (e ho solo 2GB di ram), come mai tutta questa differenza?
Elche, Ma il tuo e' un dual core o core singolo?

Originariamente inviato da Vincenzo1968

Ecco i due link:

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

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

[Vincenzo1968]

Oppure puoi crearteli a piacere con i sorgenti che ha postato repne:

LOTTO.D1:

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

#define RUOTE 250
#define ESTRAZIONI 4000
#define LUNG_NOME_RUOTE 16
#define OUTPUT_FILE_NAME "LOTTO.D1"
#define VALORI 6
#define Y_MIN 1980
#define RANGE_Y 40.0

int main(void)

{
    FILE *output_file_handle;
    time_t t;
    int m,g,a;
    unsigned long i,j,k,l;
    char nome_ruote[RUOTE][LUNG_NOME_RUOTE+1],table_lotto[90];
    double g_mese[12]={31.0,28.0,31.0,30.0,31.0,30.0,31.0,31.0,30.0,31.0,30.0,31.0};

    srand((unsigned)time(&t));

    for(i=0;i<RUOTE;i++)
    {    
	for(j=0;j<LUNG_NOME_RUOTE;j++)
	    nome_ruote[i][j]=(rand()*26.0)/(RAND_MAX+1.0)+'A';
	nome_ruote[i][j]=0;
    }

    if((output_file_handle=fopen(OUTPUT_FILE_NAME,"wt"))==NULL)
    {
	fprintf(stderr,"Non riesco a creare il file " OUTPUT_FILE_NAME "\n");
	return 1;
    }

    fprintf(output_file_handle,"Ruote %d\n",RUOTE);
    fprintf(output_file_handle,"Valori %d\n",VALORI);

    for(i=0;i<(RUOTE*ESTRAZIONI);i++)
    {
	m=(rand()*12.0)/(RAND_MAX+1.0)+1;
	g=(rand()*g_mese[m-1])/(RAND_MAX+1.0)+1;
	a=(rand()*RANGE_Y)/(RAND_MAX+1.0)+Y_MIN;
	fprintf(output_file_handle,"%.2d/%.2d/%.4d %s ",g,m,a,nome_ruote[i%RUOTE]);
	for(j=0;j<90;j++)
	     table_lotto[j]=0;
 	for(j=0;j<VALORI;j++)
	{
	    k=(rand()*(90.0-j))/(RAND_MAX+1.0)+1;
	    l=0;
	    do
	    {
		if(table_lotto[l++]==0)
		    k--;
	    } while (k);
	    table_lotto[l-1]=1;
	    fprintf(output_file_handle,"%d",l);
	    if(j!=(VALORI-1))
		fprintf(output_file_handle,",");
	}
	fprintf(output_file_handle,"\n");
    }

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

    return 0;
}

LOTTO.D2:

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

#define FIND 10000
#define MIN_G 4
#define MAX_G 5
#define OUTPUT_FILE_NAME "LOTTO.D2"

int main(void)

{
    FILE *output_file_handle;
    time_t t;
    char table_lotto[90];
    unsigned long i,j,k,l,m;

    srand((unsigned)time(&t));

    if((output_file_handle=fopen(OUTPUT_FILE_NAME,"wt"))==NULL)
    {
	fprintf(stderr,"Non riesco a creare il file " OUTPUT_FILE_NAME "\n");
	return 1;
    }

    fprintf(output_file_handle,"Find %d\n",FIND);

    for(i=0;i<FIND;i++)
    {
	for(j=0;j<90;j++)
	     table_lotto[j]=0;
	m=(rand()*(MAX_G-MIN_G+1))/(RAND_MAX+1.0);
 	for(j=0;j<(MIN_G+m);j++)
	{
	    k=(rand()*(90.0-j))/(RAND_MAX+1.0)+1;
	    l=0;
	    do
	    {
		if(table_lotto[l++]==0)
		    k--;
	    } while (k);
	    table_lotto[l-1]=1;
	    fprintf(output_file_handle,"%d",l);
	    if(j!=(MIN_G+m-1))
		fprintf(output_file_handle,",");
	}
	fprintf(output_file_handle,"\n");
    }

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

    return 0;
}

[gugoXX]

estensione 7z?
Cos'e' uno scherzo? Potevate usare zoo, Schiper, Ace o KGB...


Quelli grandi iniziano con?

Ruote 250
Valori 6
01/12/2010 HXXZLVFGBQTQVXVH 31,36,81,11,85,47
22/10/1982 UYEEEIKQBCBQARBS 36,78,80,73,15,27
24/05/1988 EMEXAARYADAVOCIV 32,30,24,6,61,73

Hihi... ho trovato un 30 febbraio hihi
Lo dicevo che il lotto e' pilotato

[Vincenzo1968]

Originariamente inviato da gugoXX

estensione 7z?
Cos'e' uno scherzo? Potevate usare zoo, Schiper, Ace o KGB...


Quelli grandi iniziano con?

Ruote 250
Valori 6
01/12/2010 HXXZLVFGBQTQVXVH 31,36,81,11,85,47
22/10/1982 UYEEEIKQBCBQARBS 36,78,80,73,15,27
24/05/1988 EMEXAARYADAVOCIV 32,30,24,6,61,73

Hihi... ho trovato un 30 febbraio hihi
Lo dicevo che il lotto e' pilotato

Quelli grandi non lo so. Io ho avuto difficoltà nello scompattarli e me li sono creati con i sorgenti di repne(dimensione circe 88 MB).
Devi chiedere a Elche.

[||ElChE||88]

Originariamente inviato da gugoXX

Elche, Ma il tuo e' un dual core o core singolo?

Il T9300 è un dual core (Penryn - per portatili).

Originariamente inviato da gugoXX

Quelli grandi iniziano con?

Ruote 250
Valori 6
01/12/2010 HXXZLVFGBQTQVXVH 31,36,81,11,85,47
22/10/1982 UYEEEIKQBCBQARBS 36,78,80,73,15,27
24/05/1988 EMEXAARYADAVOCIV 32,30,24,6,61,73

No.

Ruote 250
Valori 6
15/05/1980 SMOTOKJSEWAXWLCA 77,14,47,42,67,21
04/01/1984 GNCFNADNXFCICHUS 3,32,55,84,16,85
14/03/2001 EPZZSPDSTZXMMZVH 85,28,53,17,90,68

E' grande 90MB.
Quello che dici tu è grande 46MB (è quello da 38 sec).

Originariamente inviato da gugoXX

A me con quello che pensavo essere il piu' grande ci mette 33secondi (e ho solo 2GB di ram), come mai tutta questa differenza?

Che processore hai?
Comunque non c'è differenza tra 2GB e 4GB di RAM, il picco di consumo del programma è di 1.3GB con i file da 90MB.

[gugoXX]

Certo, ora ho capito.
Mi ero tarato su quello che pensavo essere il file grande, e che invece e' piccolo.
Ho un 3GHz dual core e 2GB.

Vedremo se mi verra' in mente qualcos'altro.
Volevo provare un algoritmo diverso, ma non e' vincente (almeno per altri 2/3 anni)

[songoge]

Originariamente inviato da gugoXX

Certo, ora ho capito.
Mi ero tarato su quello che pensavo essere il file grande, e che invece e' piccolo.
Ho un 3GHz dual core e 2GB.

Vedremo se mi verra' in mente qualcos'altro.
Volevo provare un algoritmo diverso, ma non e' vincente (almeno per altri 2/3 anni)

Lo volevi fare GPGPU?

Fate contest anche con Cuda? Sarebbe interessante vedere la differenza con una compilazione in cuda.

[gugoXX]

Originariamente inviato da songoge

Lo volevi fare GPGPU?

Fate contest anche con Cuda? Sarebbe interessante vedere la differenza con una compilazione in cuda.

No, l'ho semplicemente fatto multicore, ma anche la prima versione era cosi' e con performance non cosi' penose. Vediamo, forse mi sta venendo in mente qualcosa per ridurre.

[songoge]

Originariamente inviato da gugoXX

No, l'ho semplicemente fatto multicore, ma anche la prima versione era cosi' e con performance non cosi' penose. Vediamo, forse mi sta venendo in mente qualcosa per ridurre.

Ma anche la programmazione GPGPU è multicore. In particolare ho dato un'occhiata a cuda. Volevo utilizzarlo per costruire un motore IA, ma ho dovuto rimandare a tempi migliori perchè in questo periodo devo finire un'altro proggetto. A prima vista mi sembra troppo incasinato il sistema per gestire più processi. Forse è meglio attendere le schede multicore di intel basate su singoli core x86 (non ricordo il nome).

[Vincenzo1968]

Originariamente inviato da ||ElChE||88

Quello di gugoXX occupa 600MB di RAM con i file "piccoli", 1300MB con i file grandi.

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

cionci (C++ - GCC): 6058ms / 11930ms - 1.97
cionci (C++ - VS): 5753ms / 11461ms - 1.99
repne (C - GCC): 1563ms / 3186ms - 2.03
repne (C - VS): 1541ms / 3006ms - 1.95
gugoXX (C# / C++ - VS): 38577ms / 98240ms - 2.54

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

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

Per rilevare l'occupazione di memoria usi tools particolari come, per esempio, Performance Monitor Tool presente in Windows o lo fai da codice? In quest'ultimo caso, puoi postare un esempio?

[||ElChE||88]

Originariamente inviato da Vincenzo1968

Per rilevare l'occupazione di memoria usi tools particolari come, per esempio, Performance Monitor Tool presente in Windows o lo fai da codice? In quest'ultimo caso, puoi postare un esempio?

Uso Process Explorer, niente di complicato. Purtroppo la mia conoscenza delle API Windows è quasi nulla...

[cionci]

Ma i tempi li hai ottenuti utilizzando le ottimizzazioni ?

[Vincenzo1968]

Originariamente inviato da ||ElChE||88

Uso Process Explorer, niente di complicato. Purtroppo la mia conoscenza delle API Windows è quasi nulla...

cioè questo?:

http://technet.microsoft.com/en-us/s.../bb896653.aspx

[Vincenzo1968]

Ohé, ho misurato le performance di Repne e Cionci con Process Explorer:

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

Microsoft Windows XP Professional (32 bit)
Service Pack 3

Repne:


Cionci:


Le misure sono effettuate utilizzando il file più grosso(circa 88 MB).

[cionci]

Vincenzo, prova questo, dovrebbe essere un po' più veloce (sul mio il 25%), soprattutto se il tuo compilatore non ottimizza bene la STL dovrebbe rendere meglio. Ora guardo di togliere tutti i vector senza perdere prestazioni, e vi devo dire che su GCC 4.2 è davvero difficile, soprattutto nel caso in cui non si sappia a priori la dimensione da allocare. Proverò con un'allocazione a blocchi.

#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()
    {
        bits[0] = bits[1] = bits[2] = 0;
    }

    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, 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[items] = item;
            bits.set(item);
            ++items;
        }
        ++i;
    }
}


class Drawing
{
    MyBitSet bits;
    string text;
    int *v;

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

        v = new int[numeberCount];
        parseNumbersString(numbers, v, bits);
    }

    const string & toString()
    {
        return text;
    }

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

    int getNumber(int i)
    {
        return v[i];
    }
};


class Database
{
    vector<Drawing *> drawings[91][91];
    int numberCount;
    int *v;
public:
    Database(int numberCount): numberCount(numberCount)
    {
        v = new int[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);
                }
            }
        }
    }

    void printDrawings(const string &numbers)
    {
        MyBitSet bits;
        parseNumbersString(numbers, v, bits);

        vector<Drawing *> &l = drawings[v[0]][v[1]];

        bool print = false;

        //for(vector<Drawing*>::iterator it = l.begin(); it != l.end(); it++)
        for(unsigned int i = 0; i < l.size(); ++i)
        {
            if (l.at(i)->isMatching(bits))
            {
                if(!print)
                {
                    print = true;
                    cout << "-- " << numbers << " --" << endl;
                }

                cout  << l.at(i)->toString() << endl;
            }
        }
    }
};


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(numberCount, 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);

        db.printDrawings(numbers);
    }

    return 0;
}