Newsgroup: it.comp.lang.c++
Titolo: portabilita' vs. efficienza

premessa: questo e' un esempio, e la questione e' sicuramente piu' 
complessa di come mi appare, ma vorrei una vostra opinione a riguardo
tutti (o quasi :) sappiamo che molta della potenza espressiva del C++ 
attuale e' dovuta all'ottima libreria standard. pero' a volte questa 
porta un calo delle prestazioni e un aumento della dimensione, a fronte 
di una maggior potenza e di un controllo maggiore, e questo per me e' 
un ottimo compromesso.
pero' a volte cio' e' evitabile, facendo opportune ipotesi, magari con 
una compilazione condizionale basata sull'architettura di destinazione.
faccio un esempio: implementare il rot13.
ora, su macchine ascii e' semplice realizzarlo con dei confronti, tipo:
void do_rot13(const std::string& src, std::string& dest){
  std::string::const_iterator it = src.begin();
  dest.assign("");
  dest.reserve(src.length());
  for (;it != src.end(); ++it){
    if ((*it >= 'a') && (*it <= 'm')){
      dest += *it + 13;
    } else
      if ((*it >= 'n') && (*it <= 'z')){
        dest += *it - 13;
      } else
        if ((*it >= 'A') && (*it <= 'M')){
           dest += *it + 13;
        } else
          if ((*it >= 'N') && (*it <= 'Z')){
            dest += *it - 13;
          } else dest += *it;                           
  }
}
se invece la macchina e' un IBM AS/400 e' giocoforza attuare una 
soluzione del tipo
namespace {
  const std::string lower     = "abcdefghijklmnopqrstuvwxyz";
  const std::string lower_rot = "nopqrstuvwxyzabcdefghijklm";
  const std::string upper     = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  const std::string upper_rot = "NOPQRSTUVWXYZABCDEFGHIJKLM";
}
void do_rot13(const std::string& src, std::string& dest){
  std::string::const_iterator it = src.begin();
  dest.assign("");
  dest.reserve(src.length());
  for (;it != src.end(); ++it){
    if (std::islower(*it)) {
      dest += 
lower_rot.at
(lower.find(*it));
    } else
      if (std::isupper(*it)) {
        dest += 
upper_rot.at
(upper.find(*it));
      } else dest += *it;
  }
}
che pero' e' leggermente meno performante, e genera eseguibili 
leggermente piu' grandi. 
Volevo sapere, secondo voi, quando e' piu' conveniente mantenere 
entrambe le soluzioni per macchine differenti, e quando invece e' 
meglio utilizzare la sola versione portabile.
Grazie dell'attenzione

leggermente piu' grandi. 
A meno che tu non debba sviluppare software time-critical penso sia
meglio utilizzare sempre la versione più portabile/leggibile/semplice.
Non penso che pochi byte in più o pochi microsecondi in più possano
cambiare la vita... nei tuoi esempi, però, forse un array di char
sarebbe più veloce di una std::string ...
Luc.

 sarebbe piů veloce di una std::string ...
non mi metto certo a criticare la giustezza della tua affermazione, ma 
per essere un esempio buttato giu' per spiegare quel che penso, mi pare 
vada bene, no?-) e poi (IMHO) usando gli array, non potendo usare find 
e at, il codice sarebbe venuto meno chiaro.
Comunque grazie della tua opinione.

 Comunque grazie della tua opinione.
