[Vari] Contest 7: Il Lotto

[cionci]

Originariamente inviato da ^TiGeRShArK^

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

Ordina i numeri

[^TiGeRShArK^]

Originariamente inviato da cionci

Ordina i numeri

...vero

[cdimauro]

Originariamente inviato da ^TiGeRShArK^

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

Ti ha risposto cionci (e l'avevo scritto all'inizio del messaggio): ordina i numeri.

Originariamente inviato da cionci

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.

[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

[rеpne scasb]

■

[cionci]

Originariamente inviato da rеpne scasb

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]

Originariamente inviato da 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++?

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]

Originariamente inviato da 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++?

E' uno dei brutti vizi che mi sono portato dietro dal C 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

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
Uso un map per escludere tutti i doppi, ma ora mi è venuto in mente che potrei escluderli prima i doppi

[Vincenzo1968]

Originariamente inviato da cionci

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

Ohé Cionci,

mi dava 25 errori perché non c'era #include <map>. Il sambenito, dunque, te lo sei aggiudicato per un mese intero
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]

Originariamente inviato da Vincenzo1968

Ohé Cionci,

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

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

[cionci]

Originariamente inviato da Vincenzo1968

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

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

[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^]

Originariamente inviato da 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

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.. ).
Calcolando l'hash a mano in effetti ci metto troppo tempo...

[VICIUS]

Originariamente inviato da Vincenzo1968

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