Newsgroup: it.comp.lang.c++
Titolo: STL e word count ordinato

Salve a tutti!
Sto cercando di realizzare un piccolo metodo in una mia classe che
esegua un word count di un file. Ho pensato di utilizzare la STL perchč
č molto comoda in questi casi, ed in effetti riesco a contare senza
problemi le parole usando la classe map: in pratica faccio una hash
table che usa il la parola come chiave, e un contatore come valore. Fin
qui tutto bene, ma il problema sorge quando voglio ordinare per conteggi
la tabella risultante. Nella definizione della tabella si puň inserire
il tipo di ordinamento desiderato, ma solo (ovviamente) per la chiave...
Sono daccordo che potrei copiare tutto in un vector e ordinare quello
con i metodi specifici, ma mi chiedevo se c'era un modo migliore, cosě
da risparmiare un po' di CPU...
Vi ringrazio della collaborazione.
Bye!
Norman

 writes:

Tu devi comunque fare due ordinamenti, prima alfabetico per vedere se
una parola la si e' gia incontrata e poi numerico in ordine di
frequenza.  Io direi di usare per l'ordinamento quello dei contenitori
STL, proprio come fai tu; ma cosi':
1) definisci una struttura che astragga le tue entita', diciamo una
   string ed un unsigned piu' tutto il resto che ti puo' servire;
2) definisci un set di queste strutture, ordinato alfabeticamente (il
   criterio di ordinamento e' il secondo template parameter di
   std::set);
3) per ogni parola letta, guarda se e' nel set; se non lo e'
   inseriscila; se lo e', incrementa il contatore;
4) definisci un MULTIset di strutture ordinato secondo la frequenza
   numerica, e passa al costruttore il begin() e l'end() del set di
   prima.
Se non e' chiaro, posso tentare di elaborare del codice...
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

    prima.
Mhhh... non so esattamente come la STL lavori internamente, ma credo che il
costruttore del MULTIset faccia una copia dei dati passati con begin() ed end() e
non si limiti a fissare un puntatore (anche perchè la struttura dati è
sconosciuta..). In questo caso non vedo quale sia il vantaggio del creare un
vettore da sortare (se non forse che con il multiset l'ordinamento viene fatto al
momento dell'inserimento dei dati.... mhhhh.... il multiset è una hash table, per
cui deve comunque tenere un'altra tabella per le informazioni di sort. Questa
tabella a causa della dinamicità della hash table del multiset deve essere
percorsa ad ogni inserimento (per trovare il giusto punto di inserimento).
L'algoritmo ha allora complessità n^2 (n=numero inserimenti, nel senso che per
ogni inserimento il caso peggiore è l'intero passaggio della tabella). Al
contrario se si copia il tutto in un vettore, poi viene fatta la copia del vettore
e poi un sort che ha complessità n*log(n). Quindi in teoria la copia nel vettore è
più performante. O sbaglio da qualche parte? :) )
Bye!
Norman


Potresti copiare i dati della map in un'altra map in cui definisci il
numero come chiave. Ma non ti assicuro niente riguardo l'efficienza.
EMG

 ogni inserimento il caso peggiore è l'intero passaggio della tabella).
set e multiset hanno garantito un tempo di inserzione/ricerca O(N ln
N), e sono implementati non come hash tables ma come alberi binari
bilanciati.  Le implementazioni che conosco io usano tutte r-b trees.




Un'idea potrebbe essere questa.
Anzichč copiare tutti gli elementi nel vettore, usiamo un vettore di
puntatori agli elementi della mappa (che sono dei pair<>). Ad esempio:
 typedef map< string, int >	 map_type;
 typedef map_type::value_type    pair_type;
 typedef vector< pair_type* >    vector_type;
...con un opportuno comparatore:
 struct pair_type_ptr_less
 {
   bool operator()( pair_type* a, pair_type* b )
   {
       return( a->second < b->second );
   }
 };
Inseriamo l'indirizzo dei vari elementi nel vattore e ordiniamo il tutto
usando pair_type_ptr_less:
  map_type m;
  vector_type v;
  for( map_type::iterator i = m.begin(); i!= m.end(); ++i )
   {
     v.push_back( &*i );
   }
  sort( v.begin(), v.end(), pair_type_ptr_less() );
Max