Concordo con Luc. Prima fai la versione piu' semplice, portabile e leggibile.
Poi se hai MISURATO che la velocità non e' sufficiente, rifalla in maniere che
sia piu' veloce.
Nota che una implementazione piu' veloce non significa che sia meno portabile.
Puoi avere una implementazione che e' sia veloce che portabile, anche se per
scriverla ti serve tempo dato che e' tutt'altro che banale. Ovviamente lo farai
solo nel caso che la velocità sia per te "paramount".
Per esempio: puoi definire una classe apposita. Userà un array statico,
inizializzato da literals, di coppie di caratteri contenenti quello di partenza
e quello di arrivo (std::pair). Avrai opportunamente definito una funzione di
paragone statica binaria sulla coppia (std::pair) che ritorna un bool secondo la
logica di ordinamento del primo carattere (quello di partenza) dettata dal
collate opportuno (std::collate). Data questa funzione puoi eseguire, sempre a
livello di inizializzazione, il sort (std::sort) dell'array. La trasformazione
puo' essere fatta facendo l'overload di operator() (e in tal caso la tua classe
oltre che un singleton e' anche un funzionale ad un parametro). Tale operatore
eseguira' una ricerca binaria (std::binary_search) sull'array usando la stessa
funzione di paragone usata per l'ordinamento e ritornerà il carattere
destinazione della coppia trovata. A questo punto puoi trasformare la stringa
facilmente. Puoi anche trasformare una qualunque sequenza con std::transform. E
di conseguenza puoi anche trasformare un intero file con una riga sola usando
std::transform.
L'idea e' questa. Ma come detto non e' banale.
Tanto per chiarire butto giu' a memoria uno "scheletro". Occhio che cosi' come
e' non funziona di certo: lo sto buttando giu' a razzo come fosse uno schetch a
matita su un foglio.
// header
class Rot13 : public unary_function< char,char > {
    static pair<char,char> mapper[26*2];
    static bool initialized;
    static void initialize();
    static bool compare(const pair<char,char>&,const pair<char,char>&);
public:
    Rot13() { if ( !initialized ) initialize(); }
    char operator()( char c )
    {
        // nota: va corretta per il caso in cui il carattere c
        // non sia fra quelli previsti
        return (*binary_search( &mapper[0],
                                &mapper[26*2-1],
                                make_pair(c,' '), // secondo char ignorato
                                compare )  ).second;
    }
};
// esempio di uso
//transform( input_begin, input_end, output, Rot13() );
// implementation
bool Rot13::initialized = false;
pair<char,char> Rot13::mapper[26*2] = {
    make_pair('a','n'),
    make_pair('b','o'),
    make_pair('c','p'),
    ....
    make_pair('A','N'),
    ....
};
void Rot13::initialize()
{
    sort(&mapper[0],&mapper[26*2-1],Rot13::compare);
    initialized=true;
}
bool Rot13::compare( const pair<char,char>& a, const pair<char,char>& b )
{
    // esegue il paragone fra a.first e b.first ritornando true se
    // a.first < b.first secondo la logica system dependent
    // Nota: usare le classi collate e/o locale fornite dal sistema
    // per non doversi ridefinire la logica
}
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

un ottimo compromesso.
E' ovvio che la comoditą ha il suo prezzo. In fondo con il C++ non sei
affatto obbligato ad usare sempre le std::string, se le prestazioni
sono un problema puoi sempre ricorrere agli array di char e scriverti
a mano le funzioni per manipolare le tue stringhe, cosa che in fondo
non dovrebbe essere troppo difficile. Tuttavia, a meno che non si
abbia a che fare con implementazioni particolarmente bacate , dubito
che il calo di prestazioni sia eccessivo.
Il Ghenio
WINWORD.EXE - ERRORE DI APPLICAZIONE
l'istruzione a "0x3017ff27"ha fatto riferimento alla
memoria a "0x02a3143c".La memoria non poteva essere 'read'.

sono un problema puoi sempre ricorrere agli array di char e scriverti
dovrei avere da qualche parte un vecchio post di San Alex Martelli, il
quale mostrava come spesso std::string e le altre strutture STL sono
*più* efficienti di quelli fatti a mano, non meno. Se vuoi lo riposto.
Anto
--
Antonio Cuni, 18 anni, studente
Brainbench Certification: 
Master C++: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
http://www.brainbench.com/transcript.jsp?pid=1301688

 una compilazione condizionale basata sull'architettura di destinazione.
MI sfugge il punto : quello che dici e' sempre vero su qualunque libreria 
in qualunque linguaggio. Qundo sviluppi devi vare i conti con:
1) tempi di sviluppo 
2) efficenza del codice
3) risorse che il codice richiede
E' chiaro che devi trovare un equilibrio fra queste esigenze; il modo con 
cui lo trovi dipende molto dalle librerie che NON sono perfette; a volte 
cambiare le librerie puo' spostare di parecchio il punto di equilibrio ( ma 
cosi' come il linguaggio ).
In soldoni, non e' detto che la libreria standard ( ma ripeto anche il 
linguaggio C++ ) sia lo strumento migliore per affrontare tutti i problemi; 
cambiando libreria si puo' risolvere. ( Per assurdo basta trovare una che 
ha gia' implementato quello che ti serve .... )

 *più* efficienti di quelli fatti a mano, non meno. Se vuoi lo riposto.
