Problema efficienza algoritmo STL

di il
9 risposte

Problema efficienza algoritmo STL

Buongiorno a tutti. Ho il seguente problema:
In un programma che sto sviluppando mi sono messo ad integrare alcune delle novità introdotte in C++0x e + precisamente il std::move. Praticamente il mio problema è questo:
1. Ho un vettore di string ricavato da un query database sqlite.
2. Ho un std::set di string che dovrebbe ricevere questo vettore.
Il vettore dopo l'inserimento nel set anderbbe distrutto e non + utlizzato. E ho pensato di usare il std::move per evitare copie inutili del suddetto vettore.
Allora prima della integrazione del std::move la mia funzione era questa:

std::vector<std::wstring> vecDb;
std::set<std::wstring> playList;
.................
playList.insert(vecDb.begin(),vecDb.end());
Nel pezzo di codice sopra viene duplicato ogni elemento del vettore dentro il set (come giusto che sia)
Siccome sto vettore non verrà + utilizzato (in quanto i dati stano su set) eseguendo std::move dovrei ricavare il voluto. E bene.

for(auto it = vecDb.cbegin(); it != vecDb.cend(); ++it)
        playList.insert(std::move(*it));
Questo codice funziona ed è ok. Mi domandavo se c'è qualche altra possibilità di fare ciò senza il ciclo for. Qualcosa che interagisce col set tipo il std::for_each. Solo che il for_each vuole una funzione e potrei utilizzare anche i lambda ma mi sembra sempre la stessa pasta.
Quindi sto cercando un pezzo di codice migliore per fare tutto ciò.
Grazie dell'attenzione.