Il problema mi e' piaciuto; ho elaborato qualcosa, nel tempo libero, a
partire dal mio suggerimento di ieri.  Si tratta di 114 linee di
codice, che spero mi vorrete perdonare; eccole.
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it
---------Begin file: conta.cxx
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <set>
#include <cctype>
typedef std::map< std::string, unsigned int > msui;
typedef std::pair< std::string, unsigned int > psui;
const char *getWord(
  std::ifstream &ifs
) {
  // Legge dallo stream una parola (definita come un carattere
  // alfabetico seguito da caratteri alfabetici e/o da numeri e/o
  // underscores), e restituisce un pointer alla parola stessa (o
  // NULL all'end-of-file).  Il file puo' terminare in modo non
  // standard (EOF senza \n nell'ultima riga).
  static const size_t bufferLength(128);
  static char         buffer[bufferLength];
  static size_t       next(0);
  static bool         eof_reached(false);
  if (eof_reached) return 0;
  for (;;) {
    char c;
    if ((c = ifs.get()) == EOF) {
      if (next) {
        eof_reached  = true;
        buffer[next] = '\0';
        return buffer;
      } else {
        return 0;
      }
    }
    if (!next) {
      if (isalpha((unsigned char) c)) buffer[next++] = c;
    } else {
      if (isalpha((unsigned char) c)   ||
          isdigit((unsigned char) c)   ||
          c == '_') {
        buffer[next++] = c;
      } else {
        next = buffer[next] = '\0';
        return buffer;
      }
    }
  }
}
struct cPsui {
  // Confronto di due std::pair<std::string, unsigned> ; per un
  // ordinamento in sequenza decrescente del valore numerico.
  bool operator() (const psui & p1, const psui & p2) const {
    return p1.second > p2.second;
  }
};
int main(
  int   argc,
  char *argv[]
) {
  if (argc < 2) {
    std::cerr << "Uso: " << argv[0] << " <nome del file>\n";
  } else {
    std::ifstream ifs(argv[1]);
    if (ifs) {
      msui dict;
      while (const char *pc = getWord(ifs)) {
        std::string    word(pc);
        msui::iterator it;
        if ((it = dict.find(word)) == dict.end()) {
          dict.insert( std::make_pair(word, 1) );
        } else {
          ++(it->second);
        }
      }
      ifs.close();
      std::cout << "\n  Trovate " << dict.size()
                << " parole differenti\n\n";
      if (dict.size()) {
        msui::const_iterator it;
        std::cout << "* In ordine lessicografico:\n";
        for (it = dict.begin();   it != dict.end();   it++) {
          std::cout << "- " << it->first << ": " << it->second
                    << (it->second == 1 ? " volta\n" : " volte\n");
        }
        typedef std::multiset<psui, cPsui> uffa;
        uffa m(dict.begin(), dict.end());
        uffa::const_iterator mit;
        std::cout << "\n* In ordine decrescente di frequenza:\n";
        for (mit = m.begin();   mit != m.end();   mit++) {
          std::cout << "- " << mit->first << ": " << mit->second
                    << (mit->second == 1 ? " volta\n" : " volte\n");
        }
      }
    } else {
      std::cerr << "Errore aprendo il file \"" << argv[1] << "\"\n";
    }
  }
}

 #include <cctype>
allora dovresti scrivere
if (std::isalpha((unsigned char) c)) buffer[next++] = c;
e analogamente per std::isdigit().
EMG

 e analogamente per std::isdigit().
Non sono sicuro; dovrebbe essere cosi', ma KCC ad esempio non lo
accetta (in realta' con KCC isalpha e' una macro del preprocessore).
Pensandoci bene, anche il cast e' ridondante...
Grazie per entrambe le osservazioni!



wrote:
...
      while (const char *pc = getWord(ifs)) {
        std::string    word(pc);
        msui::iterator it;
        if ((it = dict.find(word)) == dict.end()) {
          dict.insert( std::make_pair(word, 1) );
        } else {
          ++(it->second);
        }
      }
Non ho letto bene il tutto... ma una cosa balza agli occhi:
perche' non hai usato 
      while (const char *pc = getWord(ifs)) {
        ++dict[pc];
      }
?
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 ha scritto nel messaggio
news:rmn1gjh...@mlinux.pd.infn.it...

Non era forse meglio usare una std::string?:
                            // istream è più generale di ifstream
inline void getWord(std::string& str, std::istream& is)
{
    is.clear();     // resetta lo stato dello stream
    is >> str;
}
Manlio Perillo

 }
Secondo me no; in questo modo leggi una sequenza di caratteri
delimitati da whitespace.  Io volevo che fossero usati come
delimitatore anche i caratteri non alfanumerici (leggi i commenti).


 ?
Perche' non ci ho pensato :-P                   Grazie!



Scusa, non ci avevo fatto caso.
Comunque vedo dei problemi con il tuo codice.
1) Lo stile è prettamente C non C++, e a chi è abituato al
   C++ e non al C (come me) risulta di non facile lettura.
2) La tua versione di getWord non legge parole del tipo
   "perchè"
Ecco come implementerei io la cosa.
Non so se è esattamente equivalente alla tua versione.
#include <iostream>
#include <string>
#include <locale>
std::string getWord(std::istream& is)
{
   using namespace std;
   string str;
   char ch;
   const ctype<char>& ct = std::use_facet< ctype<char> >(is.getloc());
   ctype_base::mask match = ctype_base::mask(ct.alpha | ct.digit);
   // salta i caratteri non 'validi'
   while( is.get(ch) && !(
ct.is
(match, ch) || ch == '_') );
   if(!is) return str;
   str = ch;
   while( is.get(ch) && (
ct.is
(match, ch) || ch == '_') )
      str.push_back(ch);
   is.putback(ch);
   return str;
}
In questo modo, se si vuole, si può usare un ctype facet in cui
i nostri caratteri accentati (à, ò, è, ì) siano considerati
come alfanumerici.
La cosa è abbastanza semplice ma noiosa.
Si tratta di costruire una tavola di corrispondenze:
char table[255 + 1];
table['a'] = lower | alpha | xdigit;
table['è'] = alpha;
e così via.
Anzi, se si è disposti a fare una cosa del genere, si può fare
una cosa ancora più 'furba' (forse)!
Ossia considerare tutti i caratteri ritenuti non validi nella
tua getWord come whitespace.
In questo modo si può usare direttamente l'estrattore
per le stringhe di istream:
std::locale my_loc(std::locale(""), new my_ctype);
std::ifstream is(/*...*/);
std::locale old = is.imbue(my_loc);
std::string str;
is >> str;
Non l'ho provato ma credo debba funzionare.
Manlio Perillo