Era una questione puramente algoritmica: std::string::lenght() ad esempio è
più efficiente di strlen() perché non deve calcolare ogni volta la lunghezza
della stringa, ma la legge da un membro.
Ma sicuramente le classi della librerie standard, in un contesto critico,
possono essere implementate decisamente meglio a patto di rinunciare a
feature "non indispensabili", ovviamente in quel particolare contesto.
Le classi standard sono estremamente versatili, quindi l'efficienza in una
particolare funzione deve per forza scendere a compromessi con la
molteplicità di funzioni svolte.
Almeno, io la vedo così...
Massimo

 L'idea e' questa. Ma come detto non e' banale.
[...]
Giusto per esercizio, visto che di applicazioni per il rot13 ne 
esistono a bizzeffe, ho realizzato questa variante, prendendo spunto 
dalla tua, che mi sembra ancora migliore per semplicita'.
namespace {
  const char lower_[]     = "abcdefghijklmnopqrstuvwxyz";
  const char lower_rot_[] = "nopqrstuvwxyzabcdefghijklm";
  const char upper_[]     = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  const char upper_rot_[] = "NOPQRSTUVWXYZABCDEFGHIJKLM";
};
// specializzo il confronto per i miei scopi
template <>
bool std::less< std::pair<char, char> >::
   operator () (const std::pair<char, char>& a,
                const std::pair<char, char>& b) const {
     return a.first < b.first;
}
// utiizzo i set, che hanno la ricerca binaria gestita autonomamente
class rot13 : public unary_function<char, char>{
public:
  rot13();
  char operator() (const char& c) const ;
private:
  static std::set < std::pair<char, char> > lower;
  static std::set < std::pair<char, char> > upper;
  static bool initialized;
  static void init();
};
std::set < std::pair<char, char> > rot13::lower;
std::set < std::pair<char, char> > rot13::upper;
bool rot13::initialized = false;
rot13::rot13() {
  if (!initialized)
    init();
}
void rot13::init() {
  for (int i = 0 ; i < 26; ++i){
    lower.insert(make_pair(lower_[i],lower_rot_[i]) );
    upper.insert(make_pair(upper_[i],upper_rot_[i]) );
  }
  initialized = true;
}
char rot13::operator() (const char&c) const {
  std::set<pair <char, char> >::const_iterator pos;
  if(std::isalnum(c) && !std::isdigit(c)) {
    if (std::islower(c)) {
      pos = lower.find(make_pair(c, ' '));
      if (pos != lower.end())
        return pos->second;
    } else
      if (std::isupper(c)) {
        pos = lower.find(make_pair(c, ' '));
        if (pos != upper.end())
          return pos->second;
      }
  }
  return c;
}
// esempio d'uso
  char prova[] = "Questa e' una stringa di prova"; 
  char buf[64] = {0};
  char* end = prova + strlen(prova);
  std::transform(prova, end, buf, rot13());
Che ne pensate? puo' essere un buon compromesso?

 Che ne pensate? puo' essere un buon compromesso?
