Ottimizzazione codice, vantaggi poo

ninjo

il 12 giu 2014, 19:06

60 risposte

60 Risposte - Pagina 2

skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 14:47
Tu sai cosa deve fare il programma. Se devi fare un confronto per verificare se una parola fa parte della tua lista in ogni caso devi scorrere il contenitore dove queste risiedono. Ma almeno non fai mille confronti o spostamenti. Se agisci sull'overload degli operatori giusti delle classi puoi usare i contenitori che vuoi. Ma almeno gli spostamenti li fai in gruppo e non uno ad uno.
N
ninjo
Pochi posts
Iscritto da
mag, 2014
Messaggi:
37
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 16:02
Scusa gli unici spostamenti che faccio sono, in caso di m, sposto quella singola parola, in caso di u sposto tutto il vettore ed aggiorno, di ogni parola di questo vettore, l'indice in map.
Non capisco il tuo ragionamento, come farei a spostarli in gruppo anzichè uno ad uno?
skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 16:09
Prendi il caso di due vettori di puntatori smart alla classe parola.
```
std::vector<std::shared_ptr<Parola>>
```
Lo spostamento sarà solo dei puntatori smart e non della classe stessa quindi instantaneo. Nessun aggiornamento a map esterne copia di quà e sposta di là. Se questo non lo chiami velocità non so cos'è.
```
std::vector<std::shared_ptr<Parola>> v1;
std::vector<std::shared_ptr<Parola>> v2;

v1.reserve(v1.size() + v2.size());
std::copy(v2.begin(),v2.end(),std::back_inserter(v1));
```
Finito
skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 16:18
Scordati per un attimo le map con group_id. Se un vettore tiene tutti gli hash delle parole del gruppo non serve neanche che tieni conto del gruppo dentro la classe parola. Una classe del genere può fare al tuo caso
```
class Gruppo
{
..........................
private:
   vector<shared_ptr<Parola>> paroleDelGruppo;
   int gruppoID;
}
```
ogni spostamento di parole da un gruppo all'altro nel caso avessi un vector di gruppi fa si che le parole si aggiornino da sole il gruppo di appartenenza.
N
ninjo
Pochi posts
Iscritto da
mag, 2014
Messaggi:
37
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 16:41
Ma non è che stiamo reinventando la ruota? Nel senso, a quel punto la differenza tra come dici tu, un vector<Gruppi>{vector<>Parole;int ID;} e un vector<vector<int>> non la vedo. Entrambi li devo scorrere in due dimensioni per trovare la parola(se dici che non devo usare una map per gli indici), perchè non so quella parola in che vettore<Gruppo> si trovi.

Piccola precisazione: deve essere eseguibile su c++ e non c++11, infatti non ho potuto usare unordered_map.
skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 16:54
Se non ti garba come soluzione non credo che tu abbia altre alternative. Continua per la tua strada. Con la mia proposta gli spostamenti li puoi fare guadagnando in velocità, la ricerca per non complicare le classi puoi crearti una map (visto che ti piace tanto) del tipo
```
map<string,Gruppo *>
```
dove ogni stringa viene mappata al gruppo di appartenenza. Fai la ricerca su string e ti ritorna il puntatore al gruppo di appartenenza.
Poi se non ti piace la soluzione proposta sei libero di ascoltare anche altre campane.
N
ninjo
Pochi posts
Iscritto da
mag, 2014
Messaggi:
37
Re: Ottimizzazione codice, vantaggi poo
19 giu 2014, 17:04
No anzi, stavo cercando di capire bene cosa intendessi, siccome non sono pratico di oggetti, classi ecc. Ora provo con map<string,Gruppo *>, vediamo come va.

ninjo

Pochi posts

Iscritto da: mag, 2014

Messaggi:: 37

Re: Ottimizzazione codice, vantaggi poo

20 giu 2014, 00:10

Ho fatto cosi:


dichiaro
map<int,Gruppi*> mappaHash;
    vector<Gruppi*> vecGruppi;

poi quando inserisco faccio
               Gruppi* ptr = new Gruppi(hk,x);
                mappaHash.insert(pair<int,Gruppi*>(hk,ptr));
               vecGruppi[x]=ptr;

e poi con

map<int,Gruppi*>::iterator it=mappaHash.find(hk1),it2;


if(s == 'm')
                {
                    vecGruppi[grupId1]->elimina(hk1);
                    vecGruppi[grupId2]->inserisci(hk1);
                    it->second->SetGroupID(grupId2);
                }

                else if(s == 'u' )
                {

                    it->second->SetGroupID(grupId2);
                    vecGruppi[grupId2]->unisci(vecGruppi[grupId1]->ritornaVettore());
                    vecGruppi[grupId1]->svuota();
                }

