[C++] Confronto di due vector molto grandi

[freetom]

Ho due mega vector

vector <string> insiemeA;
vector <string> insiemeB;

l'uno di 10.000.000 di stringhe
l'altro di appena... 20.000 stringhe

io dovrei riuscire a

confrontarli in questo modo:

Ogni 4 elementi del primo VS ogni 5 elementi del secondo e così via fino agli ultimi elementi del primo VS ogni 5 elementi del secondo...

Cerco di spiegarmi con un es... "+ visivo"

insiemeA = (1,2,3,4,5,6,7,8, 9,10,11,12,13,14,15,16,17,2 ecc...)
insiemeB = (3,10,21,40,75, 30,27,44,90,74, 12,13,18,20,31 ecc...)

io dovrei riuscire a confrontarli così:

1,2,3,4 VS 3,10,21,40,75
1,2,3,4 VS 30,27,44,90,74
1,2,3,4 VS 12,13,18,20,31
ecc...
poi passare al confronto degli altri 4 del primo VS tutti gli altri del secondo (prendendoli sempre 5 a 5) e quindi ...

5,6,7,8 VS 3,10,21,40,75
5,6,7,8 VS 30,27,44,90,74
5,6,7,8 VS 12,13,18,20,31
ecc...

Spero di essere stato abbastanza chiaro nell'esporre il mio attuale problemuccio...
e soprattutto che qualcuno/a di voi sappia come potrei fare per risolverlo

Grazie a tutti/e

[oregon]

Non ti capisco ... se la questione riguarda il thread precedente (e i vector hanno peggiorato la situazione) perchè apri un altro thread per usarli comunque?

[freetom]

Originariamente inviato da oregon
Non ti capisco ... se la questione riguarda il thread precedente (e i vector hanno peggiorato la situazione) perchè apri un altro thread per usarli comunque?

comunque provvedo subito ad aggiornare.. l'altro

in sostanza anche il vector mi si è caricato in tempi record (meno di un minuto) con i valori attesi... e quindi per ora penso possa procedere su questa strada...

grazie

[MItaly]

Originariamente inviato da freetom
in sostanza anche il vector mi si è caricato in tempi record (meno di un minuto) con i valori attesi...

Meno di un minuto? A me nel vecchio thread delle 84000 righe ciascun vettore si caricava in meno di mezzo secondo!
Ti posto il codice che usavo (anche se è piuttosto poco efficiente nel confronto ed è templatizzato in maniera oscena).

#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stdexcept>
#include <utility>

using namespace std;

template<typename TipoBase, unsigned int NumeroColonne>
class RigaBase
{
  private:
    TipoBase elementi[NumeroColonne];
  public:
    RigaBase() { };
    
    RigaBase(TipoBase Elementi[NumeroColonne])
    {
        for(unsigned int i=0; i<NumeroColonne; i++)
            elementi[i]=Elementi[i];
    };
    
    TipoBase * Elementi() { return elementi; };
    
    const TipoBase * ElementiConst() const { return elementi; };
    
    bool operator==(const RigaBase<TipoBase, NumeroColonne> & right) const
    {
        bool ret=true;
        for(unsigned int i=0; i<NumeroColonne; i++)
            ret&=(elementi[i]==right.ElementiConst()[i]);
        return ret;
    }
};

template<typename CharType, typename TipoBase, unsigned int NumeroColonne>
basic_istream<CharType> & operator>>(basic_istream<CharType> & Stream, RigaBase<TipoBase, NumeroColonne> & Right)
{
    for(unsigned int i=0; i<NumeroColonne; i++)
        Stream>>Right.Elementi()[i];
    return Stream;
}

void Confronta(const char * File1, const char * File2);

template<typename CharType, typename TipoOggetto>
void Carica(basic_istream<CharType> & InputStream, vector< TipoOggetto > & Contenitore)
{
    TipoOggetto riga;
    unsigned int contatore=0;
    while(InputStream)
    {
        InputStream>>riga;
        if(InputStream)
            Contenitore.push_back(riga);
        contatore++;
    }
}

template<typename TipoOggetto>
void Confronta(vector< TipoOggetto > & Contenitore1, vector< TipoOggetto > & Contenitore2)
{
    for(unsigned int i=0; i<Contenitore1.size(); i++)
    {
        for(unsigned int j=0; j<Contenitore2.size(); j++)
        {
            if(Contenitore1[i]==Contenitore2[j])
                cout<<"\tFile 1:"<<i<<" = File 2:"<<j<<"\n";
        }
    }
}

