Newsgroup: it.comp.lang.c++
Titolo: E' questo il modo...

... di scrivere una funzione???
string stripPBreaks(string s) {
   int br;
   while((br = s.find("<P>")) != string::npos)
     s.erase(br, strlen("<P>"));
   while((br = s.find("</P>")) != string::npos)
    s.erase(br, strlen("</P>"));
   return s;
}
...
Kiuhnm


Si', perche'?
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 Si', perche'?
Perché riesamina s sempre dall'inizio (almeno credo)! Alla faccia 
dell'efficienza.
Kiuhnm

Kiuhnm wrote:

E chi ha detto che deve essere efficiente?
Comunque, io l'avrei scritta cosi':
string stripPBreaks(string s) {
   const char startTag[] = "<P>";
   const char endTag[] = "</P>";
   int br = 0;
   while((br = s.find(startTag, br)) != string::npos) {
     s.erase(br, sizeof startTag - 1);
   }
   br = 0;
   while((br = s.find(endTag, br)) != string::npos) {
     s.erase(br, sizeof endTag - 1);
   }
   return s;
}
oppure, cambiandone la semantica, cosi':
void stripPBreaks2(string &s) {
   const char startTag[] = "<P>";
   const char endTag[] = "</P>";
   int br = 0;
   while((br = s.find(startTag, br)) != string::npos) {
     s.erase(br, sizeof startTag - 1);
   }
   br = 0;
   while((br = s.find(endTag, br)) != string::npos) {
     s.erase(br, sizeof endTag - 1);
   }
}
Se la prima funzione veniva chiamata nel segente modo:
    str = stripPBreaks(str);
quest'ultima va chiamata cosi':
    stripPBreaks(str);
ed e' notevolmente piu' efficiente oltre che piu' compatta.
Se invece la prima veniva chiamata cosi':
    str2 = stripPBreaks(str1);
quest'ultima va chiamata cosi':
    str2 = str1;
    stripPBreaks(str2);
ed e' probabilmente altrettanto efficiente quanto la prima versione.
Comunque, come ha scritto Knuth, l'ottimizzazione prematura e' 
all'origine di tutti i mali.
Questa funzione probabilmente era abbastanza efficiente anche nella 
versione originale.
Se, come presumo, fosse finalizzata a elaborare testo HTML,
e' piuttosto raro che una riga HTML contenga piu' di un tag <P> o piu' 
di un tag </P>, e comunque la find e' molto veloce, a confronto della 
copia di una stringa.
Bisogna scrivere il codice piu' semplice possibile e ottimizzare 
(complicando il codice) solo i colli di bottiglia.


 (complicando il codice) solo i colli di bottiglia.
Non sono completamente d'accordo (sì, ho letto i libri di Knuth).
Ottimizzare il codice in seguito è una cosa, ma usare di proposito 
algoritmi più lenti di qualche ordine di grandezza per evitare di 
scrivere una riga è veramente assurdo.
E poi i programmi danno problemi proprio perché il programmatore pensa 
"Di solito..." e invece l'utente dice "Volendo posso usarla anche in 
questo caso...".
Non ritengo *educativo* mostrare una funzione scritta in quel modo 
quando basta pochissimo per renderla O(n) anziché O(pn). L'algoritmo 
banale è O(n). Bisogna proprio mettersi d'impegno per peggiorarlo.
Non ottimizziamo il codice fin dall'inizio, ma non cerchiamo di 
peggiorarlo a tutti i costi!
Kiuhnm

 peggiorarlo a tutti i costi!
Altra cosa saggia è usare il codice quando possibile. Quindi se devi
usare molto processing su file HTML ti consiglierei di prendere in
considerazione una qualche libreria di parsing, o al limite delle regex.
Molto probabilmente l'ottimizzazione nel motore sottostante è già stata
fatta.
-- 
Ricordo che alla libertà di parola, è associata anche la libertà 
di pensiero. Purtroppo vedo che sempre più spesso si fa uso della 
prima e non della seconda.

    int br = 0;
Io metterei unsigned int


 Io metterei unsigned int
Ancora meglio, std::string::size_type, che e' il tipo ritornato da 
std::string::find.


 std::string::find.
Giusto. La tua è quella certamente corretta. Non credo che lo standard
specifichi che tale tipo debba essere un unsigned int.


 banale è O(n). Bisogna proprio mettersi d'impegno per peggiorarlo.