9 Risposte

  • Re: Problema efficienza algoritmo STL

    Che io sappia il meglio che si puo fare è usare una lambda function.
    Tra l'altro non capisco quando dici che è ok. Nelle prove che ho fatto io la stringa non viene spostata dal vector al set (ma può dipendere anche dall'implementazione della string stessa).
    Che compilatore usi?
  • Re: Problema efficienza algoritmo STL

    Visual Studio 2010. il vector tiene dei path di file non ripetuti quindi univoci. Dalle mie prove viene spostata sia in debug che in release. Il vettore se prima teneva 100 elementi dopo lo spostamento delle stringhe sempre 100 elementi contiene ma non si può far + riferimento in quanto le stringhe contiengono garbage. Almeno così ho capito io l'implementazione del std::move spiegato quà:


    Specificato anche quà:
    
    1. When the assignment source is a temporary, it's going to be destroyed very soon ("at the semicolon"). However, it could be std::move(lvalue), in which case it might survive for a long time until reassignment or destruction.
    
    Il mio caso è il secondo (lvalue). Il vettore verrà distrutto dopo l'uscita dalla funzione.
  • Re: Problema efficienza algoritmo STL

    Io VC++ 2010 Express quindi l'implementazione STL è la stessa.
    Il vettore verrà distrutto dopo l'uscita dalla funzione.
    Perciò è inserito in una funzione. Però se non ho capito male tu in realtà restituisci un std::set da quella funzione. In pratica siamo in una situazione simile:
    
    std::set<std::string> kappa() { 
    		std::vector<std::string> vecDb;
    		string a = "alpha";
    		string b = "beta";
    		string c = "gamma";
    		string d = "teta";
    
    		vecDb.push_back(a);
    		vecDb.push_back(b);
    		vecDb.push_back(c);
    		vecDb.push_back(d);
    
    		std::set<std::string>playList;
    
    		for (auto i = vec.cbegin(); i != vec.cend(); ++i) {
    			playList.insert(std::move(*i));
    		}
                    // qui
    		return playList;
                    // qua
    }
    
    Se è così, la move semantics non si applica sulla stringa, ma sul set restituito. Nel punto "qui" il vector è ancora valido e con tutti gli elementi accessibili (le stringhe sono copiate, non spostate).
    Nel punto "qua" invece ( e seguendo tutto il percorso di debug) si nota che il set viene spostato e poi il vector distrutto.
    Se è questo il caso in cui ti trovi, la cosa più efficiente (se non hai bisogno prima della playlist) è applicare la RVO così:
    
        return std::set<std::string>(vec.cbegin(),vec.cend());
    
  • Re: Problema efficienza algoritmo STL

    Intanto grazie per l'interessamento.
    Il mio modello è diverso. Ti mostro la classe (una parte perche è abbastanza lunga). Ho una classe CplayList (sotto c'è il codice). Ho poi una superclasse CPlaylistManager che non è altro che un wrapper delle funzioni di una playlist ma che contiene un std::map di Cplaylist
    (key = nome, value = std::shared_ptr(CPlaylist).)
    
    class CPlaylist
    {
    public:
    	CPlaylist(void);
    	virtual ~CPlaylist(void);
    	bool CreatePlaylist(const std::vector<std::wstring> & directoryPath);
    	bool AddTrackToPlaylist(const std::wstring & trackPath);
    	void ShufflePlaylist(void);
    	void UnShufflePlaylist(void);
    	std::wstring GetNextTrack(void);
    	std::wstring GetPrevTrack(void);
    	std::wstring GetTrackAtPosition(unsigned int pos);
    	void DeleteTrackFromPlaylist(unsigned int pos);
    	void SetPlayListName(const std::wstring & _name);
    	std::wstring GetPlayListName(void);
    private:
    	std::set<std::wstring> playList;  //questo è il set in questione.
    	std::vector<std::set<std::wstring>::iterator> playListPointer;
    	std::vector<std::set<std::wstring>::iterator> unShuffledplayListPointer;
    	std::vector<std::set<std::wstring>::iterator>::iterator playListCounter;
    	std::wstring m_playListName;
    	bool m_shuffleStatus;
    	unsigned int m_trackPosition;
    	std::wstring m_playListFileName;
    public:
    	bool SaveToFile(void);
    	bool LoadFromFile(const std::wstring & fileName);
    	const std::wstring & GetCurrentTrackPath(void);
    	unsigned int GetTrackPosition(void);
    	unsigned int GetPlaylistSize(void);
    
    };
    
    La classe PlaylistManager
    
    class CPlaylistManager
    {
    public:
    	CPlaylistManager(void);
    	virtual ~CPlaylistManager(void);
    
    //questa funzione è sviluppata sotto.
    	bool AddPlaylist(const std::wstring & directoryPath, const std::wstring & name);
    
    	bool SelectPlaylist(const std::wstring & playlistName);
    	std::wstring GetNextItem(void);
    	std::wstring GetPrevItem(void);
    	std::wstring GetItemAtPos(unsigned int pos);
    	bool DeletePlaylist(const std::wstring & playlistName);
    private:
    	std::map<std::wstring,std::shared_ptr<CPlaylist>> m_allPlaylists;
    	std::map<std::wstring,std::shared_ptr<CPlaylist>>::iterator m_selectedPlaylist;
    	CDatabaseHandler	m_databaseHandler;
    	bool SaveAllPlayLists(void);
    	bool LoadAllPlaylists(void);
    	std::vector<std::wstring> m_playlistsPath;
    public:
    	std::vector<std::wstring> GetPlayLists(void);
    	void GetFileTag(fileTag & thisFileTag);
    	unsigned int GetCurrentItemPos(void);
    	unsigned int GetCurrentPlaylistSize(void);
    };
    
    Sviluppo della funzione AddPlaylist
    
    bool CPlaylistManager::AddPlaylist(const std::wstring & directoryPath,const std::wstring & name)
    {
    	std::vector<std::vector<std::wstring> > songsInPath; 
    
    //quì è ciò che viene restituito dal database dalla funzione Search del database Handler
    //sta funzione ritorna true se è riuscito a trovare delle canzoni nel directoryPath e li mette nel
    songpath[0].
    //E' un algoritmo un pò complicato che funziona a seconda del tipo di search. 
    
    	if(m_databaseHandler.Search(SEARCH_BY_PATH,directoryPath,songsInPath,true))
    	{
    		auto thisPlayList = std::make_shared<CPlaylist>();
    		auto it = m_allPlaylists.insert(std::make_pair(name,thisPlayList));
    		if(it.second)
    		{
    			it.first->second->CreatePlaylist(songsInPath[0]);
    
    // songPath[0] è il vettore in questione che dopo esere inserito nel set della classe
    // Cplaylist (sviluppo sotto) non verrà + usato e quindi distrutto 
    // all'uscita della funzione AddPlaylist.
    
    			it.first->second->SetPlayListName(name);
    			m_selectedPlaylist = it.first;
    		}
    	}
    	
    	if(m_selectedPlaylist != m_allPlaylists.end())
    		m_selectedPlaylist->second->ShufflePlaylist();
    	return true;
    }
    
    la funzione CreatePlaylist della classe CPlaylist
    
    bool CPlaylist::CreatePlaylist(const std::vector<std::wstring> & directoryPath)
    {
    //quì c'è l'inserimento che ti dicevo
    //playList è il set che è un membro della classe CPlayList
    
    	for(auto vecIt = directoryPath.cbegin(); vecIt != directoryPath.cend(); ++vecIt)
    		playList.insert(std::move(*vecIt));
    
    //quì poi ci sono dei iterator per trovare + velocemente i file ma non c'entra col problema
    	
    	for(auto it = playList.begin(); it != playList.end(); ++it)
    		playListPointer.push_back(it);
    	unShuffledplayListPointer = playListPointer;
    	playListCounter = playListPointer.begin();
    	return true;
    }
    
    Quindi il mio std::set dura per tutto il programma diciamo (cioè per quanto dura una istanza di una CPlaylist. Mi sembrava il posto giusto quello da applicare il std::move sappendo che il vettore una volta estrappolato i dati non verrà + usato. Cosa ne pensi?
  • Re: Problema efficienza algoritmo STL

    OK ci sono riuscito. Come dicevi tu gli elementi del vettore venivano copiati e non spostati. Serviva un cast per trasformare ogni stringa in rvalue.
    
    bool CPlaylist::CreatePlaylist(std::vector<std::wstring> & directoryPath)
    {
    	for(auto vecIt = directoryPath.begin(); vecIt != directoryPath.end(); ++vecIt)
    		playList.insert(std::move(static_cast<std::wstring &&>(*vecIt)));
    
    //quì guardando il debugger il vettore ha grandezza uguale ma con elementi vuoti.
    
    	for(auto it = playList.begin(); it != playList.end(); ++it)
    		playListPointer.push_back(it);
    	unShuffledplayListPointer = playListPointer;
    	playListCounter = playListPointer.begin();
    	return true;
    }
    
    Cmq non capisco il perche. già il std::move dovrebbe fare il suddetto cast. perche serve sto brutto cast per fare tutto ciò.
  • Re: Problema efficienza algoritmo STL

    Mezz'ora in debug passo passo, per poi scoprire che il debugger in toolbox prende granchi.
    Dunque: il cast non è necessario (se proprio si vuole si può usare std::forward<wstring>() che fa la stessa cosa.
    
    int main(etc) ...
    		std::vector<std::string> vecDb;
    		string a = "alpha";
    		string b = "beta";
    		string c = "gamma";
    		string d = "teta";
    
    		vecDb.push_back(a);
    		vecDb.push_back(b);
    		vecDb.push_back(c);
    		vecDb.push_back(d);
    		std::set<std::string> playList;
    
    		for (auto i=vecDb.begin(); i !=vecDb.end(); ++i) {
    			playList.insert(std::move(*i));
    		}
    
    		for (auto i=vecDb.begin(); i !=vecDb.end(); ++i) {
    			cout << *i << endl;
    		}
    
    L'output è effettivamente vuoto (come ci si aspetta) anche senza mettere il cast.
    La domanda iniziale era se c'era un modo migliore invece del ciclo. C'è. (Riporto la parte interessata).
    
    		vecDb.push_back(d);
    		std::set<std::string> playList;
    
                    // sposta la stringa ma solo con begin(), non cbegin() 
    		std::move(vecDb.begin(),vecDb.end(),std::inserter(playList,playList.begin()));
    
    		for (auto i=vecDb.begin(); i !=vecDb.end(); ++i) {
    			cout << *i << endl;
    		}
    [
    
    Come riportato nel commento, il giochino funziona solo se non si passa un const_iterator con cbegin() (in effetti essendo costante non può modificare il contenuto). L'output resta vuoto.
    Io suggerirei di modificare in questo modo:
    
    bool CPlaylistManager::AddPlaylist(const std::wstring & directoryPath,const std::wstring & name)
    {
       std::vector<std::vector<std::wstring> > songsInPath;
    
    //quì è ciò che viene restituito dal database dalla funzione Search del database Handler
    //sta funzione ritorna true se è riuscito a trovare delle canzoni nel directoryPath e li mette nel
    songpath[0].
    //E' un algoritmo un pò complicato che funziona a seconda del tipo di search.
    
       if(m_databaseHandler.Search(SEARCH_BY_PATH,directoryPath,songsInPath,true))
       {
          auto thisPlayList = std::make_shared<CPlaylist>();
          auto it = m_allPlaylists.insert(std::make_pair(name,thisPlayList));
          if(it.second)
          {
             // Si sposta il vector da qui alla funzione. Usando il move si 
             // rafforza l'idea che da qui il vector deve sparire. 
             it.first->second->CreatePlaylist(std::move(songsInPath[0]));
    
    // songPath[0] è il vettore in questione che dopo esere inserito nel set della classe
    // Cplaylist (sviluppo sotto) non verrà + usato e quindi distrutto
    // all'uscita della funzione AddPlaylist.
    
             it.first->second->SetPlayListName(name);
             m_selectedPlaylist = it.first;
          }
       }
       
       if(m_selectedPlaylist != m_allPlaylists.end())
          m_selectedPlaylist->second->ShufflePlaylist();
       return true;
    }
    
    // Un reference ritengo sia meglio usarlo quando si vuole che il contenuto del vector resti valido
    // durante la chiamata. 
    bool CPlaylist::CreatePlaylist(const std::vector<std::wstring>&& directoryPath)
    {
    //quì c'è l'inserimento che ti dicevo
    //playList è il set che è un membro della classe CPlayList
    
        // Si spostano gli elementi dal vector al set usando begin().
        std::move(directoryPath.begin(),directoryPath.end(),std::inserter(playList,playList.begin()));
     
    //quì poi ci sono dei iterator per trovare + velocemente i file ma non c'entra col problema
       
       for(auto it = playList.begin(); it != playList.end(); ++it)
          playListPointer.push_back(it);
       unShuffledplayListPointer = playListPointer;
       playListCounter = playListPointer.begin();
       return true;
    }
    
    Ah. Come sempre:

    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.
  • Re: Problema efficienza algoritmo STL

    Grande, lo sapevo che c'era un altro modo, devo lavorare un pò con il rvalue e capirlo meglio. LO provo appena posso. Secondo te è meglio implementare il move constructor e move assignment per la classe CPlayList e non usare il shared_ptr nella mappa? A mio avviso non avrei tanto guadagno, tanto copiare un puntatore non è un operazione lunga. cmq giusto x info, il codice fa parte di un Front-End x CarPC che sto implementando a mio uso quindi anche il resto è "as is" . Tanto o userò solo io
  • Re: Problema efficienza algoritmo STL

    Potresti farlo per toglierti lo sfizio, ma ai fini pratici non ti servirebbe a molto.
    Considera che dovresti spostare sei dati da una CPlayList all'altra.
    
    CPlaylist::CPlaylist(CPlaylist&& rhs) :
    	playList(std::move(rhs.playList)), 
    	playListPointer(std::move(rhs.playListPointer)),
    	etc...
    
    { }
    
    e se sono di più è una faticaccia. A mio avviso non ne vale la pena.
    Addirittura io metterei privato il costruttore e inserirei una funzione statica per creare solo puntatori a quella classe.
    
    class CPlaylist
    {
    public:
       static CPlaylist* instance() { return new CPlaylist; }
    protected:
       CPlaylist();
       etc...
    
    // altrove
       shared_ptr<CPlaylist> p1(CPlaylist::instance());
       unique_ptr<CPlaylist> p2(CPlaylist::instance());
    
    
  • Re: Problema efficienza algoritmo STL

    Grazie di tutto. Come vedi mi piace un casino STL ma su Internet trovo solo esempi banali. Sto studiando Effective STL di Scott Meyers e devo dire che di cose da studiare c'è ne sono. Di nuvo grazie e alla prossima.
Devi accedere o registrarti per scrivere nel forum
9 risposte