solo che non ho creato il puntatore all gruppo di appartenenza come speravo di fare, dove sbaglio?

skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
20 giu 2014, 00:28
Puoi postare il programma completo con una descrizione dettagliata di ciò che vuoi raggiungere? Vorrei capire bene il ruolo di queste hash e a che ti serve inserire/spostare/modificare/unire le stringhe in un gruppo. Il gruppo a cosa serve? Insomma fammi un quadro completo.
N
ninjo
Pochi posts
Iscritto da
mag, 2014
Messaggi:
37
Re: Ottimizzazione codice, vantaggi poo
20 giu 2014, 00:37
Per un ipotetico input:
-> e ciao come stai
Inizialmente, gli elementi sono divisi in tre insiemi S1={“ciao”}, S2={“come”}, S3={“stai”}.
Le operazioni possibili sono:
• u ciao come: Unire gli insiemi contenenti ciao(S1) e come(S2).
• m ciao stai : Muovi la stringa ciao nell’insieme di stai(S3).
• s ciao: Stampa il numero di elementi nell’insieme di ciao e la somma della lunghezza delle stringhe presenti.

Ora, come posso creare una map<hashkey, puntatoreAx>, che per puntatoreAx intendo, un puntatore ad int m_ID; della classe Gruppo, cosichè quando sposto/unisco, cambiando l'indirizzo del puntatore verso l'int m_ID della Classe Gruppo di destinazione, mi aggiorna automaticamente tutti gli altri puntatori con lo stesso indirizzo in map<hashkey, puntatoreAx>.

skynet

Utente Famoso

Iscritto da: lug, 2010

Messaggi:: 3060

Re: Ottimizzazione codice, vantaggi poo

20 giu 2014, 15:07

Vedi cosa puoi fare con queste classi che ho creato.

class Parola
{
   public:
      Parola(const std::string & str = "")
         : m_string(str)
         , m_hash(funzHash(str))
      {

      };
      const int GetHash() const { return m_hash; };
	  const std::string & GetString() const { return m_string; };
   private:
      const int funzHash(const std::string & parolaHash)
      {
         int h = 5381;
         const size_t size = parolaHash.size();
         for (size_t i = 0; i < size; ++i)   
         {
            h = h * 33 + parolaHash[i];
         }
         h = abs(h);
         return h;
      }
   private:
      std::string m_string;
      int m_hash;
};


class Gruppi
{
	std::map<std::string,Parola> gruppoParole;
public:
	Gruppi() : m_ID(-1){};
	~Gruppi(){};
	const int GetGroupID() const { return m_ID; };
	const size_t GetGroupSize() const { return gruppoParole.size(); };
    const void SetGroupID(const int & groupID){ m_ID = groupID; };
	std::map<std::string,Parola> & GetGruppo() { return gruppoParole; };
	const bool InserisciParola(const std::string & parola)
	{
		std::map<std::string,Parola>::const_iterator it = gruppoParole.find(parola);
		if(it != gruppoParole.end())
		{
			Parola nuovaParola(parola);
			gruppoParole[parola] = nuovaParola;
			return true;
		}
		return false;
	}

	const bool InserisciParola(const Parola & parola)
	{
		std::map<std::string,Parola>::const_iterator it = gruppoParole.find(parola.GetString());
		if(it != gruppoParole.end())
		{
			gruppoParole[parola.GetString()] = parola;
			return true;
		}
		return false;
	}
	const bool CercaParola(const std::string & parola)
	{
		return (gruppoParole.find(parola) != gruppoParole.end());
	}
	const bool EliminaParola(const std::string & parola)
	{
		std::map<std::string,Parola>::const_iterator it = gruppoParole.find(parola);
		if(it != gruppoParole.end())
		{
			gruppoParole.erase(it);
			return true;
		}
		return false;
	}

	const void UnisciGruppo(Gruppi & gruppo)
	{
		UnisciGruppo(gruppo.GetGruppo());
	}

	const void UnisciGruppo(std::map<std::string,Parola> & gruppoDaUnire)
	{
		gruppoParole.insert(gruppoDaUnire.begin(),gruppoDaUnire.end());
	}
	
private:
	  int m_ID;
};