Hai ragione. In questo caso, si può scrivere in poche righe
qualcosa di corretto, semplice e generale.
Nell'esempio ci sono anche delle altre cose fastidiose:
- l'uso delle stringa costanti "<P>" e "</P>" come argomenti
per string::find e strlen
- il fatto che i due cicli while differiscano solo per gli argomenti
passati a string::find e strlen (e qui sono ridondante anch'io :-) )
Ecco le mie poche righe:
//-- inizio file cpp --//
#include <iostream>
#include <string>
#include <stack>
#include <cstdlib>
void erase_substring(std::string& str, const std::string substr){
    using namespace std;
    typedef string::size_type StrSize;
    typedef stack<string::size_type> Stack;
    typedef Stack::size_type StkSize;
    Stack substr_found;
    const StrSize substr_size( substr.size() );
    const StrSize not_found( string::npos );
    StrSize found( str.find(substr) );
    // Ricerca la substr e quando la trova salta i caratteri
    // gia verificati.
    // Memorizza gli indici delle stringhe che ha trovato in
    // uno stack.
    while(not_found != found){
        substr_found.push(found);
        // La verifica della posizione found
        // viene fatta da string::find()
        found += substr_size;
        found = str.find(substr, found);
    }
    // Cancella le sottostringhe a partire dalla fine.
    // Gli indici estratti dallo stack restano validi.
    while(!substr_found.empty()){
        str.erase(substr_found.top(), substr_size);
        substr_found.pop();
    }
}
void erase_page_breaks(std::string& str){
    using std::string;
    const string startPb("<P>");
    erase_substring(str, startPb);
    const string endPb("</P>");
    erase_substring(str, endPb);
}
int main(){
    using namespace std;
    //Per il diritto d'autore:
    //Citazione H.C. Von Baeyer "Informazione" ed. Dedalo
    string test("Le informazioni ci cadono addosso<P> in maniera");
    test += " sottile ma inesorabile, come </P><P>un'invisibile,";
    test += " impalpabile pioggia elettrica.</P>";
    cout << "\n\tStringa originale:\n";
    cout << test << "\n\n";
    erase_page_breaks(test);
    cout << "\tStringa pulita:\n";
    cout << test << "\n\n";
    return EXIT_SUCCESS;
}
//-- fine file cpp --//
Trovo giusto non ottimizzare prematuramente e
non pessimizzare prematuramente.
Ugo

 Ecco le mie poche righe:
LOL
Compimenti, sei riuscito a raddoppiare il codice (esclusi commenti e
righe vuote), raddoppiando anche i tempi di calcolo!
La mia routine era di 12 righe, le tue di 26.
Inserendo le seguenti righe nel tuo main,
     const int n_iter = 10000000;
     clock_t inizio = clock();
     for (int i = 0; i < n_iter; ++i) {
        string s1(test);
        erase_page_breaks(s1);
     }
     cout << (clock() - inizio) * 1.e9 / CLOCKS_PER_SEC / n_iter
        << " ns per iteration\n";
ottengo i seguenti risultati:
Con VisualC++ 7.1: tra 3105 e 3110 nanosecondi per iterazione
Con gcc 3.3.3: tra 118900 e 119100 nanosecondi per iterazione
Se al posto della della riga:
   erase_page_breaks(s1);
metto la riga
   stripPBreaks2(s1);
ottengo invece questi:
Con VisualC++ 7.1: tra 1450 e 1460 nanosecondi per iterazione
Con gcc 3.3.3: tra 34600 e 35400 nanosecondi per iterazione
A parte il fatto che l'implementazione della libreria standard nel gcc 
fa schifo, passando dal mio algoritmo al tuo, il tempo si moltiplica per 
2,1 con Visual C++ e per 3,4 con gcc!


 2,1 con Visual C++ e per 3,4 con gcc!
Esagerato :-)
Ho ripetuto il test che  hai fatto, anche con il profiler e mi risulta
una differenza tra 1.3 e 1.5.
La differenza di prestazioni dipende sia dalla lunghezza della stringa
che dal numero page breaks.
Ugo

 2,1 con Visual C++ e per 3,4 con gcc!