template<typename TipoOggetto, typename CharType>
void Confronta(basic_istream<CharType> & Stream1, basic_istream<CharType> & Stream2)
{
    vector<TipoOggetto> contenitore1, contenitore2;
    clog<<"Caricamento file 1... "<<flush;
    Carica(Stream1, contenitore1);
    clog<<"completato. "<<contenitore1.size()<<" righe caricate."<<endl;
    clog<<"Caricamento file 2... "<<flush;
    Carica(Stream2, contenitore2);
    clog<<"completato. "<<contenitore2.size()<<" righe caricate."<<endl;
    clog<<"Confronto valori... "<<flush;
    Confronta(contenitore1, contenitore2);
    clog<<"completato."<<endl;
}

template <typename TipoOggetto>
void Confronta(const char * File1, const char * File2)
{
    ifstream file1, file2;
    file1.open(File1);
    if(!file1)
        throw runtime_error("Impossibile aprire il primo file.");
    file2.open(File2);
    if(!file2)
        throw runtime_error("Impossibile aprire il secondo file.");
    Confronta< TipoOggetto >(file1, file2);
}



int main(int argc, char * argv[])
{
    if(argc<3)
    {
        cerr<<"Argomenti insufficienti"<<endl;
        return 1;
    }
    try
    {
        Confronta< RigaBase<int, 3> >(argv[1], argv[2]);
    }
    catch(exception & ex)
    {
        cerr<<"Catturata eccezione: "<<ex.what()<<endl;
        return 2;
    }
    return 0;
}

Per utilizzarlo basta passargli i nomi dei due file sulla linea di comando.

[freetom]

Originariamente inviato da MItaly
Meno di un minuto? A me nel vecchio thread delle 84000 righe ciascun vettore si caricava in meno di mezzo secondo!
Ti posto il codice che usavo (anche se è piuttosto poco efficiente nel confronto ed è templatizzato in maniera oscena).

#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stdexcept>
#include <utility>

using namespace std;

template<typename TipoBase, unsigned int NumeroColonne>
class RigaBase
{
  private:
    TipoBase elementi[NumeroColonne];
  public:
    RigaBase() { };
    
    RigaBase(TipoBase Elementi[NumeroColonne])
    {
        for(unsigned int i=0; i<NumeroColonne; i++)
            elementi[i]=Elementi[i];
    };
    
    TipoBase * Elementi() { return elementi; };
    
    const TipoBase * ElementiConst() const { return elementi; };
    
    bool operator==(const RigaBase<TipoBase, NumeroColonne> & right) const
    {
        bool ret=true;
        for(unsigned int i=0; i<NumeroColonne; i++)
            ret&=(elementi[i]==right.ElementiConst()[i]);
        return ret;
    }
};

template<typename CharType, typename TipoBase, unsigned int NumeroColonne>
basic_istream<CharType> & operator>>(basic_istream<CharType> & Stream, RigaBase<TipoBase, NumeroColonne> & Right)
{
    for(unsigned int i=0; i<NumeroColonne; i++)
        Stream>>Right.Elementi()[i];
    return Stream;
}

void Confronta(const char * File1, const char * File2);

template<typename CharType, typename TipoOggetto>
void Carica(basic_istream<CharType> & InputStream, vector< TipoOggetto > & Contenitore)
{
    TipoOggetto riga;
    unsigned int contatore=0;
    while(InputStream)
    {
        InputStream>>riga;
        if(InputStream)
            Contenitore.push_back(riga);
        contatore++;
    }
}

template<typename TipoOggetto>
void Confronta(vector< TipoOggetto > & Contenitore1, vector< TipoOggetto > & Contenitore2)
{
    for(unsigned int i=0; i<Contenitore1.size(); i++)
    {
        for(unsigned int j=0; j<Contenitore2.size(); j++)
        {
            if(Contenitore1[i]==Contenitore2[j])
                cout<<"\tFile 1:"<<i<<" = File 2:"<<j<<"\n";
        }
    }
}

template<typename TipoOggetto, typename CharType>
void Confronta(basic_istream<CharType> & Stream1, basic_istream<CharType> & Stream2)
{
    vector<TipoOggetto> contenitore1, contenitore2;
    clog<<"Caricamento file 1... "<<flush;
    Carica(Stream1, contenitore1);
    clog<<"completato. "<<contenitore1.size()<<" righe caricate."<<endl;
    clog<<"Caricamento file 2... "<<flush;
    Carica(Stream2, contenitore2);
    clog<<"completato. "<<contenitore2.size()<<" righe caricate."<<endl;
    clog<<"Confronto valori... "<<flush;
    Confronta(contenitore1, contenitore2);
    clog<<"completato."<<endl;
}

template <typename TipoOggetto>
void Confronta(const char * File1, const char * File2)
{
    ifstream file1, file2;
    file1.open(File1);
    if(!file1)
        throw runtime_error("Impossibile aprire il primo file.");
    file2.open(File2);
    if(!file2)
        throw runtime_error("Impossibile aprire il secondo file.");
    Confronta< TipoOggetto >(file1, file2);
}