N
ninjo
Pochi posts
Iscritto da
mag, 2014
Messaggi:
37
Re: Ottimizzazione codice, vantaggi poo
20 giu 2014, 16:10
Intanto grazie per l'aiuto, ma la ricerca tu la fai direttamente sulle stringhe anzichè sulle hash? Usando le hash anzichè le stringhe, la ricerca, inserimento dovrebbe essere molto più veloce, perchè un conto è inserire/cercare una parola di 100 lettere, un conto è un hash di max 8 numeri. Il ruolo delle hash è questo, velocizzare il tutto, il programma mi funziona, sto cercando di trovare un modo per renderlo più veloce.
Io mio collo di bottiglia diciamo, che mi faceva perdere un po' di tempo, era nell'aggiornare il grup_id di map<hashkey,grup_id> quando dovevo unire. Infatti, mettiamo il caso dovevo spostare tutto il gruppo1 in gruppo3, dovevo andare ad aggiornare tutti i grup_id delle hash del gruppo1 e dirgli che ora sono in gruppo3. Quello che vorrei capire è se c'è un metodo, che anzichè avere map<hashkey,grup_id>, con grup_id che sarebbe un int alla fine, un map<hashkey,puntatore*>, cosi quando gli dico vedi che puntatoreGruppo1 è diventato puntatoreGruppo2, non devo andare ad aggiornarli uno ad uno, ma li aggiorna direttamente siccome è cambiato l'indirizzo di puntatoreGruppo1.
skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
20 giu 2014, 20:11
Quanto tempo perdi a creare un hash?
skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: Ottimizzazione codice, vantaggi poo
20 giu 2014, 23:43
```
const void UnisciGruppo(std::map<std::string,Parola> & gruppoDaUnire)
   {
      gruppoParole.insert(gruppoDaUnire.begin(),gruppoDaUnire.end());
   }
```
Vedi qualche movimentazione di groupID in quel codice? NO, perche il groupID fa parte della classe che comprende la map, quindi nell'unione non devi fare nulla. la map dentro il gruppo non sa a quale gruppo appartiene ed è giusto così.
Se proprio vuoi usare gli hash basta cambiare la definizione del map cambiando la string in int.Il resto funziona cmq come prima.

skynet

Utente Famoso

Iscritto da: lug, 2010

Messaggi:: 3060

Re: Ottimizzazione codice, vantaggi poo

21 giu 2014, 00:00

Ecco la modifica col hash

class Parola
{
public:
	Parola(const std::string & str = "")
		: m_string(str)
		, m_hash(funzHash(str))
	{

	};
	const int GetHash() const { return m_hash; };
	const std::string & GetString() const { return m_string; };
	static const int funzHash(const std::string & parolaHash)
	{
		int h = 5381;
		const size_t size = parolaHash.size();
		for (size_t i = 0; i < size; ++i)
		{
			h = h * 33 + parolaHash[i];
		}
		h = abs(h);
		return h;
	}
private:
	std::string m_string;
	int m_hash;
};


class Gruppi
{
	std::map<int, Parola> gruppoParole;
public:
	Gruppi() : m_ID(-1){};
	~Gruppi(){};
	const int GetGroupID() const { return m_ID; };
	const size_t GetGroupSize() const { return gruppoParole.size(); };
	const void SetGroupID(const int & groupID){ m_ID = groupID; };
	std::map<int, Parola> & GetGruppo() { return gruppoParole; };
	const bool InserisciParola(const std::string & parola)
	{
		const int hash = Parola::funzHash(parola);
		std::map<int, Parola>::const_iterator it = gruppoParole.find(hash);
		if (it != gruppoParole.end())
		{
			Parola nuovaParola(parola);
			gruppoParole[hash] = nuovaParola;
			return true;
		}
		return false;
	}

	const bool InserisciParola(const Parola & parola)
	{
		std::map<int, Parola>::const_iterator it = gruppoParole.find(parola.GetHash());
		if (it != gruppoParole.end())
		{
			gruppoParole[parola.GetHash()] = parola;
			return true;
		}
		return false;
	}
	const bool CercaParola(const std::string & parola)
	{
		return CercaParola(Parola::funzHash(parola));
	}

	const bool CercaParola(const int & parolaHash)
	{
		return (gruppoParole.find(parolaHash) != gruppoParole.end());
	}

	const bool EliminaParola(const std::string & parola)
	{
		return EliminaParola(Parola::funzHash(parola));
	}

	const bool EliminaParola(const int & parolaHash)
	{
		std::map<int, Parola>::const_iterator it = gruppoParole.find(parolaHash);
		if (it != gruppoParole.end())
		{
			gruppoParole.erase(it);
			return true;
		}
		return false;
	}

	const void UnisciGruppo(Gruppi & gruppo)
	{
		UnisciGruppo(gruppo.GetGruppo());
	}

	const void UnisciGruppo(std::map<int, Parola> & gruppoDaUnire)
	{
		gruppoParole.insert(gruppoDaUnire.begin(), gruppoDaUnire.end());
	}

private:
	int m_ID;
};

Devi accedere o registrarti per scrivere nel forum

60 risposte