Hai compilato con -O3 con il gcc? Altrimenti non ti esegue l'inline del 
codice, e l'STL senza inline e' pesantuccia :)
Ciao,
  Gabry

 codice, e l'STL senza inline e' pesantuccia :)
Ecco il sorgente del programma:
#include <windows.h>
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
void stripPBreaks2(string &s) {
   const char startTag[] = "<P>";
   const char endTag[] = "</P>";
   string::size_type br = 0;
   while((br = s.find(startTag, br)) != string::npos) {
     s.erase(br, sizeof startTag - 1);
   }
   br = 0;
   while((br = s.find(endTag, br)) != string::npos) {
     s.erase(br, sizeof endTag - 1);
   }
}
int main(){
   string test("Le informazioni ci cadono addosso<P> in maniera");
   test += " sottile ma inesorabile, come </P><P>un'invisibile,";
   test += " impalpabile pioggia elettrica.</P>";
   const int n_iter = 1000000;
   clock_t inizio = clock();
   DWORD inizioWin = GetTickCount();
   for (int i = 0; i < n_iter; ++i) {
      string s1(test);
      stripPBreaks2(s1);
   }
   double elapsedWin = (GetTickCount() - inizioWin) * 1.e6;
   double elapsed = (clock() - inizio) * 1.e9 / CLOCKS_PER_SEC;
   cout << elapsedWin / n_iter << " ns per iteration\n";
   cout << elapsed / n_iter << " ns per iteration\n";
}
// ************ FINE DEL SORGENTE ************ //
Ed ecco la mia sessione di compilazione e test, in cui i prompt sono il 
carattere ">":
 >cl /GX /Ox stripbreaks.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler versione 13.10.3077 per 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.
stripbreaks.cpp
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation.  All rights reserved.
/out:stripbreaks.exe
stripbreaks.obj
 >"time" stripbreaks.exe
1406 ns per iteration
1406 ns per iteration
0.01user 0.00system 0:01.43elapsed 1%CPU (0avgtext+0avgdata 
5856maxresident)k
0inputs+0outputs (377major+0minor)pagefaults 0swaps
 >g++ --version
g++ (GCC) 3.3.3 (cygwin special)
Copyright (C) 2003 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 >g++ -O3 stripbreaks.cpp
 >"time" a
33469 ns per iteration
33469 ns per iteration
33.51user 0.01system 0:33.53elapsed 99%CPU (0avgtext+0avgdata 
12288maxresident)k
0inputs+0outputs (778major+0minor)pagefaults 0swaps
// ************ FINE DELLA SESSIONE ************ //
Come si vede, il programma compilato con "cl", cioe' il compilatore 
Visual C++, impiega 1.4 secondi per fare un milione di iterazioni, 
mentre lo stesso programma compilato con "g++", cioe' il compilatore 
gcc, impiega 33.5 secondi a fare le stesse iterazioni.
Tutto questo con un Pentium 4 a 2,4 Ghz.
Se qualcuno ottiene tempi molto diversi, gradirei saperlo.


 Se qualcuno ottiene tempi molto diversi, gradirei saperlo.
Ho provato il tuo esempio con il DJGPP (GCC 4.01) e ci ha messo circa 3 volte 
rispetto al BCC55, non 30 volte come nel tuo risultato. Non è che hai scritto 
33.5 mentre volevi scrivere 3.35?
EMG
--
EMAG Software Homepage:     
http://www.emagsoftware.it
The EMG's ZX-Spectrum Page: 
http://www.emagsoftware.it/spectrum
The Best of Spectrum Games: 
http://www.emagsoftware.it/tbosg
The EMG Music page:         
http://www.emagsoftware.it/emgmusic
 

 33.5 mentre volevi scrivere 3.35?
Il che conferma il mio test, su un sempron/3000+ con XP ottengo:
1328 VisualC6 ottimizzato
5768 VisualC6 debug
4322 gcc mingw 3.4.4 (-O3 -fomit-frame-pointer)
Su un Athlon XP 2600+ con linux e gcc 4.0.3 invece ottengo
3320 (-O3 -fomit-frame-pointer)
e
3050 (aggiungendo anche -ftree-vectorize -msse2)
Ad avere il tempo guarderei il codice ottimizzato, ma suppongo che il 
visualC faccia qualcosa di furbo per quanto riguarda il ciclo che ha un 
numero fisso di iterazioni, piu` che sull'STL.
Bye,
  Gabry