int main(int argc, char * argv[])
{
    if(argc<3)
    {
        cerr<<"Argomenti insufficienti"<<endl;
        return 1;
    }
    try
    {
        Confronta< RigaBase<int, 3> >(argv[1], argv[2]);
    }
    catch(exception & ex)
    {
        cerr<<"Catturata eccezione: "<<ex.what()<<endl;
        return 2;
    }
    return 0;
}

Per utilizzarlo basta passargli i nomi dei due file sulla linea di comando.

Grazie MItaly
Mi piacerebbe molto testarlo il tuo script ma mandandolo in esecuzione mi apre la finestra nera per mezzo secondo e si richiude...

Come faccio a passargli i due file da riga di comando?

Grazie
Ciao

[oregon]

Originariamente inviato da freetom
Come faccio a passargli i due file da riga di comando?

Come ? Come avresti fatto con un qualsiasi eseguibile ... apri una finestra DOS, vai nella cartella dove c'e' l'exe e scrivi

nomeeseguibile percorsoenomeprimofile percorsoenomesecondofile

[freetom]

Originariamente inviato da oregon
Come ? Come avresti fatto con un qualsiasi eseguibile ... apri una finestra DOS, vai nella cartella dove c'e' l'exe e scrivi

nomeeseguibile percorsoenomeprimofile percorsoenomesecondofile

provato a fare come suggeritomi ma il report a video nella finestra dos mi dice

0 righe caricate per entrambi i files
confronto completato...



Comunque adesso avrei questo problemino principale... sempre riguardo questo thread ovvero il confronto dei due maga vector...

Volendo provare a confrontare i primi 4 elementi del primo vector con i primi 5 elementi del secondo ... staticamente... ho provato a fare così:

//PROVA CONFRONTO DEI DUE MEGA VECTOR...
 
 //inizio con il confrontare staticamente... solo i primi 4 elementi del primo vector con i primi 5 elementi del secondo...
 
 cout << "\n\n";
 cout << "PRIMI QUATTRO ELEMENTI DEL 1° VECTOR: ";
 cout << numeri[0];
 cout << ",";
 cout << numeri[1];
 cout << ",";
 cout << numeri[2];
 cout << ",";
 cout << numeri[3];

 cout << "\n\n";
 cout << "PRIMI CINQUE ELEMENTI DEL 2° VECTOR: ";
 cout << numeri2[0];
 cout << ",";
 cout << numeri2[1];
 cout << ",";
 cout << numeri2[2];
 cout << ",";
 cout << numeri2[3]; 
 cout << ",";
 cout << numeri2[4];
  
 
 cin.get();
 
cout << "VERIFICA ULTIMI COMPONENTI DEI DUE INSIEMI: ";
cout << "\n\n";
cout << "DELL'insieme A: ";
cout << numeri[3];
cout << "\n\n";
cout << "DELL'insieme B: ";
cout << numeri2[4];

cin.get();

 
 //PROVA CONFRONTO... 
 
 
     for (int y=0; y<5;y++)   {
     for (int x=0; x<4;x++) {   
 
 
  if (numeri[x]==numeri2[y]) {    
       
       cout << " *** ";
       cout << "numeroQ: ";
       cout << numeri[x];
       cout << " numeroC: ";
       cout << numeri2[y];
       cout << " *** ";
       cin.get();
       contapunti++;
       cout << "\n\n";
       cout << "QUANTO VALE CONTAPUNTI ADESSO? ";
       cout << contapunti;
       cin.get();

        
        //VERIFICA X ESTRATTO
        
        
      
      
      }  
      
      else
      
      {    
 
       cout << " *** ";
       cout << "numeroQ: ";
       cout << numeri[x];
       cout << " numeroC: ";
       cout << numeri2[y];
       cout << " *** ";
       cin.get();
       //contapunti++;
       cout << "\n\n";
       cout << "QUANTO VALE CONTAPUNTI ADESSO? ";
       cout << contapunti;
       cin.get();
      
      
      }
    }   
        
      
        
    } 


      cout << "punteggi totali x questa estrazione: ";
      cout << contapunti;
      cin.get(); 
 
     if (contapunti == 1) {
                    
        cout << "PUNTI:1 SCOVATO!";
        //presenze++;
        //conteggio=0;
        //ritardi.push_back(conteggio);
        
        cin.get();
        
            
     } else {
     
    //conteggio++;
    //ritardi.push_back(conteggio);
    cout << "PUNTI:1 NON SCOVATO!";
    cin.get();
    
    
    } 
 //------------------------
contapunti=0;

nonostante questo codice:

cout << "VERIFICA ULTIMI COMPONENTI DEI DUE INSIEMI: ";
cout << "\n\n";
cout << "DELL'insieme A: ";
cout << numeri[3];
cout << "\n\n";
cout << "DELL'insieme B: ";
cout << numeri2[4];

mi riporti i valori esatti...

quando vado a fare il confronto... immancabilmente l'ultimo valore di A non viene considerato... :master:

Sto diventando matto e scommetto per una sciocchezza davvero... :master:

Grazie a tutti e due

[MItaly]

Pardon... il codice che ho postato si aspetta i valori separati da spazi e non da virgole... modifica l'estrattore per la classe RigaBase in questa maniera (evidenzio in rosso la modifica):

template<typename CharType, typename TipoBase, unsigned int NumeroColonne>
basic_istream<CharType> & operator>>(basic_istream<CharType> & Stream, RigaBase<TipoBase, NumeroColonne> & Right)
{
    for(unsigned int i=0; i<NumeroColonne; i++)
    {
        if(i>0)
            Stream.ignore(1);
        Stream>>Right.Elementi()[i];
    }
    return Stream;
}

Sul mio PC per effettuare i confronti tra due file da 84000 righe ci mette circa 45 secondi.
Condizioni del test:

• PC AMD Athlon 64 3800+, 3 GB di RAM, GNU/Linux Ubuntu 9.10 x86_64;
• codice compilato con g++ 4.4.1, opzioni di compilazione: -O3 -Wall -Wextra -ansi -pedantic;
• file di input da 84000 righe, ciascuna formata da una terna di numeri compresi tra 0 e 100; in totale il programma ha individuato 7211 corrispondenze;
• il tempo di esecuzione citato è al netto dell'IO (l'output del programma è stato redirezionato su file ed è stato contato solo il tempo user del programma, come da output di time)
  

  matteo@teoubuntu:~/cpp$ time ./ConfrontoRigheSemplice.o  File1.txt File2.txt > confronto.txt
  Caricamento file 1... completato. 84000 righe caricate.
  Caricamento file 2... completato. 84000 righe caricate.
  Confronto valori... completato.
  
  real	0m56.746s Nota: intanto stavo facendo altro
  user	0m45.370s
  sys	0m0.100s

.

[freetom]

Originariamente inviato da MItaly
Pardon... il codice che ho postato si aspetta i valori separati da spazi e non da virgole... modifica l'estrattore per la classe RigaBase in questa maniera (evidenzio in rosso la modifica):

template<typename CharType, typename TipoBase, unsigned int NumeroColonne>
basic_istream<CharType> & operator>>(basic_istream<CharType> & Stream, RigaBase<TipoBase, NumeroColonne> & Right)
{
    for(unsigned int i=0; i<NumeroColonne; i++)
    {
        if(i>0)
            Stream.ignore(1);
        Stream>>Right.Elementi()[i];
    }
    return Stream;
}

Sul mio PC per effettuare i confronti tra due file da 84000 righe ci mette circa 45 secondi.
Condizioni del test:

• PC AMD Athlon 64 3800+, 3 GB di RAM, GNU/Linux Ubuntu 9.10 x86_64;
• codice compilato con g++ 4.4.1, opzioni di compilazione: -O3 -Wall -Wextra -ansi -pedantic;
• file di input da 84000 righe, ciascuna formata da una terna di numeri compresi tra 0 e 100; in totale il programma ha individuato 7211 corrispondenze;
• il tempo di esecuzione citato è al netto dell'IO (l'output del programma è stato redirezionato su file ed è stato contato solo il tempo user del programma, come da output di time)
  

  matteo@teoubuntu:~/cpp$ time ./ConfrontoRigheSemplice.o  File1.txt File2.txt > confronto.txt
  Caricamento file 1... completato. 84000 righe caricate.
  Caricamento file 2... completato. 84000 righe caricate.
  Confronto valori... completato.
  
  real	0m56.746s Nota: intanto stavo facendo altro
  user	0m45.370s
  sys	0m0.100s

.

Dopo l'ultima modifica a me stampa a video:

Caricamento file 1... completato. 1 righe caricate.
Caricamento file 2... completato. 1 righe caricate.
Confronto valori... completato.

Come faccio a vedere il result del confronto valori? Ovvero delle rispettive corripondenze???

GRAZIE infinite

[MItaly]

Se ti dice "1 righe caricate" vuol dire che ha problemi a leggere dai file... com'è il formato dei file che gli hai dato in input? Finora io l'ho collaudato con righe del tipo

1, 2, 3
4, 5, 6

e

1,2,3
4,5,6

e non aveva di questi problemi.

Tra parentesi, ho riletto il primo post ho notato che parli di 10000000 di righe e mi sono preoccupato... ma ho visto che comunque il mio programma le carica in circa 6 secondi.