Non molto diversa dalla mia (credo, non ricordo la mia :-( ).
Una cosa che non capisco e' perche' usi due set di pair<char,char> definendoti
la funzione d'ordine. Se non altro perche' e' esattamente quello che fa la map!
Cosa c'e' che non va in questa (piu' semplice) versione (salvo typos, la scrivo
in outlook!):
// rot13.hpp
#ifndef _ROT13_HPP
#define _ROT13_HPP
#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
class Rot13: public std::unary_function<char, char> {
public:
    Rot13();
    char operator() (const char& c) const ;
};
template < class InputIt, class OutputIt >
    OutputIt Rot13Code( InputIt begin, InputIt end, OutputIt out )
    {
        std::transform(begin, end, out, Rot13());
    }
template < class Sequence >
    Sequence Rot13Code( const Sequence& s )
    {
        std::vector<Sequence::value_type> v;
        std::transform(s.begin(), s.end(), std::back_inserter(v), Rot13());
        return Sequence(v.begin(),v.end());
    }
/** Samples
    const char prova[] = "Questa e' una stringa di prova";
    char coded[64] = {0};
    char* end = prova + strlen(prova);
    *Rot13Code(prova, end, coded) = '\0';
    std::string prova="Questa e' una stringa di prova";
    std::string coded=Rot13Code(prova);
    const char init[] = "Questa e' una stringa di prova";
    std::vector<char> prova(init,init+strlen(init));
    std::vector<char> coded=Rot13Code(prova);
**/
#endif // _ROT13_HPP
// rot13.cpp
#include "rot13.hpp"
#include <map>
using namespace std;
static bool initialized=false;
static map<char,char> rot_map;
static const char lower_[]     = "abcdefghijklmnopqrstuvwxyz";
static const char lower_rot_[] = "nopqrstuvwxyzabcdefghijklm";
static const char upper_[]     = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static const char upper_rot_[] = "NOPQRSTUVWXYZABCDEFGHIJKLM";
Rot13::Rot13()
{
    if (!initialized) {
        for (int i = 0 ; i < 26; ++i) {
            rot_map.insert(make_pair(lower_[i],lower_rot_[i]));
            rot_map.insert(make_pair(upper_[i],upper_rot_[i]));
          }
        initialized = true;
    }
}
char Rot13::operator() (const char& c) const
{
    map<char,char>::iterator i=rot_map.find(c);
    return i==rot_map.end() ? c : i->second;


 versione (salvo typos, la scrivo in outlook!):
bella, ancora + elementare e generica per l'input.
i due set e la f. ordine, solo per evitare la map, che in alcune imp. 
della lib. std, e' un mostro per codice aggiunto ad ogni chiamata.

 wrote in message news:3779611.G...@tin.it...

E' il solito discorso. Se vuoi una cosa che funge falla in modo semplice. Se poi
la tua app ha problemi specifici (tonnellate di roba da codificare e una
libreria che implementa male la map) puoi sempre ... scriverti una MyMap
specifica per quello (senza implementarla tutta, solo quello che usi) in un
secondo tempo.


secondo tempo.
Per pura curiosita' ho fatto qualche esperimento e ho visto che
con BCC55 la versione basata su std::map e' piu' lenta anche
di una scansione linear in un array... ovvero risulta *peggiore*
di qualcosa del tipo:
  char r13(char x)
  {
    const char *p="ANBOCPDQERFSGTHUIVJWKXLYMZ"
                  "NAOBPCQDRESFTGUHVIWJXKYLZM"
                  "anbocpdqerfsgthuivjwkxlymz"
                  "naobpcqdresftguhviwjxkylzm";
    while(*p!='\0')
    {
      if (p[0]==x) return p[1];
      p+=2;
    }
    return x;
  }
Inoltre con tutti i compilatori con cui ho provato la versione
std::map e' risultata *nettamente* piu' lenta di un versione
"srotolata" basata su switch(...)
  char r13(char x)
  {
    switch(x)
    {
      case 'A' : return 'N';
      case 'B' : return 'O';
      ...
      case 'y' : return 'l';
      case 'z' : return 'm';
    }
    return x;
  }
(con nettamente intendo dire circa il 300%)
Con VC++ e g++ std::map era quasi performante quanto una
versione a ricerca dicotomica ottimizzata su un array di
caratteri organizzato a coppie (da,a) ordinato sul primo
carattere della coppia...
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 carattere della coppia...
Questo non mi stupisce. E' praticamente quello che mi aspetto da una buona
implementazione di map (e della STL in genere).


implementazione di map (e della STL in genere).
Infatti... il problema credevo pero' di aver capito che fosse:
se si vole scrivere codice *portabile* di rot13 senza
sacrificare le prestazioni cosa conviene fare ?
Secondo me, nel 2001, la risposta e' "usare switch". E' semplice,
portabile, e su tutti i compilatori che ho provato e' quello che
genera il codice migliore.
In fondo secondo me la cosa e' anche corretta da un punto di
vista "filosofico". La funzione di traduzione char->char basata
su switch descrive perfettamente il problema nei suoi termini
originali: noi vogliamo tradurre un carattere nel suo
corrispondente. Punto. Nel problema originale gli iterator non
ci sono, la possibilita' di modificare la mappa non esiste.
Usare std::map e' fornire al compilatore gia' la nostra
soluzione... (ovvero usare un container associativo) ma questa
potrebbe non essere la scelta migliore in tutti i contesti
(e spesso nel caso rot13 non lo e' affatto).
In fondo se questa e' la cosa piu' comoda ci pensera' il
compilatore no ? Nota anche che con VC++ quello switch viene
tradotto in una jump-table ... piu' efficiente di quello su
X86 a me viene in mente solo qualcosa del tipo
   template<class it>
   void rot13(it from,it to)
   {
     while(from!=to)
     {
       *from=xlat_table[(unsigned char)*from];
       ++from;
     }
   }
che diventa pero' problematico se CHAR_BIT e' grande.


 genera il codice migliore.
il roting era un esempio, il senso era' piu' generale: quanto conviene 
sacrificare in efficienza, per aumentare la leggibilita' / 
manutenibilita'?
E per inciso, trovo + leggibile la map di un mega switch di 53 
opzioni... ma qui si va sulla conoscenza di un programmatore C++ della 
libreria std C++, il che mi sembra doveroso e, se manca tale 
conoscenza, almeno per sommi capi, manca anche il programmatore C++, 
imho.

 comunque un ottimo programmatore C++... dipende da che cosa deve fare
Si, ma per prendere una decisione del genere deve prima
obbligatoriamente conoscerla tale libreria altrimenti è un partito
preso.
EMG

ci sono, la possibilita' di modificare la mappa non esiste.
magari il mio intervento non sarà significativo, visto che non so di
preciso cosa sia il rot13 e quindi forse scriverò delle cose non
sensate.
Da quello che ho letto mi sembra di aver capito che vi serve un array
associativo char-->char, ma std::map ha prestazioni poco efficienti.
Si potrebbe allora usare un array di ('z'-'a'+1) elementi: se c è il
carattere che dobbiamo convertire basterebbe accedere all'elemento
(c-'a'): in questo modo non c'è bisogno di alcun switch e la ricerca
avviene in tempo costante anzichè lineare.
Conscio di avere probabilemente detto una ca***ta,
ciao Anto


imho.
Hmmm... boh...
Io, come ho gia' detto in passato, trovo che gli algoritmi in
C++ siano un po' limitati dal fatto di non poter definire
codice "in place" in modo comodo (cosa che altri linguaggi come
PERL o anche il vecchio CLIPPER invece permettevano).
Cosa ci sia poi di poco leggibile in quello switch proprio
non lo capisco... non e' che lo dici solo perche' unary_function
e' parte di "C++"-"C" e quindi fa piu' figo ?
Io penso che, nel caso particolare di rot13, la soluzione ideale
sia uno switch per la conversione del singolo carattere e un
template per la conversione di una sequenza...


Conscio di avere probabilemente detto una ca***ta,
Nessuna cavolata... La lookup table credo proprio sia il sistema piu'
comodo nel caso di codifiche generiche purche' a 8 bit; i termini del
problema erano pero' diversi.
Sia std::map che i 52 "if" che lo switch con 52 "case" sono tutti
sistemi piu' portabili.


 template per la conversione di una sequenza...
forse non ho chiarito bene, prima, cio' che intendevo, percio' mi 
ripeto: concordo che lo switch sia il + veloce, ma e' specifico per 
questo algoritmo. e anche cosi', non e' estendibile ai wchar senza 
riscrivere lo switch. la map funziona cambiandone la dichiarazione. e 
dato che e' buona norma definire il tipo del contenitore usato nella 
classe con un
typedef std::map<char, char> Container;
basta cambiare in <wchar, wchar>, o meglio ancora, definire rot13 come 
template sul tipo di char usato, a-la basic_string.
o sto sparandole grosse?-)

   numericamente consecutivi
ok, è vero, non ci avevo pensato. Riesco a capire il perchè non
funzioni nei sistemi in cui le lettere non sono consecutive; però
perchè mai non dovrebbe funzionare sui sistemi non a 8 bit?
